3. 페이지 교체 알고리즘(FIFO, LRU, OPT, LFU)의 단점과 해결 방법
1. FIFO (First In First Out) - 선입선출
✅ 단점
- 오래된 페이지가 먼저 제거되므로, 자주 사용되는 페이지도 제거될 가능성이 있음
- Belady's Anomaly(벨라디의 역설) 발생 가능
* 일반적으로 페이지 프레임 개수가 증가하면 페이지 폴트가 감소해야 하지만, FIFO에서는 오히려 페이지 폴트가 증가할 수도 있음
* 오래된 페이지를 무조건 제거하기 때문에, 최근 자주 사용된 페이지라도 교체될 수 있음
✅ 해결 방법
✔️ Second Chance (Clock Algorithm) 적용
- FIFO 방식에서 페이지를 제거하기 전에 한 번 더 기회를 줌
- 페이지에 **참조 비트(Reference Bit)**를 추가해서,
* 참조 비트가 1이면: 페이지를 교체하지 않고, 비트를 0으로 바꿔서 다시 대기열로 이동
* 참조 비트가 0이면: 페이지 교체 수행
- FIFO의 단순한 구조를 유지하면서도 자주 사용되는 페이지를 보호할 수 있음
2. LRU (Least Recently Used) - 가장 오랫동안 사용되지 않은 페이지 교체
✅ 단점
- 최근 사용된 페이지를 반영할 수 있지만, 구현 비용이 높음
- 페이지 사용 기록을 저장해야 하므로, 추가적인 메모리 및 CPU 오버헤드가 발생
- 사용 기록을 저장하는 방법:
* 카운터 기반 → 각 페이지의 마지막 사용 시간을 저장해야 함
* 스택 기반 → 페이지가 참조될 때마다 정렬해야 함
✅ 해결 방법
✔️ LRU Approximation (LRU 근사 알고리즘) 사용
- 참조 비트(Reference Bit) 또는 페이지 접근 히스토리를 사용하여 완벽한 LRU 대신 근사적인 방법을 사용
- Clock Algorithm: FIFO + LRU 혼합 방식 (Second Chance 알고리즘과 유사)
- NFU (Not Frequently Used) 알고리즘: LRU처럼 최근 사용 기록을 반영하지만, 계산을 단순하게 만듦
✔️ LRU-K 알고리즘
- 최근 K번 참조된 시점을 기준으로 교체할 페이지를 결정 (예: LRU-2는 최근 2번 참조된 시간을 기준으로 판단)
- 장점: 단순 LRU보다 짧은 기간 동안만 많이 사용된 페이지가 유지되는 문제를 해결 가능
3. OPT (Optimal Page Replacement) - 가장 오랫동안 사용되지 않을 페이지 교체
✅ 단점
- 실제 시스템에서는 구현할 수 없음 (미래를 예측해야 함)
- 가장 적은 페이지 폴트를 발생시키는 이상적인 방법이지만, 실제 운영체제에서는 OPT 방식으로 동작할 수 없음
✅ 해결 방법
✔️ LRU 또는 LFU를 대체 알고리즘으로 사용
- OPT는 현실적으로 불가능하므로, 최근 사용 기록을 바탕으로 OPT에 가까운 성능을 내는 알고리즘(LRU, LFU 등)을 사용
- 예를 들어, LPU-K는 최근 K번 참조된 기록을 기준으로 페이지를 교체하여 OPT에 가까운 성능을 낼 수 있음
4. LFU (Least Frequently Used) - 사용 빈도가 가장 적은 페이지 교체
✅ 단점
- 최근에 사용된 페이지라도, 과거에 사용 빈도가 적다면 제거될 가능성이 있음
* 예: 처음 등장한 페이지는 무조건 1회 사용 → 바로 제거될 가능성이 큼
- 오래된 페이지가 계속 유지될 수도 있음
* 한 번 많이 사용된 페이지가 계속 남아 있어서, 최근 자주 사용되는 페이지가 제거될 수도 있음
✅ 해결 방법
✔️ LFU + Aging (가중치 감소 적용)
- 시간이 지날수록 과거의 사용 횟수 가중치를 줄이는 방식
- 예를 들어, 일정 시간마다 모든 페이지의 사용 횟수를 절반으로 줄이면, 오래된 페이지가 계속 유지되는 문제를 해결 가능
✔️ Adaptive LFU (적응형 LFU) 사용
- LRU와 혼합해서 최근 사용 패턴을 반영하도록 개선
- 예를 들어, 최근 K번의 참조 횟수만 고려하는 LFU-K 알고리즘을 사용하면, LFU의 단점(오래된 데이터 유지)을 해결할 수 있음
✅결론
| 알고리즘 | 단점 | 해결 방법 |
| FIFO | 오래된 페이지라도 무조건 제거됨 (Belady's Anomaly 발생 가능) | Second Chance (Clock Algorithm) 사용 |
| LRU | 사용 기록 저장 오버헤드 큼 | LRU Approximation (Clock Algorithm, NFU, LRU-K) 사용 |
| OPT | 미래를 예측해야 하므로 구현 불가능 | LRU-K, LFU 등 현실적인 대안 사용 |
| LFU | 최근 사용된 페이지라도 과거에 사용 횟수가 적으면 제거될 가능성 | Aging 적용, LFU-K 사용하여 최신 패턴 반영 |