OPT
OPT(Optimal Page Replacement, 최적 페이지 교체)는 가상 메모리 시스템에서 페이지 폴트가 발생했을 때, 가장 먼 미래에 사용될 페이지를 교체하는 페이지 교체 알고리즘이다. 이름 그대로 이론적으로 가장 좋은 결과를 내지만, 미래를 알아야 한다는 한계가 있어 실제 시스템에서는 사용할 수 없다.
동작 방식
페이지 폴트 발생 → 메모리에 적재된 페이지 중 앞으로 가장 오랫동안 참조되지 않을 페이지를 선택해 교체한다.
왜 사용 불가한가
미래에 어떤 페이지가 어떤 순서로 참조될지 사전에 알 수 없다. 따라서 OPT는 실제 시스템이 아닌 다른 알고리즘의 성능을 비교하는 기준점으로만 쓰인다.
다른 페이지 교체 알고리즘과의 비교
| 알고리즘 | 기준 | 특징 |
|---|---|---|
| OPT | 앞으로 가장 늦게 쓰일 페이지 | 이론상 최적, 구현 불가 |
| FIFO | 가장 먼저 들어온 페이지 | 단순, Belady 변칙 발생 |
| LRU | 가장 오래 사용 안 한 페이지 | 시간 지역성 활용 |
| NUR | 최근 사용 안 한 페이지 | LRU의 근사치 |
| LFU | 사용 빈도 낮은 페이지 | 빈도 지역성 활용 |
활용
- 벤치마크 기준: 새 알고리즘이 OPT에 얼마나 가까운지로 평가
- 교육 목적: 페이지 교체의 본질을 이해하기 위한 출발점