어떤 페이지를 내릴지 고르는 기준도 지역성입니다. 앞으로 가장 늦게 쓰일 것을 내리는 것이 최적이지만 미래를 모르므로, 과거를 근거로 추정합니다.
페이지 교체 알고리즘
물리 메모리가 가득 찼을 때, 어떤 페이지를 쫓아낼지 결정하는 알고리즘
주요 알고리즘
| 알고리즘 | 기준 | 특징 |
|---|---|---|
| FIFO | 먼저 들어온 것 | 단순, Belady 이상 |
| LRU | 가장 오래 안 쓴 것 | 성능 좋음, 구현 비용 |
| LFU | 가장 적게 쓴 것 | 빈도 기반 |
| Clock | LRU 근사 | 실무 사용 |
| OPT | 미래에 가장 늦게 쓸 것 | 이론적 최적 (구현 불가) |
FIFO (First In First Out)
프레임 3개, 참조: 1 2 3 4 1 2 5
[1] → [1]
[1,2] → [1,2]
[1,2,3] → [1,2,3]
4 → 1 교체 → [4,2,3] 폴트!
1 → 2 교체 → [4,1,3] 폴트!
2 → 3 교체 → [4,1,2] 폴트!
5 → 4 교체 → [5,1,2] 폴트!
Belady 이상: 프레임 늘려도 폴트 증가 가능!
LRU (Least Recently Used)
프레임 3개, 참조: 1 2 3 4 1 2 5
[1] → [1]
[1,2] → [1,2]
[1,2,3] → [1,2,3]
4 → 1이 가장 오래 전 → [4,2,3] 폴트
1 → 2가 가장 오래 전 → [4,1,3] 폴트
2 → 3이 가장 오래 전 → [4,1,2] 폴트
5 → 4가 가장 오래 전 → [5,1,2] 폴트
FIFO보다 일반적으로 성능 좋음
Clock 알고리즘 (Second Chance)
원형 버퍼 + 참조 비트
→ [1:1] → [2:1] → [3:0] → [4:1]
↑ 시계 바늘
교체 시:
1. 참조 비트 1 → 0으로 바꾸고 넘어감
2. 참조 비트 0 → 이 페이지 교체!
LRU 근사 + 오버헤드 적음
→ 실제 OS에서 많이 사용
비교
| 기준 | FIFO | LRU | Clock |
|---|---|---|---|
| 구현 | 쉬움 | 복잡 | 중간 |
| 성능 | 보통 | 좋음 | 좋음 |
| 오버헤드 | 낮음 | 높음 | 낮음 |
| Belady | 있음 | 없음 | 없음 |
| 실무 | 드묾 | Redis 등 | Linux |