페이지 교체 알고리즘은 물리 메모리가 가득 찼을 때 어떤 페이지를 내보낼지 결정하는 정책이다. 교체 결정은 페이지 폴트 수를 최소화하는 방향으로 이루어지며, OPT(최적 알고리즘)가 이론적 기준이 된다.
주요 알고리즘
OPT (Optimal)
미래에 가장 오래 사용되지 않을 페이지 교체. 이론적으로만 가능.
FIFO
python
from collections import deque
def fifo(references, n_frames):
frames = deque(maxlen=n_frames)
frame_set = set()
faults = 0
for page in references:
if page not in frame_set:
faults += 1
if len(frames) == n_frames:
old = frames.popleft()
frame_set.remove(old)
frames.append(page)
frame_set.add(page)
return faults
LRU (Least Recently Used)
python
from collections import OrderedDict
def lru(references, n_frames):
cache = OrderedDict()
faults = 0
for page in references:
if page in cache:
cache.move_to_end(page)
else:
faults += 1
if len(cache) == n_frames:
cache.popitem(last=False)
cache[page] = True
return faults
Clock (NRU 근사)
원형 버퍼에 참조 비트(R) 관리
R=1: 0으로 초기화 후 통과
R=0: 해당 페이지 교체
성능 비교
| 알고리즘 | 폴트 수 | 구현 난이도 | 실용성 |
|---|
| OPT | 최소 | 불가 | 기준점 |
| LRU | 낮음 | 높음 | 높음 |
| Clock | 낮음 | 중간 | 높음 |
| FIFO | 높음 | 낮음 | 낮음 |
관련 개념
