Optimal 페이지 교체 (OPT/MIN)

핵심 개념

Optimal 페이지 교체(OPT/MIN)는 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 알고리즘이다. 이론적으로 가장 낮은 페이지 폴트율을 보장하지만, 미래의 메모리 참조 순서를 알아야 하므로 실제 구현은 불가능하다. 다른 알고리즘의 성능을 비교하는 기준점(benchmark)으로만 사용된다.

비유하면, 냉장고에 새 음식을 넣을 때 가장 나중에 먹을 음식을 빼는 것이다 — 미래 식단을 안다면.

동작 원리

1. 페이지 교체가 필요할 때 현재 메모리에 있는 모든 페이지 검사
2. 각 페이지가 다음에 언제 참조될지 확인
3. 가장 늦게 참조될 페이지(또는 다시 참조되지 않을 페이지)를 victim으로 선택

왜 구현 불가능한가?

• 프로그램 실행 전에 모든 메모리 참조를 알 수 없음
• 동적 입력, 조건 분기 등으로 참조 패턴이 런타임에 결정됨
• SJF 스케줄링과 유사한 문제 — 미래 정보 필요

Stack Algorithm 특성

OPT는 스택 알고리즘에 속한다. n 프레임일 때 메모리에 있는 페이지 집합이 n+1 프레임일 때 집합의 부분집합이므로, 프레임 수 증가 시 페이지 폴트 수가 절대 증가하지 않는다 (Belady’s anomaly 없음).

예시

Reference string = 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1, 3 프레임:

참조: 7  0  1  2  0  3  0  4  2  3  0  3  2  1  2  0  1  7  0  1
f0:  7  7  7  2  2  2  2  2  2  2  2  2  2  2  2  2  2  7  7  7
f1:     0  0  0  0  0  0  4  4  4  0  0  0  0  0  0  0  0  0  0
f2:        1  1  1  3  3  3  3  3  3  3  3  1  1  1  1  1  1  1
폴트: F  F  F  F     F     F        F        F           F

총 9번의 페이지 폴트 (FIFO의 15번보다 훨씬 적음)

교체 결정 예시 — 참조 2 시점 (메모리에 7, 0, 1):

• 7: 다음 참조 = 18번째 (가장 멀리) → 교체 대상
• 0: 다음 참조 = 5번째
• 1: 다음 참조 = 14번째

관련 개념

• 페이지 교체 (Page Replacement) - 페이지 교체의 일반 개념
• FIFO 페이지 교체 - 가장 오래된 페이지를 교체하는 알고리즘
• LRU 페이지 교체 - OPT를 과거 정보로 근사하는 알고리즘