페이지 교체 평가

페이지 교체 비교

페이지 교체 알고리즘은 빈 프레임이 없을 때 어떤 페이지를 내보낼지 정합니다. 최적 알고리즘은 비교 기준일 뿐 실제 구현은 참조 정보의 근사, 하드웨어 지원, dirty page 비용을 함께 봐야 합니다.

01

참조 문자열 검토

페이지 접근 순서를 기준으로 각 알고리즘이 언제 fault를 내는지 비교합니다.

trace
02

희생 페이지 선택

FIFO는 오래 들어온 순서, LRU는 오래 안 쓴 순서, Clock은 reference bit로 근사합니다.

victim
03

쓰기 비용을 반영한다

dirty page를 내보내면 디스크 쓰기가 필요하므로 깨끗한 페이지와 비용이 다릅니다.

dirty
04

근사 정확도 비교

LRU에 가까울수록 결함률은 좋아질 수 있지만 추적 비용이 커질 수 있습니다.

tradeoff
FIFO
구현이 쉽지만 오래된 페이지가 곧 쓰일 수 있음 Belady anomaly처럼 프레임을 늘려도 fault가 늘 수 있는 예가 있습니다.
simple
LRU
최근 사용 이력으로 미래 사용을 근사 정확한 구현은 비용이 커서 하드웨어 bit나 clock으로 근사합니다.
locality
Clock
reference bit로 LRU를 저비용 근사 원형 포인터를 돌며 두 번째 기회를 주는 방식입니다.
practical

비교 기준 · 지역성 · 작업 집합 점검

교체 알고리즘 비교 fault 수만 보지 말고 dirty write와 메타데이터 유지 비용도 봅니다.
지역성 LRU 계열이 유리한 이유는 프로그램의 시간 지역성 때문입니다.
작업 집합 교체 알고리즘보다 메모리 할당량 부족이 더 큰 원인일 수 있습니다.