페이지 교체 알고리즘
물리 메모리가 가득 찼을 때, 어떤 페이지를 쫓아낼지 결정하는 알고리즘
주요 알고리즘
| 알고리즘 | 기준 | 특징 |
|---|
| 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 |