OPT (최적 페이지 교체)

OPT(Optimal Page Replacement, 최적 페이지 교체 알고리즘)은 이론적으로 가장 효율적인 페이지 교체 알고리즘으로, 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체 대상으로 선택한다. 실제로 구현할 수는 없지만, 다른 알고리즘들의 성능을 비교하는 기준으로 사용된다.

개념

OPT는 다음과 같은 원칙에 따라 동작한다:

• 페이지 폴트가 발생했을 때, 메모리에 있는 페이지들 중
• 가장 늦게 다시 사용될 페이지를 제거한다

이 알고리즘은 모든 미래 접근 정보를 알고 있어야 하므로 현실적인 운영체제에서는 사용할 수 없으며, 시뮬레이션 및 성능 평가 목적에 주로 사용된다.

동작 방식

1. 페이지 요청이 발생함
   • 메모리에 존재하면 히트
   • 존재하지 않으면 페이지 폴트 발생
2. 페이지 프레임이 가득 찼다면:
   • 향후 가장 오랫동안 참조되지 않을 페이지를 교체

예시

페이지 요청 순서: 7, 0, 1, 2, 0, 3, 0, 4 페이지 프레임 수: 3

동작:

1. 7 → [7]
2. 0 → [7, 0]
3. 1 → [7, 0, 1]
4. 2 → [0, 1, 2] (7은 앞으로 사용되지 않음 → 제거)
5. 0 → [0, 1, 2] (히트)
6. 3 → [0, 2, 3] (1은 가장 늦게 참조됨 → 제거)
7. 0 → [0, 2, 3] (히트)
8. 4 → [0, 3, 4] (2 제거)

→ 페이지 폴트: 6회

장점

• 이론상 가장 적은 페이지 폴트를 유도
• 다른 알고리즘과 비교할 때 기준선 역할

단점

• 실제 미래의 참조 패턴을 미리 알 수 없으므로 현실에서 사용 불가
• 시뮬레이션 용도 외에는 제한적

활용

• LRU, FIFO, LFU 등 실제 알고리즘 성능 비교 기준
• 운영체제 교육 및 이론적 분석에서 자주 등장

같이 보기

• 페이지 교체 알고리즘
• LRU (페이지 교체 알고리즘)
• FIFO (페이지 교체 알고리즘)
• LFU (페이지 교체 알고리즘)
• 가상 메모리
• 페이지 폴트

참고 문헌

• Silberschatz, A., Galvin, P. B., & Gagne, G. (2020). Operating System Concepts. Wiley
• Tanenbaum, A. S., & Bos, H. (2014). Modern Operating Systems. Pearson