페이지 교체 알고리즘은 물리 메모리가 부족할 때 기존 페이지 중 회수할 대상을 정해 새 페이지가 사용할 프레임을 확보하는 과정입니다. 다시 사용할 가능성이 낮은 페이지를 골라 페이지 부개(Page Fault)와 I/O 비용을 줄이는 것이 목적입니다.
NOTE
페이지 부재가 났는데 빈 프레임이 없으면, RAM에 있는 페이지 하나를 보조기억장치로 내보내고(swap-out) 그 자리에 필요한 페이지를 가져옵니다(swap-in). 이때 “어떤 페이지를 내보낼 것인가?”를 결정하는 규칙이 바로 페이지 교체 알고리즘입니다.
- OPT - Optimal : 앞으로 가장 오랫동안 사용되지 않을 페이지 교체
- FIFO - First In First Out: 선입선출, 가장 먼저 들어온 페이지를 가장 먼저 교체
- LRU - Least Recently Used : 가장 오랫동안 사용되지 않은 페이지 교체
- LFU - Least Frequently Used : 참조 횟수가 가장 작은 페이지 교체
- MFU - Most Frequently used : 참조 횟수가 가장 많은 페이지 교체
- NUR - Not Used Recently : 최근에 사용하지 않은 페이지 교체
FIFO (First In First Out)
- 장점: 구현이 매우 간단합니다.
- 단점: 자주 사용되는 페이지임에도 불구하고 먼저 들어왔다는 이유만으로 교체될 수 있어 비효율적일 수 있습니다. (이를 Belady의 모순(Belady’s Anomaly) 이라고도 합니다. 프레임 수를 늘렸는데도 페이지 부재가 더 많이 발생하는 현상)
LRU (Least Recently Used)
- 장점: FIFO에 비해 페이지 부재율이 낮고, 일반적으로 좋은 성능을 보입니다.
- 단점: 각 페이지의 최근 사용 시간을 기록하고 유지해야 하므로, 운영체제의 부담이 크고 구현이 복잡합니다.
LFU (Least Frequently Used)
참조 횟수가 가장 적은 페이지를 교체하는 알고리즘입니다. “과거에 많이 사용된 페이지는 앞으로도 많이 사용될 것이다”라는 가정에 기반합니다.
- 장점: LRU가 잡아내지 못하는 장기적인 참조 패턴을 고려할 수 있습니다.
- 단점:
- 참조 횟수를 계산하기 위한 오버헤드가 큽니다.
- 초기에 많이 사용되었지만 더 이상 사용되지 않는 페이지가 계속 메모리에 남아있을 수 있습니다.
- 참조 횟수가 동일한 페이지가 여러 개일 경우, 어떤 것을 교체할지 결정하기 위한 추가적인 규칙(e.g., FIFO)이 필요합니다.
