Midterm 2 · 2차 시험범위

Synchronization I · Synchronization II · CPU Scheduling · Memory Management

06. Synchronization I

요약

멀티스레드 프로그램에서 스레드들은 공유 데이터에 동시에 접근하며, 이때 race condition이 발생할 수 있다. 두 스레드가 아무런 동기화 없이 같은 변수를 읽고 쓰면 결과가 실행 순서에 따라 달라져 예측 불가능해진다. 이를 방지하기 위해 critical section을 정의하고, 그 진입·퇴출을 제어하는 메커니즘이 필요하다.

critical section의 올바른 구현이 만족해야 할 조건은 mutual exclusion, progress, bounded waiting이다. 구현 방법으로는 소프트웨어 알고리즘(Peterson's algorithm), 하드웨어 원자 명령(test-and-set, compare-and-swap), 그리고 interrupt 비활성화가 있다. 그러나 spinlock과 인터럽트 비활성화는 오버헤드와 한계가 있어 고수준 동기화 기법의 기반 요소로만 사용된다.

핵심개념

race condition 경쟁 조건

두 개 이상의 스레드(또는 프로세스)가 공유 데이터에 동시에 접근·조작할 때 실행 순서에 따라 결과가 달라지는 상황. 비결정적(non-deterministic) 결과를 낳으므로 반드시 동기화로 제어해야 한다.

critical section 임계 구역

공유 자원(공유 변수, 파일 등)에 접근하는 코드 영역. 한 번에 하나의 스레드만 실행 가능하도록 mutual exclusion을 보장해야 하며, 요구 조건은 mutual exclusion, progress, bounded waiting이다.

lock 잠금

acquire()와 release() 두 연산을 제공하는 동기화 객체. critical section 진입 전 acquire를 호출하고, 퇴출 후 release를 호출한다. 잠금을 획득하지 못한 스레드는 스핀(spinlock) 또는 블록(mutex)한다.

spinlock 스핀락

잠금이 해제될 때까지 CPU를 점유하며 반복 검사(busy waiting)하는 락. 구현이 단순하지만 CPU 사이클 낭비가 심해 짧고 단순한 critical section의 기반 요소로만 사용해야 한다.

Peterson's algorithm 피터슨 알고리즘

두 스레드 간 critical section 문제를 소프트웨어만으로 해결하는 알고리즘(1981). turn과 interested[] 두 변수를 이용하여 mutual exclusion, progress, bounded waiting을 모두 만족한다.

test-and-set 테스트-앤드-셋

메모리 위치의 값을 읽고 1로 설정하는 동작을 원자적으로 수행하는 하드웨어 명령. 락 구현에 사용되며, 이전 값이 0이면 락 획득 성공, 1이면 스핀 대기한다.

compare-and-swap 비교-교환

Swap 명령으로도 불린다. 두 메모리 값을 원자적으로 교환하는 하드웨어 명령. test-and-set과 함께 spinlock 구현에 활용된다.

atomic operation 원자적 연산

중간에 인터럽트되지 않고 전부 실행되거나 전혀 실행되지 않는("all or nothing") 연산. 락 구현 자체의 critical section 문제를 해결하기 위해 하드웨어 수준에서 보장된다.

disabling interrupts 인터럽트 비활성화

cli()/sti()로 인터럽트를 껐다 켜서 컨텍스트 스위치를 막는 방법. 커널 전용이며 멀티프로세서에는 부적합하고, 긴 critical section에서는 타이머·I/O 이벤트를 놓칠 수 있다.

개념정리

1. Synchronization — 필요성과 배경

멀티스레드 프로그램에서 스레드들은 공유 자원 접근과 실행 조율을 위해 협력한다. 스케줄러는 스레드를 임의 순서로 선점(preemptive scheduling) 할 수 있으므로, 응용 개발자는 실행 순서를 제어할 수 없다. synchronization은 실행 인터리빙을 제한함으로써 이 문제를 해결한다. (스레드 뿐 아니라 프로세스 간, 분산 시스템에도 동일하게 적용된다.)

2. The Classic Example — 은행 계좌와 race condition

잔액 100만 원인 공유 계좌에서 두 스레드가 각각 10만 원을 출금하는 시나리오를 생각하자. withdraw 함수는 세 단계로 이루어진다:

balance = get_balance(account) — 잔액 읽기
balance = balance - amount — 감산
put_balance(account, balance) — 잔액 기록

두 스레드가 1·2단계를 모두 마친 뒤 컨텍스트 스위치가 일어나면, 두 스레드 모두 90만 원을 기록해 최종 잔액이 잘못 계산된다. 이것이 race condition의 전형적 예다.

주의 count++ 같은 한 줄짜리 코드도 내부적으로 LOAD → ADD → STORE 세 명령으로 분리되므로 중간에 선점될 수 있다.

3. Sharing Resources — 스레드 간 공유 범위

로컬 변수 — 스택에 저장, 각 스레드 고유, 공유되지 않음.
전역 변수 — static data segment에 저장, 모든 스레드가 공유.
동적 객체 — 힙에 저장, 포인터를 통해 공유.
프로세스 간 — shared-memory 객체, 파일 등을 통해 공유.

4. Critical Sections — 정의와 요구 조건

critical section은 공유 자원에 접근하는 코드 구간이다. 한 번에 하나의 스레드만 실행되어야 하며, 아래 세 조건을 모두 만족해야 한다.

critical section 3대 요구 조건
조건	내용
mutual exclusion	한 번에 최대 하나의 스레드만 critical section 안에 존재
progress	critical section 안의 스레드는 합리적 시간 내에 완료; 바깥의 스레드가 진입을 막으면 안 됨
bounded waiting	대기 중인 스레드는 유한 시간 내에 반드시 진입 가능 (starvation 금지)

구현 메커니즘으로는 lock, semaphore, monitor, 메시지 전달 방식이 있다.

5. Locks — 구조와 사용법

lock은 acquire()와 release()를 제공하는 메모리 객체다. acquire()는 잠금이 비어있으면 획득 후 반환, 다른 스레드가 보유 중이면 대기한다. release()는 잠금을 해제하고 대기 스레드를 깨운다.

Critical section 진입 전 acquire() 호출
퇴출 후 release() 호출
한 번에 최대 한 스레드만 잠금 보유 가능

6. Implementing Locks — 초기 시도와 원자성 문제

held 플래그를 검사하고 설정하는 단순 구현은 그 자체가 critical section이다. 두 스레드가 동시에 while(l->held)를 통과하면 상호 배제가 깨진다. 락 구현 자체를 atomic하게 만들어야 한다는 재귀적 문제(atomicity recursion)가 발생한다.

7. Software-only Algorithms & Peterson's Algorithm

하드웨어 지원 없이 공유 변수만으로 락을 구현하는 알고리즘들이다. 초기 알고리즘(interested[]만 사용)은 mutual exclusion을 만족하지만 progress를 보장하지 못한다.

Peterson's algorithm은 turn과 interested[2] 두 변수를 사용하여 두 스레드에 대해 세 가지 요구 조건을 모두 만족한다. 현대 멀티코어에서는 메모리 재배열 문제로 추가 보장이 필요하지만, 개념 증명으로서 중요하다.

8. Atomic Instructions — test-and-set & compare-and-swap

하드웨어가 제공하는 원자 명령으로 락 구현의 핵심 재귀 문제를 해결한다.

TestAndSet: 메모리 값을 읽고 1로 설정하는 동작을 원자적으로 수행. 이전 값이 0(잠금 없음)이면 락 획득, 1이면 스핀.
Swap: 두 값을 원자적으로 교환. key=1을 잠금 값과 교환하여, 이전 잠금 값이 0이면 획득 성공.

9. Problems with Spinlocks & Disabling Interrupts

spinlock은 잠금 대기 중 CPU를 계속 점유한다. critical section이 길수록, 또는 잠금 보유자가 강제 선점될수록 낭비가 심해진다. 고수준 동기화 구성 요소를 만들기 위한 기반 요소로만 사용해야 한다.

인터럽트 비활성화(cli()/sti())는 컨텍스트 스위치를 차단하지만 세 가지 문제가 있다:

커널 전용 — 사용자 모드에서는 사용 불가
멀티프로세서 환경에서 다른 CPU의 접근을 막지 못함
긴 critical section에서 타이머·I/O 이벤트 누락 위험

10. 동기화 구현 방식 비교

락 구현 방식 비교
방식	핵심 아이디어	장점	한계
소프트웨어 알고리즘 (Peterson's)	`turn` + `interested[]` 변수	하드웨어 불필요, 개념 명확	2스레드만 지원, 현대 CPU 재배열 문제
원자 명령 (test-and-set, swap)	H/W 원자 read-modify-write	멀티프로세서 지원, 구현 간단	busy waiting (CPU 낭비)
인터럽트 비활성화	`cli()`/`sti()`로 선점 차단	단순, 단일 CPU에 효과적	커널 전용, 멀티코어 부적합, 이벤트 누락

참고 spinlock과 인터럽트 비활성화는 모두 primitive한 메커니즘으로, 더 높은 수준의 동기화 구성 요소(semaphore, monitor)를 만드는 기반으로만 사용한다.

예상 서술형문제

Q1 race condition이 발생하는 원인을 설명하고, critical section이 올바르게 동작하기 위해 만족해야 할 세 가지 요구 조건을 각각 서술하시오.

모범답안 보기

race condition 원인: 두 개 이상의 스레드가 공유 데이터에 동기화 없이 동시에 접근·조작할 때 발생한다. 고수준 언어의 단순해 보이는 연산(예: count++)도 내부적으로 LOAD, ADD, STORE 세 명령으로 나뉘므로, 중간에 context switch가 일어나면 두 스레드가 같은 이전 값을 읽은 뒤 각자 갱신하여 결과가 실행 순서에 따라 달라진다.

critical section 요구 조건:

mutual exclusion: 한 번에 최대 하나의 스레드만 critical section 안에 있을 수 있다.
progress: critical section 내 스레드는 합리적 시간 내에 완료해야 하며, 바깥의 스레드가 진입을 방해해서는 안 된다.
bounded waiting (no starvation): 대기 중인 스레드는 유한 번의 시도 안에 반드시 진입할 수 있어야 한다.

Q2 Peterson's algorithm의 동작 원리를 설명하고, 이것이 mutual exclusion을 보장하는 이유를 서술하시오.

모범답안 보기

Peterson's algorithm은 두 개의 공유 변수 turn과 interested[2]를 사용한다.

acquire(i): interested[i] = TRUE로 의사를 표명한 뒤 turn = other로 양보 의사를 나타내고, 상대가 관심 있고 차례도 상대(turn == other)이면 스핀 대기한다.
release(i): interested[i] = FALSE로 의사를 철회한다.

mutual exclusion 보장 이유: 두 스레드가 동시에 critical section에 진입하려면 두 스레드 모두 turn의 값을 자신에게 유리하게 설정해야 한다. 그러나 turn은 마지막 대입 값만 유지되므로, 최종적으로는 한 스레드만 turn == other 조건을 벗어나 진입하게 된다. 따라서 두 스레드가 동시에 루프를 빠져나올 수 없다.

Q3 spinlock의 문제점을 설명하고, 인터럽트 비활성화(disabling interrupts)를 이용한 락 구현이 갖는 한계를 세 가지 서술하시오.

모범답안 보기

spinlock 문제점: 잠금을 얻지 못한 스레드가 busy waiting(반복 검사)을 수행하므로 CPU 사이클을 낭비한다. critical section이 길수록, 또는 잠금 보유 스레드가 비자발적 context switch로 선점될수록 낭비가 심해진다. 따라서 spinlock은 짧은 critical section에서 고수준 동기화 기법을 구현하는 기반 요소로만 사용해야 한다.

인터럽트 비활성화의 한계:

커널 전용: cli()/sti()는 특권 명령이라 사용자 모드 프로그램이 직접 호출할 수 없다. OS가 시스템 콜로 제공해도 악의적 사용자가 인터럽트를 영구 비활성화할 위험이 있다.
멀티프로세서 부적합: 한 CPU의 인터럽트를 꺼도 다른 CPU는 계속 실행되므로 상호 배제가 보장되지 않는다. 결국 atomic instruction이 필요하다.
중요 이벤트 누락: critical section이 길면 비활성화 기간 동안 타이머, I/O 인터럽트 등 중요한 이벤트를 놓치거나 지연시킬 수 있다.

07. Synchronization II

요약

spinlock과 인터럽트 비활성화는 짧은 critical section에만 적합한 저수준 기법이다. 실제 응용에는 대기 스레드를 블록시키고 인터럽트를 허용하는 고수준 동기화 기법이 필요하다. semaphore는 Dijkstra(1968)가 고안한 동기화 기본 요소로, wait()(P)와 signal()(V) 두 원자 연산으로 동작하며 binary semaphore와 counting semaphore 두 종류가 있다.

semaphore는 잘못 사용하면 deadlock이나 starvation을 유발하며, 전역 변수처럼 어디서든 접근 가능해 버그가 생기기 쉽다. 이를 해결하기 위해 언어 수준 구조체인 monitor가 도입되었다. monitor는 공유 데이터와 그 접근 프로시저를 하나로 캡슐화하고, 컴파일러가 동기화 코드를 자동 삽입해 안전한 공유 데이터 접근을 보장한다.

핵심개념

semaphore 세마포어

정수 카운터와 대기 큐로 구성된 고수준 동기화 기본 요소. Dijkstra가 1968년 "THE" OS에서 고안. wait()(P/down)과 signal()(V/up) 두 원자 연산만으로 조작한다. busy waiting이 필요 없다.

wait() / signal() P / V 연산

wait(S)는 카운터를 감소시키고, 0 미만이면 호출 스레드를 블록한다. signal(S)는 카운터를 증가시키고, 대기 중인 스레드가 있으면 하나를 깨운다. 두 연산은 반드시 원자적으로 실행되어야 한다.

binary semaphore 이진 세마포어 (mutex)

카운터를 1로 초기화한 세마포어. 한 번에 하나의 스레드/프로세스만 자원에 접근할 수 있으므로 상호 배제(mutual exclusion) 보장에 사용된다. mutex와 유사하다.

counting semaphore 계수형 세마포어

카운터를 N(자원 단위 수)으로 초기화한 세마포어. 사용 가능한 자원이 남아있는 한 여러 스레드가 동시에 진입할 수 있다. 예: 프린터 5대, 버퍼 N개.

deadlock 교착 상태

두 개 이상의 프로세스가 서로 상대방이 보유한 자원을 영원히 기다리는 상태. 예: P0이 S→Q 순, P1이 Q→S 순으로 wait를 호출하면 순환 대기가 발생한다.

starvation 기아 상태

특정 프로세스가 세마포어 대기 큐에서 영원히 제거되지 않아 실행 기회를 얻지 못하는 상태. 큐의 선택 정책(LIFO 등)이 잘못되면 발생한다.

bounded-buffer problem 유한 버퍼 문제

생산자(producer)와 소비자(consumer)가 유한 크기의 공유 버퍼를 통해 데이터를 교환하는 고전적 동기화 문제. 버퍼 가득 참/비어있음 조건과 상호 배제를 세마포어로 해결한다.

monitor 모니터

공유 데이터 구조와 그 접근 프로시저, 프로세스 간 동기화를 하나로 캡슐화한 프로그래밍 언어 구조체. 컴파일러가 동기화 코드를 자동 삽입하므로 세마포어보다 오용 위험이 낮다. Java의 synchronized가 대표 예다.

condition variable 조건 변수

monitor 내에서 특정 조건이 충족될 때까지 스레드를 대기시키는 메커니즘. wait()로 조건 미충족 시 블록하고, signal()로 대기 스레드를 깨운다.

개념정리

1. Higher-level Synchronization — 동기 저수준 기법의 한계

spinlock과 인터럽트 비활성화는 매우 짧고 단순한 critical section에만 적합하다. 긴 대기가 필요하거나 복잡한 조건 조율이 필요할 때는 낭비가 심하다. 고수준 동기화 기법은 두 가지를 추가로 제공한다:

대기 스레드를 블록(block)시켜 CPU를 양보
critical section 내에서도 인터럽트를 허용

대표적 고수준 기법은 semaphore와 monitor이며, 내부 구현에는 앞서 배운 원자 락을 기반으로 사용한다.

2. Semaphores — 정의와 wait/signal 연산

semaphore는 정수 카운터와 대기 큐를 가진 동기화 객체다. 두 가지 원자 연산만으로 조작한다:

wait(S) [= P(), down()]: 카운터를 1 감소. 카운터가 0 미만이면 호출 스레드를 대기 큐에 삽입하고 블록.
signal(S) [= V(), up()]: 카운터를 1 증가. 대기 큐에 스레드가 있으면 하나를 깨워 준비 큐로 이동.

semaphore는 "역사(history)"를 가진다 — 카운터가 이전 signal 호출을 기억하므로, wait 전에 signal이 먼저 일어나도 정보가 보존된다.

참고 카운터가 음수이면 그 절댓값이 현재 대기 중인 스레드/프로세스의 수다.

3. Implementing Semaphores — block/wakeup 구현

세마포어는 value(정수)와 대기 리스트 L로 구현한다. wait() 내에서 S.value-- 후 값이 음수이면 block()을 호출하고, signal()에서 S.value++ 후 값이 0 이하이면 wakeup(P)로 대기 프로세스를 깨운다. wait/signal 자체가 critical section이므로 하드웨어 원자 명령 또는 인터럽트 비활성화로 보호해야 한다.

4. Types of Semaphores — binary vs. counting

binary semaphore vs. counting semaphore
구분	binary semaphore (mutex)	counting semaphore
초기값	1	N (자원 단위 수)
허용 동시 진입	1개 스레드만	최대 N개 스레드
주요 용도	상호 배제 (mutual exclusion)	다수 자원 관리 (예: 버퍼 슬롯, 프린터)
관계	lock / mutex와 유사	binary semaphore의 일반화

5. Deadlock & Starvation

deadlock은 두 프로세스가 서로 상대방의 자원을 기다리는 순환 대기 상태다. 예를 들어 P0이 wait(S) 후 wait(Q)를, P1이 wait(Q) 후 wait(S)를 호출하면 서로 영원히 대기한다.

starvation은 특정 프로세스가 대기 큐에서 선택되지 않아 영원히 실행되지 못하는 상태다.

priority inversion은 낮은 우선순위 프로세스가 높은 우선순위 프로세스에 필요한 잠금을 보유할 때 발생하는 스케줄링 문제로, priority-inheritance protocol로 해결한다.

6. Classical Problems — Bounded Buffer (Producer-Consumer)

producer는 버퍼가 가득 차면 대기하고, consumer는 버퍼가 비어있으면 대기해야 한다. 세마포어로 해결할 때 세 가지 세마포어를 사용한다:

mutex (초기값 1): 버퍼 접근 상호 배제
empty (초기값 N): 빈 슬롯 수
full (초기값 0): 채워진 슬롯 수

producer: wait(empty) → wait(mutex) → 삽입 → signal(mutex) → signal(full)
consumer: wait(full) → wait(mutex) → 제거 → signal(mutex) → signal(empty)

7. Classical Problems — Dining Philosophers

다섯 명의 철학자가 원형 테이블에 앉아 생각과 식사를 반복한다. 식사하려면 양쪽 젓가락을 동시에 집어야 하며, 젓가락은 5개만 있다. 단순 해결책:

semaphore chopstick[N]: 모두 1로 초기화
철학자 i: wait(chopstick[i]) → wait(chopstick[(i+1)%N]) → eat → signal(chopstick[i]) → signal(chopstick[(i+1)%N])

주의 이 단순 해결책은 모든 철학자가 동시에 왼쪽 젓가락을 집으면 deadlock이 발생한다. 완전한 해결을 위해서는 추가 제약(예: 최대 N-1명만 동시 도전, 홀짝 순서 변경 등)이 필요하다.

8. Problems with Semaphores — 세마포어의 한계

세마포어는 사용하기 어렵고 버그가 생기기 쉽다:

전역 변수처럼 어디서든 접근 가능 — 소프트웨어 공학적으로 나쁜 설계
상호 배제와 조건 조율 두 가지 목적에 혼용되어 혼란 초래
사용 순서 보장 없음 — signal→wait 역전, 이중 wait, wait/signal 누락 등 실수 가능
잘못 사용 시 deadlock이나 starvation 발생

9. Monitors & Condition Variables

monitor는 다음 세 요소를 캡슐화한 프로그래밍 언어 구조체다:

공유 데이터 구조
공유 데이터를 조작하는 프로시저들
concurrent 프로세스 간 동기화

모니터 내부에서는 한 번에 하나의 프로세스만 실행되도록 컴파일러가 자동으로 동기화 코드를 삽입한다. 공유 데이터에는 모니터의 프로시저를 통해서만 접근 가능하므로 구조적으로 잘못된 접근을 방지한다. Java의 synchronized 키워드가 대표적 구현이다.

10. Semaphore vs. Monitor 비교

semaphore vs. monitor 비교
항목	semaphore	monitor
추상화 수준	저수준 — 카운터 + 큐	고수준 — 언어 구조체
동기화 코드 위치	개발자가 직접 wait/signal 호출	컴파일러가 자동 삽입
오용 가능성	높음 (순서 실수, 누락 등)	낮음 (구조적 보호)
언어 지원 필요	불필요 (라이브러리 수준)	필요 (예: Java `synchronized`)
용도	상호 배제 + 조건 조율 모두	공유 자료 구조의 안전한 접근

예상 서술형문제

Q1 semaphore의 wait()와 signal() 연산의 동작을 설명하고, binary semaphore와 counting semaphore의 차이점을 서술하시오.

모범답안 보기

wait(S) [P 연산]: S.value-- 후, 값이 0 미만이면 호출 프로세스를 S.L 대기 큐에 삽입하고 block()을 호출해 CPU를 반납한다.

signal(S) [V 연산]: S.value++ 후, 값이 0 이하이면(즉, 대기 중인 프로세스가 있으면) S.L에서 프로세스 하나를 꺼내 wakeup()으로 깨운다.

두 연산은 반드시 원자적으로 실행되어야 하며, 이를 위해 하드웨어 원자 명령 또는 인터럽트 비활성화를 사용한다.

binary vs. counting semaphore:

binary semaphore: 카운터를 1로 초기화. 한 번에 하나의 스레드만 자원 접근 가능. 상호 배제(mutex)에 사용.
counting semaphore: 카운터를 N으로 초기화. N개 단위의 자원을 N개 스레드가 동시에 사용 가능. 자원 개수 관리에 사용.

Q2 deadlock과 starvation의 차이를 설명하고, 세마포어를 사용할 때 deadlock이 발생하는 구체적인 시나리오를 서술하시오.

모범답안 보기

deadlock: 두 개 이상의 프로세스가 서로 상대방이 보유한 자원을 기다리며 영원히 진행되지 못하는 상태. 모든 관련 프로세스가 블록된다.

starvation: 특정 프로세스가 대기 큐에서 선택되지 않아 실행 기회를 영원히 얻지 못하는 상태. 다른 프로세스들은 계속 진행될 수 있다.

deadlock 시나리오: 두 세마포어 S, Q를 모두 1로 초기화하고, P0이 wait(S) → wait(Q) 순으로, P1이 wait(Q) → wait(S) 순으로 호출한다고 하자. P0이 S를 획득한 뒤 컨텍스트 스위치로 P1이 Q를 획득하면, P0은 Q를 기다리고 P1은 S를 기다리는 순환 대기가 발생해 deadlock에 빠진다.

Q3 semaphore의 문제점을 설명하고, 이를 해결하기 위해 monitor가 어떻게 구조적으로 더 안전한 동기화를 제공하는지 서술하시오.

모범답안 보기

세마포어의 문제점:

전역 변수처럼 프로그램 어디서든 접근·조작 가능하여 소프트웨어 공학적으로 나쁜 설계다.
상호 배제와 조건 조율 두 가지 목적에 혼용되어 의도 파악이 어렵다.
개발자가 wait()/signal() 순서를 직접 관리해야 해서 실수(순서 역전, 누락, 이중 wait 등)가 잦고, 이로 인해 deadlock이나 starvation이 발생한다.

monitor의 해결 방법: monitor는 공유 데이터 구조, 접근 프로시저, 동기화를 하나로 캡슐화한다. 외부에서는 모니터의 프로시저를 통해서만 공유 데이터에 접근할 수 있으므로 비구조적 접근이 차단된다. 동기화 코드는 컴파일러가 자동 삽입해 개발자의 실수를 원천 방지하며, 런타임에 강제된다. Java의 synchronized 키워드가 이 방식을 채택하여, 메서드 진입 시 자동으로 락을 획득하고 퇴출 시 해제한다.

08. CPU Scheduling

요약

CPU scheduling은 실행 가능한 프로세스들 중에서 다음에 실행할 프로세스를 결정하는 기법이다. 스케줄러는 빈번하게 호출되므로 반드시 빠르게 동작해야 한다. 스케줄링 목표는 시스템 유형별로 나뉘는데, 모든 시스템에서는 starvation 방지와 공정성이, 배치 시스템에서는 throughput과 turnaround time이, 대화형 시스템에서는 response time이 핵심 기준이다.

주요 알고리즘으로는 FCFS, SJF, SRTF, Round Robin, Priority Scheduling, Multilevel Feedback Queue가 있다. 다중 프로세서 환경에서는 SMP, processor affinity, NUMA, hyperthreading 등을 추가로 고려해야 한다.

핵심개념

CPU burst / I/O burst CPU 버스트 / 입출력 버스트

프로세스 실행은 CPU burst(연산 구간)와 I/O burst(입출력 대기 구간)의 반복으로 이루어진다. CPU-bound 프로세스는 긴 CPU burst를, I/O-bound 프로세스는 짧은 CPU burst를 많이 가진다. 대부분의 burst는 짧으며, 이 분포가 스케줄링 알고리즘 설계의 기준이 된다.

preemptive scheduling 선점 스케줄링

스케줄러가 실행 중인 프로세스를 강제로 중단하고 context switch를 일으킬 수 있는 방식이다. 반대인 non-preemptive scheduling에서는 프로세스가 자발적으로 CPU를 양보할 때까지 기다린다. 선점 스케줄링은 공유 데이터 접근 중 선점 시 일관성 문제를 유발할 수 있다.

starvation & aging 기아 현상과 에이징

starvation은 높은 우선순위 프로세스가 계속 도착해 낮은 우선순위 프로세스가 영원히 실행되지 못하는 상태다. 해결책인 aging은 대기 시간이 길수록 우선순위를 올려 결국 실행 기회를 얻도록 보장한다.

Round Robin (RR) 라운드 로빈

준비 큐를 원형 FIFO로 취급하며, 각 프로세스에 time quantum(보통 10–100 ms)을 할당한다. starvation이 없고 대화형 응답에 유리하지만, quantum이 너무 짧으면 context switch 오버헤드가 커진다. 경험칙: CPU burst의 80%가 quantum보다 짧아야 한다.

priority inversion 우선순위 역전

높은 우선순위 프로세스가 낮은 우선순위 프로세스가 보유한 자원(락)을 기다리며 실행되지 못하는 현상이다. 1997년 화성 탐사선 Pathfinder 사례가 유명하다. 해결책으로 priority inheritance protocol (PIP)과 priority ceiling protocol (PCP)이 있다.

Multilevel Feedback Queue (MLFQ) 다단계 피드백 큐

여러 우선순위 큐 사이에서 프로세스가 이동할 수 있는 스케줄러다. CPU를 많이 쓰면 낮은 우선순위 큐로 강등되고, 오래 기다리면 높은 우선순위 큐로 승격된다. UNIX scheduler가 이 방식을 사용하며, I/O-bound 프로세스를 우대한다.

SMP & processor affinity 대칭 다중처리와 프로세서 친화성

symmetric multiprocessing (SMP)에서는 각 프로세서가 자체 스케줄링을 수행한다. processor affinity는 프로세스가 현재 실행 중인 프로세서에 캐시 데이터가 남아 있어 같은 프로세서에 계속 실행되길 선호하는 성질이다. 소프트 친화성과 하드 친화성으로 구분된다.

NUMA 비균일 메모리 접근

Non-Uniform Memory Access (NUMA) 아키텍처에서는 CPU마다 로컬 메모리 접근이 리모트 메모리보다 빠르다. 스케줄러는 메모리 배치 알고리즘과 연계해 프로세스를 해당 메모리에 가까운 프로세서에서 실행하도록 고려한다.

hyperthreading 하이퍼스레딩 (동시 멀티스레딩)

하나의 물리 코어에 여러 하드웨어 스레드를 두어, 한 스레드가 memory stall 상태일 때 다른 스레드가 실행되도록 하는 기술이다. 하드웨어 수준의 멀티스레딩으로, 코어 수보다 더 많은 논리 프로세서를 OS에 제공한다.

개념정리

1. CPU Scheduling 개요

CPU scheduling은 실행 가능한(runnable) 프로세스 집합에서 다음에 실행할 프로세스를 선택하는 작업이다. 스케줄러는 매우 자주 호출되므로 빠른 처리가 필수다. dispatcher는 실제로 제어권을 선택된 프로세스에게 넘기는 역할을 하며, context switch 시간이 곧 오버헤드다.

스케줄링 목표 (시스템 유형별):

시스템 유형별 스케줄링 목표
시스템 유형	주요 목표
모든 시스템	starvation 방지, 공정성, 시스템 전체 가동률 유지
배치 시스템	throughput 최대화, turnaround time 최소화, CPU 이용률 최대화
대화형 시스템	response time 최소화
실시간 시스템	데드라인 준수, 예측 가능성

2. Starvation & Preemption

starvation은 필요한 자원(CPU 또는 락)을 다른 프로세스가 계속 점유해 특정 프로세스가 진행하지 못하는 상황이다. 부실한 스케줄링 정책이나 동기화 메커니즘 모두 starvation을 유발할 수 있다.

non-preemptive scheduling에서는 실행 중인 프로세스가 자발적으로 CPU를 반납할 때까지 대기한다. preemptive scheduling에서는 스케줄러가 강제로 context switch를 일으킨다. 선점 시 공유 데이터 일관성과 시스템 콜 처리 중 선점 문제를 고려해야 한다.

3. Execution Characteristics (CPU / I/O Burst)

프로세스는 CPU burst와 I/O burst를 교대로 반복한다. CPU-bound 프로세스는 CPU burst가 길고, I/O-bound 프로세스는 짧은 CPU burst를 많이 가진다. CPU burst 길이의 히스토그램을 보면 대부분이 짧은 burst에 집중되어 있으며, 이 특성이 SJF·RR 같은 알고리즘 설계의 근거가 된다.

4. Process State Queues

운영체제는 프로세스를 상태별 큐로 관리한다. 준비 상태 프로세스는 ready queue에, I/O 대기 프로세스는 각 장치별 device queue에 놓인다. 스케줄러는 ready queue에서 다음 실행 프로세스를 선택하고, dispatcher가 실제 전환을 수행한다.

5. FCFS / SJF / SRTF

FCFS (First-Come, First-Served): 도착 순서대로 실행. 구현이 단순하고 starvation이 없지만, 긴 프로세스 뒤에 짧은 프로세스가 오면 평균 대기 시간이 커진다 (convoy effect).

SJF (Shortest Job First): 예상 CPU burst가 가장 짧은 프로세스를 먼저 실행. 모든 프로세스가 동시에 도착할 때 평균 대기 시간이 최소임이 증명된다. 비선점형. 미래 burst 크기를 알 수 없다는 것이 실용적 한계이며, starvation 가능성이 있다.

SRTF (Shortest Remaining Time First): SJF의 선점형 버전. 새 프로세스 도착 시 현재 프로세스의 남은 burst보다 새 프로세스의 burst가 짧으면 선점한다.

워크드 예제 — FCFS vs SJF (4 프로세스)

프로세스: P1(도착 0, burst 7) · P2(도착 2, burst 4) · P3(도착 4, burst 1) · P4(도착 5, burst 4)

FCFS 간트 차트:

구간	0→7	7→11	11→12	12→16
실행	P1	P2	P3	P4

대기 시간: P1=0, P2=(7−2)=5, P3=(11−4)=7, P4=(12−5)=7
평균 대기 시간 = (0+5+7+7)/4 = 4.75

SJF (비선점) 간트 차트:

t=0: P1만 도착 → P1 실행(0→7).
t=7: P2(4), P3(1), P4(4) 모두 도착 → 최단 P3 선택(7→8) → P2·P4 동착, P2 먼저(8→12) → P4(12→16).

구간	0→7	7→8	8→12	12→16
실행	P1	P3	P2	P4

대기 시간: P1=0, P2=(8−2)=6, P3=(7−4)=3, P4=(12−5)=7
평균 대기 시간 = (0+6+3+7)/4 = 4.0

6. Round Robin (RR)

ready queue를 원형 FIFO로 취급하며, 각 프로세스에 time quantum(보통 10–100 ms)만큼 CPU를 부여한다. quantum 내에 완료되지 않으면 선점 후 큐 끝으로 이동한다. starvation이 없으며 대화형 시스템에 적합하다.

quantum 설정 원칙:

CPU burst의 80%가 quantum보다 짧아야 한다 (경험칙).
quantum이 길수록 throughput 증가, 짧을수록 response time 감소.

워크드 예제 — RR (Q=4)

P1(도착 0, burst 24) · P2(도착 1, burst 3) · P3(도착 2, burst 7)

RR Q=4 간트 차트
구간	0–4	4–7	7–11	11–15	15–18	18–22	22–26	26–30	30–34
실행	P1	P2	P3	P1	P3	P1	P1	P1	P1

완료 시각: P1=34, P2=7, P3=18
대기 시간: P1=34−24−0=10, P2=7−3−1=3, P3=18−7−2=9
평균 대기 시간 = (10+3+9)/3 ≈ 7.33

7. Priority Scheduling

우선순위가 가장 높은 프로세스를 실행한다. SJF는 우선순위 = 예상 CPU burst 길이의 역수인 우선순위 스케줄링의 특수 사례다. 선점·비선점 모두 가능하며, 같은 우선순위 내에서는 RR 또는 FIFO를 적용한다.

Priority Inversion: 낮은 우선순위 프로세스가 락을 보유해 높은 우선순위 프로세스가 실행되지 못하는 현상.

Priority Inheritance Protocol (PIP): 높은 우선순위 프로세스가 자신의 우선순위를 락 보유자에게 임시 위임.
Priority Ceiling Protocol (PCP): 락 획득 즉시 낮은 우선순위 스레드를 사전 설정된 ceiling 값으로 상승.

주의 우선순위 스케줄링에서 starvation을 방지하려면 반드시 aging을 적용해야 한다.

8. Multilevel Queue & Multilevel Feedback Queue

Multilevel Queue Scheduling: ready queue를 여러 큐로 분리 (예: foreground/interactive → RR, background/batch → FCFS). 프로세스는 특정 큐에 고정되며, 큐 간 스케줄링은 고정 우선순위 방식이 일반적이므로 starvation 위험이 있다.

Multilevel Feedback Queue (MLFQ): 프로세스가 큐 사이를 이동할 수 있다. CPU를 많이 사용하면 낮은 우선순위 큐로 강등되고, 낮은 큐에서 오래 대기하면 높은 큐로 승격된다(aging). I/O-bound·대화형 프로세스가 자연스럽게 높은 큐에 머문다.

MLFQ 예시 (3-큐)

Q0: RR 8 ms → Q1: RR 16 ms → Q2: FCFS
새 프로세스는 Q0 진입 → 8 ms 내 미완료 시 Q1으로 강등 → 16 ms 내 미완료 시 Q2로 강등.

9. UNIX Scheduler

UNIX scheduler의 특성:

선점형(preemptive), 우선순위 기반
타임쉐어링: RR 방식으로 timeslice 부여
MLFQ 구조: 큐 간 우선순위 스케줄링 + 큐 내 RR
프로세스 우선순위 동적 변경 (Solaris: 170 레벨, Linux: 0–39)

기본 원칙: I/O-bound 프로세스를 CPU-bound보다 우대해 응답성을 확보. aging으로 starvation 방지.

10. Multiple-Processor Scheduling & NUMA

다중 프로세서 환경에서는 스케줄링이 더 복잡해진다.

Asymmetric multiprocessing: 하나의 마스터 프로세서만 OS 자료구조에 접근 → 단순하지만 병목 위험.
Symmetric multiprocessing (SMP): 각 프로세서가 자체 스케줄링. 공통 ready queue 또는 프로세서별 프라이빗 큐 사용. 현재 가장 일반적.
Processor affinity: 캐시 재사용을 위해 프로세스를 같은 프로세서에서 실행하려는 성질. soft affinity(권고) vs hard affinity(강제).

NUMA 아키텍처에서는 CPU마다 로컬 메모리 접근이 더 빠르므로, 스케줄러와 메모리 배치 알고리즘이 연계되어 processor affinity를 고려한다.

11. Multithreaded Multicore (Hyperthreading)

최근 트렌드: 하나의 물리 칩에 여러 코어를 집적(빠르고 전력 효율 우수). 각 코어에 여러 하드웨어 스레드를 두는 hyperthreading은 한 스레드가 memory stall 상태일 때 다른 스레드가 실행되도록 하여 코어 활용도를 극대화한다. 이는 하드웨어 수준의 멀티스레딩이다.

12. 스케줄링 알고리즘 비교

주요 CPU 스케줄링 알고리즘 비교
알고리즘	선점 여부	핵심 아이디어	장점	단점
FCFS	비선점	도착 순서대로 실행	단순, starvation 없음	convoy effect, 평균 대기 시간 큼
SJF	비선점	최단 burst 프로세스 먼저	평균 대기 시간 최소 (동시 도착 시)	미래 burst 예측 불가, starvation 가능
SRTF	선점	남은 burst 가장 짧은 프로세스 선점	평균 대기 시간 더 최소화	잦은 context switch, starvation 가능
Round Robin	선점	time quantum씩 순환 실행	starvation 없음, 좋은 response time	평균 turnaround time이 SJF보다 큼
Priority	선점/비선점	우선순위 높은 프로세스 먼저	중요도 반영 가능	starvation, priority inversion 문제
MLFQ	선점	큐 간 이동으로 동적 우선순위 조정	I/O-bound 우대, starvation 방지 (aging)	파라미터 튜닝이 복잡

예상 서술형문제

Q1 FCFS, SJF, Round Robin(Q=4) 스케줄링 알고리즘 각각에 대해 개념을 설명하고, 세 알고리즘의 장단점을 비교하시오.

모범답안 보기

FCFS: 도착 순서대로 프로세스를 실행하는 비선점형 알고리즘이다. 구현이 단순하고 starvation이 없지만, 긴 프로세스가 앞에 위치하면 뒤에 오는 짧은 프로세스의 대기 시간이 크게 늘어나는 convoy effect가 발생한다.

SJF: 예상 CPU burst가 가장 짧은 프로세스를 먼저 실행하는 비선점형 알고리즘이다. 모든 프로세스가 동시에 도착할 경우 평균 대기 시간이 최소임이 수학적으로 증명된다. 그러나 미래의 CPU burst 길이를 정확히 알 수 없고, 긴 프로세스가 무기한 대기하는 starvation이 발생할 수 있다.

Round Robin: 각 프로세스에 time quantum만큼 CPU를 부여하고 원형 큐로 순환하는 선점형 알고리즘이다. starvation이 없고 대화형 응답에 유리하지만, quantum이 너무 짧으면 context switch 오버헤드가 커지고 평균 turnaround time이 SJF보다 크다.

참고 quantum 설정 경험칙: CPU burst의 80%가 quantum보다 짧아야 Round Robin이 효과적으로 동작한다.

Q2 priority inversion 문제가 무엇인지 설명하고, 이를 해결하는 Priority Inheritance Protocol (PIP)과 Priority Ceiling Protocol (PCP)의 동작 방식을 비교하시오.

모범답안 보기

Priority Inversion 개념: 높은 우선순위 프로세스 H가 실행되려 하지만, 낮은 우선순위 프로세스 L이 H에 필요한 자원(예: 뮤텍스 락)을 보유하고 있어 H가 진행하지 못하는 상황이다. 1997년 화성 탐사선 Pathfinder에서 실제로 발생한 사례로 유명하다.

Priority Inheritance Protocol (PIP): 높은 우선순위 프로세스 H가 기다리는 자원을 보유한 낮은 우선순위 프로세스 L에게 H의 우선순위를 임시로 물려준다. L이 자원을 반납하면 원래 우선순위로 복귀한다. 동적으로 동작하여 별도의 사전 설정이 필요 없다.

Priority Ceiling Protocol (PCP): 각 자원에 대해 그 자원을 사용할 수 있는 프로세스들의 최대 우선순위를 ceiling 값으로 사전에 설정한다. 프로세스가 자원을 획득하는 즉시 해당 ceiling 값으로 우선순위가 상승한다. 사전 분석이 필요하지만 체계적인 priority inversion 방지가 가능하다.

Q3 Multilevel Feedback Queue (MLFQ)가 Multilevel Queue와 어떻게 다른지 설명하고, UNIX scheduler가 이 방식을 채택하는 이유를 서술하시오.

모범답안 보기

Multilevel Queue: 프로세스가 배정된 큐에 고정된다. 각 큐는 자체 스케줄링 알고리즘을 가지며 (예: foreground → RR, background → FCFS), 큐 간에는 고정 우선순위 스케줄링을 적용한다. 프로세스 특성이 변해도 큐를 이동할 수 없으므로 starvation 위험이 있다.

MLFQ: 프로세스가 큐 사이를 이동할 수 있다. CPU를 오래 사용하면 낮은 우선순위 큐로 강등되고, 낮은 큐에서 오래 대기하면 높은 큐로 승격된다(aging). 결과적으로 I/O-bound·대화형 프로세스는 자연스럽게 높은 우선순위 큐에 머무르고, CPU-bound 프로세스는 낮은 큐로 이동한다.

UNIX scheduler가 MLFQ를 채택하는 이유: 대화형 응답성 확보를 위해 I/O-bound 프로세스(예: 텍스트 편집기)를 CPU-bound 프로세스보다 우대할 필요가 있기 때문이다. 또한 aging을 통해 starvation을 방지하면서 동시에 우선순위를 동적으로 조정하는 유연성을 제공한다.

09. Memory Management

요약

메모리 관리의 목표는 프로그래밍 편의를 위한 추상화 제공, 희소 메모리 자원의 효율적 할당, 그리고 프로세스 간 격리다. 단일 프로그래밍 환경에서는 프로세스가 물리 주소를 직접 사용하지만, multiprogramming에서는 여러 프로세스가 메모리를 공유하므로 보호(protection)와 빠른 주소 변환이 필요하다.

역사적 기법으로 fixed partitions (내부 단편화 문제), variable partitions (외부 단편화 문제), overlays, swapping이 있다. 이러한 한계를 극복하기 위해 virtual memory가 도입되었으며, 각 프로세스는 독립된 가상 주소 공간을 갖고 CPU·OS가 런타임에 물리 주소로 변환한다.

핵심개념

fixed partitions 고정 분할

물리 메모리를 고정 크기의 파티션으로 분할하고, 각 프로세스를 하나의 파티션에 배치한다. 하드웨어 요구사항은 base register뿐이며 (physical address = virtual address + base), 구현이 단순하고 context switch가 빠르다. 그러나 파티션 내 미사용 공간이 낭비되는 internal fragmentation이 발생한다.

variable partitions 가변 분할

프로세스 크기에 맞춰 파티션을 동적으로 할당한다. base register와 limit register를 사용해 주소를 변환하고 보호한다 (물리 주소 > base + limit이면 protection fault). internal fragmentation은 없지만, 프로세스 적재/제거를 반복하면 메모리 곳곳에 작은 구멍이 생기는 external fragmentation이 발생한다.

internal fragmentation 내부 단편화

파티션 내부에 프로세스가 사용하지 않는 메모리 공간이 존재하지만, 다른 프로세스가 사용할 수 없는 상태. fixed partitions의 특징적인 문제다.

external fragmentation 외부 단편화

총 여유 메모리는 충분하지만, 연속된 공간이 아닌 작은 구멍들로 흩어져 있어 새 프로세스를 수용하지 못하는 상태. variable partitions의 특징적인 문제다. 해결책: compaction 또는 paging/ segmentation.

overlays 오버레이

프로세스가 할당된 메모리보다 클 때, 실제로 필요한 코드·데이터만 메모리에 올리는 사용자 수준 기법. OS의 특별한 지원 없이 동작하지만, 프로그래머가 오버레이 구조를 직접 설계해야 하므로 복잡하다.

swapping 스와핑

프로세스 전체를 메모리에서 backing store(빠른 디스크)로 내보내고, 나중에 다시 메모리로 불러와 실행을 재개하는 기법. 스왑 시간의 대부분은 전송 시간이며, 전송량에 비례한다. 현대 OS는 순수 스와핑 대신 demand paging 기반의 수정된 스와핑을 사용한다.

virtual memory 가상 메모리

프로세스가 물리 메모리 크기보다 큰 가상 주소 공간을 사용할 수 있게 해주는 추상화. 각 프로세스는 독립된 virtual address space (VAS)를 가지며, CPU와 OS가 런타임에 가상 주소를 물리 주소로 변환한다. 구현 방법으로 paging과 segmentation이 있다.

base & limit register 베이스·리밋 레지스터

base register: 파티션의 시작 물리 주소를 저장. 물리 주소 = 가상 주소 + base.
limit register: 파티션 크기를 저장. 가상 주소가 limit을 초과하면 protection fault 발생. OS가 context switch 시 레지스터를 교체한다.

개념정리

1. Memory Management 목표와 어려움

메모리 관리의 세 가지 목표:

프로그래밍 편의를 위한 추상화 제공
경쟁하는 프로세스 간 메모리 자원의 효율적 할당 (최소 오버헤드로 최대 성능)
프로세스 간 격리(isolation) 보장

multiprogramming 환경에서는 메모리 관리가 어렵다. 요구사항:

Protection: 프로세스가 다른 프로세스의 주소 공간에 접근하지 못하도록 제한
빠른 주소 변환: 메모리 접근 성능에 직접 영향
빠른 context switch: 보호·변환 하드웨어 업데이트가 신속해야 함

2. Single/Batch Programming

OS에 하나의 사용자 프로세스만 있는 환경. 프로세스가 물리 주소를 직접 사용한다. OS는 작업을 적재(load) → 실행(run) → 제거(unload) 순서로 처리한다. 메모리 레이아웃: OS(ROM 또는 RAM 하단) + 사용자 프로그램. 보호나 변환이 필요 없어 단순하지만, CPU와 I/O의 중첩이 불가능하고 자원 낭비가 크다.

3. Multiprogramming

여러 프로세스를 동시에 메모리에 올려 I/O와 CPU를 중첩 실행한다. 각 프로세스는 가변 크기의 연속된 공간을 필요로 한다. 가상 주소 ↔ 물리 주소 변환이 필수가 된다 (커널이 물리 주소 관리).

참고 동일한 프로그램을 두 사용자가 동시에 실행하면 동일한 가상 주소를 사용하지만, 각자 독립된 물리 메모리 위치에 매핑된다는 점이 virtual memory의 핵심 이점이다.

4. Fixed Partitions

물리 메모리를 동일한(또는 다른) 크기의 고정 파티션으로 분할. 하드웨어 요구: base register만 필요.

물리 주소 = 가상 주소 + base register 값
context switch 시 OS가 base register 교체
파티션 수 = 다중 프로그래밍 정도(degree of multiprogramming)

할당 전략 (파티션 크기가 다를 경우):

First fit: 빈 파티션 중 처음 맞는 것에 할당 (스캔 필요)
Best fit: 가장 크게 들어가는 파티션에 할당 (더 많은 스캔)

주의 internal fragmentation: 파티션 내 프로세스가 사용하지 않는 공간은 다른 프로세스가 쓸 수 없어 낭비된다. 파티션 크기가 고정이면 크고 작은 프로그램 모두를 효율적으로 수용하기 어렵다.

5. Variable Partitions

프로세스 크기에 맞춰 파티션을 동적으로 할당 (IBM OS/MVT). 하드웨어 요구: base register + limit register.

물리 주소 = 가상(offset) 주소 + base register
offset > limit이면 protection fault

할당 전략:

First fit: 충분한 첫 번째 hole에 할당
Best fit: 충분한 가장 작은 hole에 할당
Worst fit: 가장 큰 hole에 할당

주의 external fragmentation: 적재·제거 반복 시 메모리 곳곳에 작은 hole이 생겨 총 여유 공간은 있지만 연속 공간이 부족해진다. 해결책: compaction(hole 통합, 비용 큼) 또는 paging/segmentation.

Fixed Partitions vs Variable Partitions 비교
항목	Fixed Partitions	Variable Partitions
파티션 크기	고정 (동일하거나 사전 설정)	프로세스 크기에 맞춰 동적 결정
하드웨어 요구	base register만	base register + limit register
단편화 유형	internal fragmentation	external fragmentation
구현 복잡도	단순, context switch 빠름	hole 관리 필요, 상대적으로 복잡
대표 OS	IBM OS/MFT	IBM OS/MVT

6. Overlays

프로세스가 할당된 메모리보다 클 때, 실제 필요한 코드·데이터만 메모리에 올리는 기법. 사용자가 직접 구현하며 OS의 특별 지원이 필요 없다. 두 번 패스 어셈블러를 예로 들면, 패스 1과 패스 2는 동시에 필요하지 않으므로 번갈아 메모리에 올릴 수 있다.

장점: 메모리보다 큰 프로세스 실행 가능, OS 지원 불필요
단점: 오버레이 구조 설계가 복잡하고 프로그래머 부담이 큼

7. Swapping

프로세스 전체를 메모리에서 backing store로 내보내고(swap out), 나중에 다시 메모리로 불러와(swap in) 실행을 이어가는 기법.

backing store 요구사항:

빠른 디스크
모든 메모리 이미지를 수용할 만큼 충분히 큼
메모리 이미지에 대한 직접 접근 가능

문제점:

스왑 시간의 대부분이 전송 시간(스왑 크기에 비례)
I/O 대기 중인 프로세스는 스왑 아웃하면 안 됨

참고 현대 OS는 순수 스와핑 대신 demand paging과 결합된 수정된 스와핑 방식을 사용한다.

8. Virtual Memory 개념 도입

동일한 프로그램을 두 사용자가 실행하면 같은 가상 주소(예: 0x08049508)를 참조하지만, 실제 물리 메모리 위치는 다르다. 이것이 가능한 이유가 virtual memory다.

핵심 개념:

프로세스는 virtual address를 사용해 메모리를 참조한다 (크고 연속적).
CPU와 OS가 런타임에 가상 주소를 물리 주소로 변환한다.
물리 메모리는 수요에 따라 동적으로 할당·해제된다 (lazy loading).
각 프로세스는 독립된 가상 주소 공간을 가지므로, 한 프로세스가 다른 프로세스의 주소를 직접 참조할 수 없다.

가상 주소 공간(VAS) 구성 (상위→하위):

커널 영역 (사용자 코드 비가시)
user stack (런타임 생성)
run-time heap (malloc 관리)
read/write segment (.data, .bss)
read-only segment (.init, .text, .rodata)

9. Virtual Memory 장단점 및 구현

장점:

사용자의 논리 메모리를 물리 메모리로부터 분리 → 프로그래머가 메모리 크기 제약에서 자유로워짐
더 많은 프로세스를 동시에 실행 가능
demand paging으로 물리 메모리보다 큰 VAS 사용 가능
I/O 횟수 감소, 파일 및 주소 공간 공유 용이
프로세스 보호 및 생성 효율 향상

단점:

성능 오버헤드 (시간·공간 모두): 주소 변환 비용

구현 방법: paging과 segmentation (이후 챕터에서 상세 다룸)

참고 virtual address space는 프로세스마다 독립적이므로, 두 프로세스가 같은 가상 주소를 가지더라도 서로 다른 물리 메모리를 가리킨다. 이것이 프로세스 격리의 핵심이다.

예상 서술형문제

Q1 fixed partitions와 variable partitions를 비교하고, 각각 발생하는 단편화(fragmentation) 유형과 그 원인을 설명하시오.

모범답안 보기

Fixed Partitions: 물리 메모리를 사전에 고정된 크기로 분할하고 각 프로세스를 하나의 파티션에 배치한다. base register만으로 주소 변환(물리 주소 = 가상 주소 + base)이 가능하며 구현과 context switch가 단순하고 빠르다.

발생 단편화: internal fragmentation — 파티션 크기가 고정되어 있어, 프로세스가 파티션을 꽉 채우지 못하면 남은 공간이 낭비된다. 다른 프로세스가 이 공간을 사용할 수 없다.

Variable Partitions: 프로세스 크기에 맞춰 파티션을 동적으로 할당한다. base register와 limit register로 주소 변환 및 보호를 수행한다. internal fragmentation이 없다는 장점이 있다.

발생 단편화: external fragmentation — 프로세스를 반복적으로 적재·제거하면 메모리 곳곳에 작은 hole이 생긴다. 총 여유 공간은 충분해도 연속된 공간이 없어 새 프로세스를 수용하지 못할 수 있다. 해결책으로 compaction이나 paging/segmentation을 사용한다.

Q2 swapping의 개념과 동작 방식을 설명하고, 스와핑 사용 시 발생하는 문제점과 현대 OS의 해결 방향을 서술하시오.

모범답안 보기

개념: swapping은 메모리에 있는 프로세스 전체를 일시적으로 backing store(빠른 디스크)로 내보내고(swap out), 나중에 다시 메모리로 불러와(swap in) 실행을 재개하는 기법이다. 메모리보다 많은 프로세스를 수용하기 위해 사용된다.

backing store 요구사항: 빠른 디스크, 모든 메모리 이미지를 담을 만큼 충분한 용량, 이미지에 대한 직접 접근 지원.

문제점:

스왑 시간의 대부분이 디스크 전송 시간으로, 스왑 크기에 비례해 오버헤드가 크다.
I/O 작업이 진행 중인 프로세스를 스왑 아웃하면 I/O 데이터 전달 대상이 사라지는 문제가 생긴다. → 따라서 I/O 대기 중인 프로세스는 스왑 아웃하지 않아야 한다.

현대 OS의 해결 방향: 프로세스 전체를 스왑하는 대신, demand paging을 결합한 수정된 스와핑을 사용한다. 필요한 페이지만 디스크에서 메모리로 가져오고, 필요 없어진 페이지를 선택적으로 내보내 전송 비용을 최소화한다.

Q3 virtual memory의 개념을 설명하고, 이것이 이전의 물리 메모리 직접 사용 방식 또는 단순 파티션 방식보다 우수한 이유를 장점 중심으로 서술하시오.

모범답안 보기

개념: virtual memory는 프로세스가 물리 메모리 크기와 무관하게 크고 연속된 주소 공간(virtual address space, VAS)을 사용할 수 있도록 하는 추상화 기법이다. CPU와 OS가 런타임에 가상 주소를 실제 물리 주소로 변환하며, 각 프로세스는 독립된 VAS를 갖는다.

장점:

프로그래밍 편의: 프로그래머가 물리 메모리 크기나 배치를 신경 쓸 필요가 없다. 논리 메모리와 물리 메모리가 분리된다.
물리 메모리보다 큰 프로그램 실행: demand paging을 통해 실제로 필요한 부분만 물리 메모리에 적재할 수 있어, VAS가 물리 메모리보다 커도 실행이 가능하다.
더 많은 동시 프로세스: 각 프로세스의 실제 물리 사용량이 줄어 더 많은 프로세스를 메모리에 수용할 수 있다.
프로세스 격리(protection): 각 프로세스의 VAS가 독립적이므로, 한 프로세스가 다른 프로세스의 메모리에 직접 접근할 수 없다.
파일·주소 공간 공유 용이: 여러 프로세스의 VAS를 같은 물리 페이지에 매핑할 수 있어 공유 라이브러리 등을 효율적으로 구현한다.

단점: 주소 변환 오버헤드로 인한 성능 비용이 있으므로, TLB 등 하드웨어 가속이 필요하다 (이후 챕터 주제).