페이지 교체 알고리즘 — FIFO, LRU, Clock, Working Set
물리 메모리가 부족하면 어떤 페이지를 내보낼지 결정해야 합니다. 이 결정이 시스템 성능에 직접 영향을 주고, 잘못하면 스래싱이 발생합니다.
페이지 교체가 필요한 상황
가상 메모리 시스템에서 페이지 폴트 가 발생했는데, 물리 메모리(프레임)가 모두 사용 중이면 기존 페이지 하나를 디스크로 내보내고(swap out) 새 페이지를 올려야 합니다. 이때 어떤 페이지를 내보낼지 결정하는 것이 페이지 교체 알고리즘입니다.
OPT (Optimal, 최적 교체)
앞으로 가장 오랫동안 사용되지 않을 페이지 를 교체합니다.
프레임 수: 3
참조 순서: 7 0 1 2 0 3 0 4
| 참조 | 프레임 상태 | 폴트 |
|------|-------------|------|
| 7 | [7, -, -] | O |
| 0 | [7, 0, -] | O |
| 1 | [7, 0, 1] | O |
| 2 | [2, 0, 1] | O (7을 교체: 7은 앞으로 안 쓰임) |
| 0 | [2, 0, 1] | |
| 3 | [2, 0, 3] | O (1을 교체: 1은 앞으로 안 쓰임) |
| 0 | [2, 0, 3] | |
| 4 | [4, 0, 3] | O (2를 교체) |
- 페이지 폴트 횟수가 이론적 최소
- 미래를 알아야 하므로 실제 구현 불가 — 다른 알고리즘의 성능 비교 기준으로 사용
FIFO (First In, First Out)
가장 먼저 들어온 페이지를 먼저 교체 합니다.
프레임 수: 3
참조 순서: 7 0 1 2 0 3 0 4
| 참조 | 프레임 상태 | 폴트 |
|------|-------------|------|
| 7 | [7, -, -] | O |
| 0 | [7, 0, -] | O |
| 1 | [7, 0, 1] | O |
| 2 | [2, 0, 1] | O (7이 가장 오래됨) |
| 0 | [2, 0, 1] | |
| 3 | [2, 3, 1] | O (0이 가장 오래됨) |
| 0 | [2, 3, 0] | O (1이 가장 오래됨) |
| 4 | [4, 3, 0] | O (2가 가장 오래됨) |
- 장점: 구현이 매우 간단 (큐)
- 단점: Belady's Anomaly — 프레임 수를 늘렸는데 오히려 폴트가 증가하는 현상
Belady's Anomaly
참조 순서: 1 2 3 4 1 2 5 1 2 3 4 5
3 프레임: 9번 폴트
4 프레임: 10번 폴트 ← 프레임이 많은데 더 나빠짐!
LRU (Least Recently Used)
가장 오랫동안 사용되지 않은 페이지를 교체 합니다. 과거 사용 패턴으로 미래를 예측합니다.
프레임 수: 3
참조 순서: 7 0 1 2 0 3 0 4
| 참조 | 프레임 상태 | 폴트 |
|------|-------------|------|
| 7 | [7, -, -] | O |
| 0 | [7, 0, -] | O |
| 1 | [7, 0, 1] | O |
| 2 | [2, 0, 1] | O (7이 가장 오래 안 쓰임) |
| 0 | [2, 0, 1] | |
| 3 | [2, 0, 3] | O (1이 가장 오래 안 쓰임) |
| 0 | [2, 0, 3] | |
| 4 | [4, 0, 3] | O (2가 가장 오래 안 쓰임) |
- 장점: OPT에 가장 가까운 성능, Belady's Anomaly 없음
- 단점: 구현 비용이 높음 — 매 참조마다 타임스탬프 갱신 또는 리스트 재정렬 필요
LRU 구현 방식
- 카운터 방식: 각 페이지에 마지막 접근 시간 기록 → 가장 작은 값 교체
- 스택 방식: 참조될 때마다 스택 맨 위로 이동 → 맨 아래가 LRU
- 이중 연결 리스트 + 해시맵: O(1) 접근, O(1) 갱신 — 가장 효율적
Clock 알고리즘 (Second-Chance)
LRU의 근사(approximation) 알고리즘 입니다. 실제 리눅스가 사용하는 방식의 기반입니다.
원형 큐로 페이지를 관리, 각 페이지에 참조 비트(Reference Bit) 부여
시계 바늘이 돌면서:
1. 참조 비트 = 1 → 비트를 0으로 리셋, 다음으로 이동 (한 번 더 기회)
2. 참조 비트 = 0 → 이 페이지를 교체!
┌── 참조비트:1 ──┐
│ │
참조비트:0 시계바늘→ 참조비트:1
│ │
└── 참조비트:0 ──┘
↑
이 페이지 교체!
- 장점: LRU보다 구현이 간단하면서 성능은 비슷
- FIFO + 참조 비트 = Clock
Enhanced Clock (NRU)
참조 비트(R)와 수정 비트(M) 두 개를 사용합니다.
| 클래스 | (R, M) | 우선순위 |
|---|---|---|
| 0 | (0, 0) | 가장 먼저 교체 |
| 1 | (0, 1) | |
| 2 | (1, 0) | |
| 3 | (1, 1) | 가장 나중에 교체 |
수정된 페이지는 디스크에 써야 하므로 비용이 더 큽니다.
Working Set 모델
특정 시간 동안 프로세스가 참조한 페이지의 집합 을 Working Set이라 합니다.
시간 윈도우 Δ = 5
참조 순서: ... 1 2 5 7 1 3 ...
↑ 현재
Working Set = {2, 5, 7, 1, 3} (최근 5번 참조한 페이지들)
- Working Set에 없는 페이지는 교체 후보
- Working Set 크기가 프레임 수보다 크면 → 스래싱(Thrashing) 발생 가능
- OS는 각 프로세스의 Working Set을 추적하여 충분한 프레임을 할당
알고리즘 비교 정리
| 알고리즘 | 교체 대상 | Belady's Anomaly | 성능 | 구현 복잡도 |
|---|---|---|---|---|
| OPT | 미래에 가장 늦게 쓸 페이지 | 없음 | 최적 (이론적) | 불가능 |
| FIFO | 가장 먼저 들어온 페이지 | 있음 | 나쁨 | 매우 쉬움 |
| LRU | 가장 오래 안 쓴 페이지 | 없음 | 좋음 | 어려움 |
| Clock | 참조 비트 0인 페이지 | 없음 | 좋음 | 보통 |
| Working Set | WS 밖의 페이지 | 없음 | 좋음 | 어려움 |
핵심 포인트
- LRU vs FIFO: FIFO는 Belady's Anomaly가 있지만 LRU는 없음. 이유는 LRU가 "스택 알고리즘"이기 때문
- 실제 OS가 순수 LRU를 안 쓰는 이유: 매 메모리 접근마다 타임스탬프 갱신은 너무 비쌈 → Clock(근사)
- 스래싱과 Working Set: 프로세스의 Working Set보다 적은 프레임을 주면 스래싱 → 페이지 폴트 폭증 → CPU 사용률 하락
정리
페이지 교체는 결국 "미래에 안 쓸 페이지를 예측" 하는 문제입니다. 완벽한 예측(OPT)은 불가능하므로, 과거 사용 패턴(LRU)이나 최근 참조 여부(Clock)를 기반으로 근사합니다. 각 알고리즘의 동작 과정을 예시와 함께 설명하고, Belady's Anomaly와 스래싱 개념을 연결 지을 수 있으면 좋습니다.