Chapter 12 · Virtual Memory III

페이지 교체 알고리즘, 스래싱, 워킹셋, 고급 가상 메모리 기능

요약

물리 메모리가 가득 찼을 때 운영체제는 page replacement 알고리즘으로 내보낼 victim page를 결정한다. 이론적 최적인 Belady's algorithm (OPT)은 미래 참조 순서를 알아야 하므로 구현할 수 없지만 다른 알고리즘의 기준선(yardstick)으로 사용된다. 실용 알고리즘에는 FIFO, LRU, second chance (clock), NRU, LFU 등이 있으며, 각각 구현 복잡도와 성능 사이의 트레이드오프가 존재한다.

다수의 프로세스가 경쟁할 때 프레임 할당량이 너무 적으면 thrashing이 발생해 대부분의 시간을 페이지 교체에 낭비한다. working set model은 프로세스가 현재 "필요로 하는" page 집합을 추적하여 다중프로그래밍 수준을 조절하고, page-fault frequency (PFF)는 page fault율에 따라 프레임 수를 동적으로 늘리거나 줄인다.

고급 가상 메모리 기능으로는 두 프로세스가 동일한 물리 프레임을 공유하는 shared memory, fork() 후 실제 쓰기 시점에만 page를 복사하는 copy-on-write (COW), 그리고 파일 I/O를 메모리 참조로 수행하는 memory-mapped files이 있다.

핵심개념

page replacement 페이지 교체

빈 frame이 없을 때 기존 page를 내보내고 새 page를 적재하는 절차. 내보낼 page를 victim이라 한다.

reference string 참조 문자열

프로세스가 참조하는 page 번호의 순서열. 알고리즘 분석 시 page fault 횟수를 계산하는 데 사용된다.

dirty bit (modify bit) 더티 비트

page가 메모리에 적재된 이후 수정되었는지 표시하는 PTE 비트. victim page가 dirty이면 디스크에 write-back이 필요하고, clean이면 단순 폐기로 I/O를 절약한다.

Belady's algorithm (OPT) 최적 알고리즘

앞으로 가장 오랫동안 참조되지 않을 page를 교체한다. page fault 횟수가 이론적 최솟값이지만 미래를 알아야 하므로 실제 구현이 불가능하며, 다른 알고리즘의 성능 척도(yardstick)로 활용된다.

FIFO 선입선출

가장 먼저 메모리에 올라온 page를 교체한다. 구현이 단순하지만 Belady's anomaly가 발생할 수 있다.

Belady's anomaly 벨라디 이상 현상

프레임 수를 늘렸는데 오히려 page fault 횟수가 증가하는 현상. FIFO에서 발생 가능하며 LRU에서는 발생하지 않는다.

LRU 최근 최소 사용

과거에 가장 오랫동안 참조되지 않은 page를 교체한다. OPT의 근사이며 Belady's anomaly가 없다. 구현에 카운터 또는 스택, 혹은 하드웨어 지원이 필요하다.

reference bit (R bit) 참조 비트

PTE에 있는 비트로, page가 읽히거나 쓰일 때 하드웨어가 자동으로 1로 설정한다. second chance·NRU· LFU 구현에 활용된다.

second chance (clock) 두 번째 기회 / 클록 알고리즘

모든 frame을 원형으로 배치하고 시계 바늘이 순회한다. R bit가 0이면 victim으로 선택하고, 1이면 0으로 지우고 다음으로 넘어간다. FIFO에 두 번째 기회를 추가한 근사 LRU 기법이다.

not recently used (NRU) 최근 미사용

R bit와 M(modify) bit를 조합해 page를 4가지 클래스(0~3)로 분류하고, 번호가 가장 낮은 nonempty 클래스에서 무작위로 교체한다. Macintosh에서 사용되었다.

LFU 최소 빈도 사용

각 page의 참조 횟수를 소프트웨어 카운터로 유지하여 횟수가 가장 적은 page를 교체한다. aging 기법으로 최근성을 반영한다.

frame allocation 프레임 할당

다중 프로세스 환경에서 각 프로세스에 물리 프레임을 나누어 주는 정책. 고정 공간(fixed space / local replacement)과 가변 공간(variable space / global replacement)으로 나뉜다.

thrashing 스래싱

프로세스에 할당된 프레임이 너무 적어 page fault가 극단적으로 많이 발생하고, OS가 page를 디스크와 주고받는 데만 시간을 소모하여 유용한 작업을 거의 하지 못하는 상태.

locality 지역성

프로세스는 일정 시간 동안 제한된 page 집합만 집중적으로 참조하는 경향이 있다. working set model의 이론적 근거이다.

working set 워킹셋

프로세스가 최근 w회의 참조(working-set window) 동안 접근한 page 집합 WS(t, w). 이 집합이 메모리에 없으면 thrashing이 발생한다.

working-set window 워킹셋 윈도우

working set을 계산하는 시간 구간의 크기 w. page 참조 횟수 단위로 측정하며, w가 너무 작으면 locality를 충분히 반영하지 못하고 너무 크면 과대 추정한다.

PFF (page-fault frequency) 페이지 폴트 빈도

각 프로세스의 page fault율을 모니터링해 상한 초과 시 프레임을 추가하고 하한 미달 시 프레임을 회수하는 동적 프레임 조절 정책.

shared memory 공유 메모리

두 프로세스의 PTE를 동일한 물리 frame에 매핑하여 데이터를 직접 메모리 참조로 공유하는 기법. 각 PTE는 서로 다른 보호 권한을 가질 수 있다.

copy-on-write (COW) 쓰기 시 복사

fork() 후 부모와 자식이 같은 물리 page를 읽기 전용으로 공유하다가, 어느 쪽이 쓰기를 시도하는 순간 해당 page만 복사하고 매핑을 분리한다. 불필요한 복사를 피해 fork() 비용을 줄인다.

memory-mapped file 메모리 매핑 파일

mmap()으로 파일을 가상 주소 공간에 바인딩하여 포인터 접근으로 파일 I/O를 수행하는 기법. 파일이 해당 영역의 backing store 역할을 한다.

개념정리

1. Page Replacement 개요

demand paging 환경에서 프로세스가 허용된 모든 frame을 소진한 상태에서 새 page fault가 발생하면, OS는 기존 page 중 하나를 내보내야 한다. 이 과정을 page replacement라 한다.

OS는 교체할 victim page를 선택해 디스크로 내보낸다(evict).
victim이 dirty (modified)이면 디스크에 write-back이 필요하고, clean이면 단순 폐기로 I/O를 절약할 수 있다.
교체 알고리즘의 목표는 page fault 횟수를 최소화하는 victim을 선택하는 것이다.
이상적인 victim은 앞으로 절대 참조되지 않을 page이다 — Belady's proof.

2. Optimal(Belady) & FIFO

Optimal (OPT / Belady's algorithm) — 미래 참조 중 가장 나중에 쓰일 page를 교체한다. page fault 횟수가 이론적 최솟값이지만 미래를 예측해야 하므로 구현이 불가능하다. 다른 알고리즘과 비교하여 개선 여지를 측정하는 yardstick으로 활용한다. OPT가 다른 알고리즘과 큰 차이가 없으면 그 알고리즘은 충분히 좋고, 차이가 크면 개선 여지가 있다.

FIFO — 가장 먼저 메모리에 올라온 page를 교체한다. 구현이 단순하지만, 오래 전에 올라왔다는 이유만으로 자주 쓰는 page까지 내보낼 수 있다. 또한 Belady's anomaly가 발생할 수 있다.

주의 Belady's anomaly: 프레임 수를 늘렸을 때 오히려 fault가 증가하는 역설적 현상. FIFO에서 발생 가능하며 LRU·OPT에서는 발생하지 않는다.

알고리즘별 fault 횟수 비교 (reference string = 1 2 3 4 1 2 5 1 2 3 4 5):

FIFO — Belady's anomaly 예제 (슬라이드 slide 6–7)
프레임 수	1	2	3	4	1	2	5	1	2	3	4	5	합계
3 frames	F	F	F	F	F	F	F	F	F	-	-	-	9
4 frames	F	F	F	F	-	-	F	F	F	F	F	-	10

3 frames → 9 faults, 4 frames → 10 faults: 프레임이 늘었는데 fault가 더 많다 — Belady's anomaly.

page replacement 알고리즘 비교 (3 frames, 동일 reference string)
알고리즘	핵심 아이디어	faults (3 frames)	특징 / 한계
OPT	미래에 가장 오래 안 쓰일 page 교체	7	이론적 최적, 구현 불가 (미래 참조 필요)
FIFO	가장 먼저 들어온 page 교체	9	구현 단순, Belady's anomaly 발생 가능
LRU	과거에 가장 오래 참조 안 된 page 교체	10	OPT 근사, Belady's anomaly 없음, 하드웨어 지원 필요

참고 위 예제에서 LRU가 FIFO보다 fault가 많은 것은 이 특정 reference string의 특성 때문이다. LRU는 일반적으로 FIFO보다 우수하며, Belady's anomaly가 없다는 이론적 보장이 있다.

3. LRU (Least Recently Used)

과거 참조 이력을 이용하여, 가장 오랫동안 참조되지 않은 page를 교체한다. "과거는 미래의 근사(past gives a guess of future)"라는 가정에 기반하며 Belady's anomaly가 발생하지 않는다. LRU는 과거를 보고, OPT는 미래를 본다.

구현 방식:

Counter implementation: 각 page의 PTE에 타임스탬프를 기록하고, fault 시 카운터가 가장 작은(가장 오래된) page를 선택한다.
Stack implementation: 참조될 때마다 해당 page를 스택 맨 위로 이동. 스택 바닥이 LRU page이다.

완전한 LRU 구현은 모든 메모리 접근마다 하드웨어가 타임스탬프를 갱신해야 하므로 비용이 크다. 실제로는 PTE의 R bit를 이용한 근사(approximation)를 사용한다.

LRU 근사 — counter 방식 (slide 10 참조)
시점	동작
주기적 인터럽트 시	R = 0이면 카운터 증가(오래 안 씀); R = 1이면 카운터 = 0(최근 사용). R bit 초기화.
교체 시	카운터 값이 가장 큰 page = LRU → victim 선택.

참고 일부 아키텍처는 R bit를 제공하지 않는다. 이 경우 valid bit를 0으로 만들어 인위적으로 fault를 유도해 참조 시점을 탐지하는 방법으로 R bit를 시뮬레이션할 수 있다.

4. Second Chance & NRU

Second chance (clock algorithm) — 모든 물리 frame을 원형(시계 모양)으로 배치하고 시계 바늘로 순회한다.

바늘이 가리키는 frame의 R bit가 0이면 victim 선택.
R bit가 1이면 0으로 지우고 다음 frame으로 이동 — "두 번째 기회(second chance)" 부여.
메모리가 충분하면 바늘이 천천히 움직이고, 메모리가 부족하면 빠르게 순회한다.
메모리가 매우 크면 정보의 정확도가 낮아지는 한계가 있다.

NRU (Not Recently Used / enhanced second chance) — R bit와 M(modify) bit를 결합하여 page를 4가지 클래스로 분류한다.

NRU 4가지 클래스 (slide 13)
클래스	R bit	M bit	의미	교체 우선순위
0	0	0	최근 미참조, 미수정	최우선 교체
1	0	1	최근 미참조, 수정됨	두 번째
2	1	0	최근 참조, 미수정	세 번째
3	1	1	최근 참조, 수정됨	최하위 교체

번호가 가장 낮은 nonempty 클래스에서 무작위로 page를 교체한다. 수정된 비참조 page(클래스 1)가 참조된 깨끗한 page(클래스 2)보다 교체 우선순위가 높다. 이해하기 쉽고 구현 비용이 적당하며 Macintosh에서 사용되었다.

참고 클록 인터럽트마다 R bit를 주기적으로 초기화하여 최근 참조 여부를 구분한다.

5. LFU (Least Frequently Used)

각 page마다 소프트웨어 카운터를 유지하고, 주기적 인터럽트 시 R bit 값을 카운터에 누적한다. 카운터 값은 각 page가 얼마나 자주 참조되었는지를 나타낸다.

LFU (Least Frequently Used): 카운터 값이 가장 작은(참조 빈도 최저) page를 교체한다.
MFU (Most Frequently Used): 카운터 값이 가장 큰 page를 교체한다. "카운터가 작은 page는 방금 올라온 것"이라는 역발상이다.

Aging — 카운터를 오른쪽으로 1비트 시프트(shift right)한 뒤 R bit를 최상위 비트(leftmost)에 추가한다. 오래된 참조는 점차 가중치가 줄어들어 최근성을 반영한다.

참고 초기에 집중적으로 사용된 후 다시는 쓰이지 않는 page는 카운터가 높게 누적되어 교체되지 않는 문제가 있다. Aging은 이 문제를 완화한다.

6. Allocation of Frames

다중프로그래밍 환경에서 물리 메모리를 여러 프로세스에 나눠 줄 때 두 가지 전략이 있다.

프레임 할당 전략 비교 (slide 17)
전략	설명	교체 범위	장단점
fixed space (local replacement)	각 프로세스에 고정된 프레임 수 배정	자신의 프레임에서만 교체	한 프로세스가 잘 동작해도 다른 쪽이 손해 볼 수 있음
variable space (global replacement)	프로세스 프레임 집합이 동적으로 변화	임의 프로세스의 프레임 교체 가능	한 프로세스가 다른 프로세스의 메모리를 빼앗을 수 있음 (Linux 사용 방식)

victim page가 다른 프로세스 소유일 수 있으며, 각 프로세스에 얼마나 많은 메모리를 줄지 결정하는 것이 핵심 문제이다.

7. Thrashing

thrashing은 OS가 page fault를 처리하느라 대부분의 시간을 디스크 I/O에 소비하고 유용한 작업을 거의 하지 못하는 상태이다.

시스템 전체적으로 메모리가 과도하게 커밋된(overcommitted) 상태에서 발생한다.
OS는 어떤 page를 메모리에 두어야 fault를 줄일 수 있는지 파악하지 못한다.
물리 메모리 자체가 모든 프로세스를 수용하기에 부족한 경우에도 발생한다.

가능한 해결책:

프로세스 하나의 모든 page를 디스크로 내보내어(swap out) 메모리를 확보한다.
물리 메모리를 증설한다(buy more memory).

8. Working Set Model

Peter Denning(1968)이 제안한 working set은 프로세스가 현재 "필요로 하는" page의 집합이다. 프로그램의 locality에 기반하여 메모리 사용의 동적 지역성을 모델링한다.

정의: WS(t, w) = { 시각 t 이전 w번의 참조 구간 (t−w, t) 동안 참조된 page 집합 }

t: 현재 시각 (CPU 가상 시간으로 측정)
w: working-set window 크기 (page 참조 횟수 단위)
working set size (WSS): WS(t, w)의 page 수 — locality 변화에 따라 달라진다.

working set이 메모리에 없으면 heavy faulting(thrashing)이 발생한다.

WSS 기반 다중프로그래밍 제어:

각 프로세스에 WSS 파라미터를 연결한다.
모든 프로세스의 WSS 합이 총 frame 수를 초과하면 → 프로세스 하나를 일시 정지(suspend).
새 프로세스는 WSS가 여유 frame 내에 들어올 때만 시작을 허용한다.

Working set page replacement 구현 (slide 24):

각 PTE에 Time of last use (Tlast) 필드를 유지한다.
주기적 클록 인터럽트 시 R bit를 초기화한다.
page fault 시 page table을 스캔하여 evict 대상을 탐색한다:
- R = 1 이면 Tlast = Tcurrent (현재 시각으로 갱신).
- R = 0 이고 (Tcurrent − Tlast) > w 이면 → evict (워킹셋 밖).
- R = 0 이고 (Tcurrent − Tlast) < w 이면 → 유지 (워킹셋 내).

9. PFF (Page-Fault Frequency)

PFF는 각 프로세스의 page fault율을 직접 모니터링하여 프레임 수를 동적으로 조절하는 정책이다.

fault율 > 상한(upper bound) → 해당 프로세스에 frame 추가 (fault를 줄이기 위해).
fault율 < 하한(lower bound) → 해당 프로세스에서 frame 회수.
PFF가 증가하는데 여유 frame이 없으면 → 프로세스를 일시 정지(suspend).

주의 frame을 추가해도 fault율이 줄지 않는 경우가 있다 — FIFO의 Belady's anomaly가 그 예이다. PFF가 항상 만능은 아니다.

10. Shared Memory

각 프로세스는 독립된 가상 주소 공간으로 서로를 보호하지만, 이로 인해 데이터 공유가 어렵다. 예를 들어 forking Web 서버에서 부모와 자식이 in-memory cache를 복사 없이 공유하거나, 공유 라이브러리를 실행(execute)할 때 공유가 필요하다.

shared memory는 두 프로세스의 PTE를 동일한 물리 frame에 매핑하여 직접 메모리 참조로 데이터를 공유한다.

두 프로세스 모두 공유 메모리 세그먼트의 갱신을 바로 볼 수 있다.
각 PTE는 서로 다른 보호 권한(read/write, execute)을 가질 수 있다.
page가 invalid 상태가 되면 두 PTE를 모두 갱신해야 한다.
공유 데이터 접근 조율에는 별도의 동기화 메커니즘이 필요하다.

Linux POSIX 예시 (sys/shm.h):

생성 프로세스: shmget(key, SIZE, IPC_CREAT | 0644) → shmat()로 attach.
참여 프로세스: 동일 key로 shmget() → shmat()로 attach 후 직접 읽기.

11. Copy-on-Write (COW)

fork()는 부모 프로세스의 전체 주소 공간을 자식에게 복사해야 하므로 매우 느리고 비효율적이다. 이를 해결하는 방법 세 가지:

threads 사용: 주소 공간 공유가 기본이므로 복사 비용 없음.
vfork(): 자식이 부모의 주소 공간을 그대로 공유. 자식이 exit하거나 exec할 때까지 부모는 블로킹. 자식의 변경이 부모에게도 보인다.
Copy-on-Write (COW): fork 직후 복사하지 않고, 부모·자식이 동일 물리 page를 읽기 전용으로 공유한다.

COW 동작 단계:

fork 후 부모와 자식의 PTE가 모두 동일한 물리 page를 읽기 전용(read-only)으로 가리킨다.
읽기 접근은 평소처럼 동작한다.
어느 쪽이 page에 쓰기를 시도하면 protection fault 발생 → OS로 trap.
OS가 해당 page를 복사하여 새 물리 frame에 넣고, 쓴 쪽의 PTE를 새 frame으로 변경.
쓰기 명령을 재시작(restart)한다.

실제로 수정된 page만 복사가 발생하여 불필요한 복사 비용을 대폭 줄일 수 있다.

12. Memory-Mapped Files

memory-mapped files는 mmap()을 사용하여 파일을 가상 주소 공간의 한 영역에 바인딩한다. 포인터를 통한 메모리 참조로 파일 I/O를 수행하므로 open()/read()/write()/close() 시퀀스가 불필요하다.

PTE가 가상 주소를 파일 데이터를 담은 물리 frame에 매핑: 가상 주소 base + 오프셋 N = 파일의 N번째 바이트.
초기에는 매핑 영역 내 모든 page가 invalid. 접근 시 OS가 파일에서 page를 읽어온다.
물리 메모리에서 내보낼 때(evict) dirty이면 파일로 write-back; clean이면 단순 폐기.
여러 프로세스가 동일 파일을 mmap하면 물리 메모리 내 page를 공유할 수 있다.

Memory-Mapped Files 장단점 (slide 39)
장점	단점
파일과 메모리 접근이 동일한 인터페이스 (포인터)	프로세스가 데이터 이동 시점을 직접 제어하기 어려움
복사 횟수 감소 (less copying)	파이프·소켓 같은 streamed I/O에는 적용 불가
여러 프로세스 간 파일 page 공유 가능

참고 mmap 영역의 backing store는 swap 공간이 아니라 매핑된 파일이다. 실제 파일과 연결되지 않은 익명 영역(anonymous VM / anonymous page)만 swap을 backing store로 사용한다.

예상 서술형문제

Q1 page replacement가 필요한 상황을 설명하고, Belady's algorithm (OPT)이 이론적으로 최적임에도 실제 구현이 불가능한 이유를 서술하시오. 또한 실무에서 OPT를 어떤 용도로 활용하는지 설명하시오.

모범답안 보기

demand paging 환경에서 모든 가용 frame이 소진된 상태에서 page fault가 발생하면 OS는 기존 page를 내보내야(evict) 한다. 이때 어떤 page를 내보낼지 결정하는 것이 page replacement이다.

OPT는 앞으로 가장 오랫동안 참조되지 않을 page를 교체하므로 page fault 횟수가 이론적 최솟값이다. 그러나 이 알고리즘은 미래의 참조 순서를 미리 알아야 victim을 결정할 수 있기 때문에 실제 운용 시스템에서는 구현이 불가능하다. 실무에서는 OPT를 yardstick으로 활용한다. 즉, 특정 workload에서 OPT의 fault 횟수와 실제 알고리즘의 fault 횟수를 비교하여 알고리즘의 개선 여지를 측정하는 기준선으로 사용한다. OPT와 차이가 작으면 그 알고리즘은 충분히 좋고, 차이가 크면 개선의 여지가 있다.

Q2 reference string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5에 대해 3개 프레임과 4개 프레임을 사용할 때 FIFO 알고리즘의 page fault 수를 각각 구하고, Belady's anomaly가 무엇인지 결과와 함께 설명하시오.

모범답안 보기

FIFO 3 frames — 참조 순서별 상태: 1(F:[1]), 2(F:[1,2]), 3(F:[1,2,3]), 4(F→1 퇴출:[2,3,4]), 1(F→2 퇴출:[3,4,1]), 2(F→3 퇴출:[4,1,2]), 5(F→4 퇴출:[1,2,5]), 1(F→1 퇴출:[2,5,1]), 2(F→2 퇴출:[5,1,2]), 3(-:[5,1,2]→hit), 4(-:hit), 5(-:hit) → 총 9 faults.

FIFO 4 frames: 1(F), 2(F), 3(F), 4(F:[1,2,3,4]), 1(hit), 2(hit), 5(F→1 퇴출:[2,3,4,5]), 1(F→2 퇴출:[3,4,5,1]), 2(F→3 퇴출:[4,5,1,2]), 3(F→4 퇴출:[5,1,2,3]), 4(F→5 퇴출:[1,2,3,4]), 5(hit) → 총 10 faults.

Belady's anomaly는 프레임 수를 늘렸음에도 오히려 page fault 횟수가 증가하는 역설적 현상이다. 위 예에서 3 frames → 9 faults, 4 frames → 10 faults로 프레임이 1개 늘었는데도 fault가 1개 더 발생했다. 이 현상은 FIFO에서 발생할 수 있으며, LRU나 OPT에서는 발생하지 않는다.

Q3 thrashing이 무엇인지 정의하고 발생 원인을 설명하시오. working set model이 thrashing을 방지하는 원리를 WS(t, w) 정의와 함께 서술하시오.

모범답안 보기

thrashing이란 프로세스에 할당된 frame이 너무 적어 page fault가 과도하게 발생하고, OS가 page를 디스크와 주고받는 데만 시간을 소모하여 유용한 작업 처리량이 급감하는 상태이다. 시스템이 overcommitted되었거나 물리 메모리 자체가 부족할 때 발생한다.

working set model은 프로세스가 일정 시간 동안 제한된 page 집합만 집중 참조하는 locality 성질을 이용한다. WS(t, w)는 시각 t 이전 w회의 참조 구간 동안 접근된 page 집합이며, 이 집합을 메모리에 유지해야 thrashing을 방지할 수 있다. 운영체제는 각 프로세스의 WSS를 추적하여, 모든 프로세스의 WSS 합이 총 frame 수를 초과하면 프로세스를 일시 정지(suspend)한다. 이를 통해 다중프로그래밍 수준을 조절하여 thrashing 없이 최대한 많은 프로세스를 실행한다.

Q4 second chance (clock) 알고리즘의 동작 원리를 R bit의 역할과 함께 단계별로 서술하고, 이 알고리즘이 순수한 FIFO와 어떻게 다른지 비교하시오.

모범답안 보기

① 모든 물리 frame을 원형으로 배치하고 시계 바늘을 유지한다. ② 교체가 필요하면 바늘이 현재 가리키는 frame의 R bit를 확인한다. ③ R = 0이면 해당 frame을 victim으로 선택하고 page를 교체한다. ④ R = 1이면 R bit를 0으로 지우고("두 번째 기회" 부여) 다음 frame으로 넘어간다. ⑤ 한 바퀴를 완전히 돌아 R = 0인 frame을 찾을 때까지 반복한다.

FIFO는 도착 순서만으로 victim을 선택하므로 최근에 참조된 page도 가장 오래된 것이면 교체된다. 반면 second chance는 최근 참조된 page(R = 1)에게 교체를 한 번 면제해 주어 자주 사용되는 page가 불필요하게 교체되는 FIFO의 단점을 완화한다. 하드웨어 R bit만 있으면 구현할 수 있는 근사 LRU이다.

Q5 copy-on-write (COW)가 fork()에서 어떻게 동작하는지 단계별로 설명하고, COW가 없을 때와 있을 때의 차이를 메모리 복사 비용 관점에서 비교하시오.

모범답안 보기

COW 없이 fork()를 수행하면 부모의 전체 주소 공간을 자식에게 복사해야 하므로, 주소 공간이 클수록 프로세스 생성 비용이 매우 크다. 자식이 곧바로 exec()를 호출하는 경우에는 복사한 page가 전혀 사용되지 않아 더욱 낭비적이다.

COW를 사용하면 fork 직후 부모와 자식이 동일한 물리 page를 읽기 전용으로 공유한다. 이후 어느 쪽이 특정 page에 쓰기를 시도하면: ① protection fault 발생 → OS로 trap. ② OS는 해당 page를 복사하여 새 물리 frame에 넣고, 쓴 프로세스의 PTE를 새 frame으로 갱신. ③ 쓰기 명령을 재시작(restart).

결과적으로 실제로 수정된 page만 복사가 발생하여 불필요한 복사를 크게 줄이고 fork() 비용을 낮출 수 있다.

Q6 memory-mapped files의 개념과 동작 원리를 설명하고, 기존 파일 I/O(read()/write())와 비교하여 장단점을 서술하시오.

모범답안 보기

memory-mapped files는 mmap() 시스템 콜로 파일을 프로세스의 가상 주소 공간에 바인딩하는 기법이다. PTE가 가상 주소를 파일 데이터를 담은 물리 frame에 매핑하므로, 포인터 연산만으로 파일을 읽고 쓸 수 있다. 가상 주소 base + 오프셋 N = 파일의 N번째 바이트에 대응한다.

초기에는 모든 page가 invalid로 마킹. 접근 시 page fault가 발생하면 OS가 파일에서 해당 page를 읽어온다. 물리 메모리에서 내보낼 때 dirty이면 파일로 write-back하고, clean이면 단순 폐기한다.

장점: 파일과 메모리가 통일된 포인터 인터페이스로 접근 가능하고, 여러 프로세스가 동일 파일을 mmap하면 물리 page를 공유하여 복사 비용이 줄어든다. 단점: 프로세스가 데이터 이동 시점을 직접 제어하기 어렵고, 파이프·소켓 같은 streamed I/O에는 적용할 수 없다.

참고 mmap 영역의 backing store는 swap 공간이 아니라 매핑된 파일이다. 실제 파일과 연결되지 않은 익명 영역(anonymous VM)만 swap을 backing store로 사용한다.

Q7 NRU 알고리즘에서 4가지 page 클래스를 R bit와 M bit 기준으로 정의하고, 클래스 1(R=0, M=1)이 클래스 2(R=1, M=0)보다 교체 우선순위가 높은 이유를 설명하시오.

모범답안 보기

클래스 0: R=0, M=0 — 최근 미참조, 미수정. 교체 시 write-back 불필요. 최우선 victim.
클래스 1: R=0, M=1 — 최근 미참조, 수정됨. 교체 시 write-back 필요.
클래스 2: R=1, M=0 — 최근 참조, 미수정. 교체 시 write-back 불필요.
클래스 3: R=1, M=1 — 최근 참조, 수정됨. 최하위 교체 대상.

클래스 1은 최근에 참조되지 않았으므로(R=0) 앞으로도 가까운 미래에 참조될 가능성이 낮다. 반면 클래스 2는 최근에 참조되었으므로(R=1) 곧 다시 참조될 가능성이 높다. 교체 후 write-back 비용은 클래스 1이 더 크지만, 참조될 가능성이 낮은 page를 선택하는 것이 메모리 효율 면에서 더 중요하다. 따라서 NRU는 수정된 비참조 page(클래스 1)를 참조된 깨끗한 page(클래스 2)보다 먼저 교체한다.

Q8 PFF (page-fault frequency)와 working set model은 모두 thrashing을 방지하기 위한 정책이다. 두 방법의 작동 방식 차이를 비교하고 각각의 장단점을 서술하시오.

모범답안 보기

Working set model은 프로세스가 최근 w회의 참조 동안 접근한 page 집합(WS)을 유지하고, 모든 프로세스의 WSS 합이 총 frame을 초과하지 않도록 다중프로그래밍 수준을 제어한다. locality에 기반한 선제적(proactive) 접근이다. 단점은 정확한 WS를 추적하기 위한 오버헤드가 크고, 적절한 w 값을 결정하기가 어렵다는 점이다.

PFF는 각 프로세스의 실제 page fault율을 측정하여 상한·하한과 비교하는 반응적(reactive) 방식이다. fault율이 높으면 frame을 추가하고, 낮으면 회수한다. 구현이 단순하고 실시간 피드백에 기반하지만, FIFO의 Belady's anomaly처럼 frame을 추가해도 fault율이 줄지 않는 예외적 상황이 존재한다.

두 방법 모두 여유 frame이 전혀 없으면 프로세스를 일시 정지(suspend)하여 메모리를 확보하는 전략을 공유한다.