OPT (최적 페이지 교체) 편집하기

OPT(Optimal Page Replacement, 최적 페이지 교체 알고리즘)은 이론적으로 가장 효율적인 [[페이지 교체 알고리즘]]으로, 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체 대상으로 선택한다. 실제로 구현할 수는 없지만, 다른 알고리즘들의 성능을 비교하는 기준으로 사용된다.
==개념==
OPT는 다음과 같은 원칙에 따라 동작한다:
*페이지 폴트가 발생했을 때, 메모리에 있는 페이지들 중
*'''가장 늦게 다시 사용될 페이지'''를 제거한다
이 알고리즘은 모든 미래 접근 정보를 알고 있어야 하므로 현실적인 운영체제에서는 사용할 수 없으며, 시뮬레이션 및 성능 평가 목적에 주로 사용된다.
==동작 방식==
#페이지 요청이 발생함
#*메모리에 존재하면 히트
#*존재하지 않으면 페이지 폴트 발생
#페이지 프레임이 가득 찼다면:
#*향후 가장 오랫동안 참조되지 않을 페이지를 교체
==예시==
페이지 요청 순서: 7, 0, 1, 2, 0, 3, 0, 4  페이지 프레임 수: 3

동작:
#7 → [7]
#0 → [7, 0]
#1 → [7, 0, 1]
#2 → [0, 1, 2] (7은 앞으로 사용되지 않음 → 제거)
#0 → [0, 1, 2] (히트)
#3 → [0, 2, 3] (1은 가장 늦게 참조됨 → 제거)
#0 → [0, 2, 3] (히트)
#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
[[분류:운영체제]]