페이지 교체 알고리즘
요구 페이징을 사용하는 운영체제에서 새 페이지를 적재할 빈 프레임이 없을 때, 어떤 페이지를 내보낼지 결정하는 알고리즘입니다.
등장 배경
- 가상 메모리 기법은 프로그램의 일부만 물리 메모리에 적재해, 실제 물리 메모리보다 큰 프로세스도 실행할 수 있게 합니다.
- 필요한 시점에만 페이지를 메모리에 올리는 방식을 요구 페이징이라 하며, 페이지 폴트가 발생했는데 빈 프레임이 없다면 기존 페이지 중 하나를 내보내야 합니다.
- 이때 교체 대상을 정하는 기준이 페이지 교체 알고리즘입니다.
알고리즘 종류
| 알고리즘 | 설명 | 특징 |
|---|---|---|
| FIFO | 가장 먼저 적재된 페이지를 교체 | 단순하지만 Belady's Anomaly 발생 가능. 2차 기회 알고리즘 등 변형으로 개선 |
| OPT | 앞으로 가장 나중에 사용될 페이지를 교체 | 이론적 최적해. 미래 접근 패턴을 알 수 없어 실제 구현 불가 |
| LRU | 가장 오래 사용되지 않은 페이지를 교체 | OPT에 근접한 성능이지만 사용 시각을 추적해야 해 구현 비용이 높음 |
| LFU | 사용 빈도가 가장 낮은 페이지를 교체 | 빈도가 같으면 다른 알고리즘으로 보완 필요, 최근 적재된 페이지에 불리 |
| NUR | 최근에 참조된 적 없는 페이지를 교체 | LRU·LFU와 유사한 성능이면서 참조 비트·수정 비트만으로 판단해 오버헤드가 적음 |
OPT와 근사 알고리즘의 차이
OPT를 제외한 FIFO, LRU, LFU, NUR은 모두 과거의 데이터를 기반으로 미래의 메모리 접근 패턴을 예측하는 최적 근접 알고리즘입니다. OPT는 미래의 사용 패턴을 알아야 하므로 실제 시스템에는 적용할 수 없고, 다른 알고리즘의 성능을 비교하는 이론적 기준으로 활용됩니다.
핵심 정리
페이지 교체 알고리즘은 페이지 폴트 발생 시 빈 프레임이 없을 때 어떤 페이지를 내보낼지 정하는 기준이며, 실제 구현 가능한 FIFO·LRU·LFU·NUR과 이론적 최적해인 OPT로 나뉩니다.