토픽 44 / 85·메모리 관리

페이지 교체 알고리즘 (Page Replacement Algorithm)

메모리가 가득 찬 상태에서 페이지 폴트 발생 시 어떤 페이지를 제거할지 결정하는 알고리즘

목적: 페이지 폴트 최소화, 성능 최적화, 스래싱 방지

특징: 지역성 활용, 과거 참조 기반, 트레이드오프

주요 알고리즘

•FIFO(First-In, First-Out): 가장 오래된 페이지 교체, 단순, Belady's Anomaly(프레임 증가 시 페이지 폴트 증가)
•Optimal(OPT): 가장 나중에 사용될 페이지 교체, 이론적 최적, 미래 예측 불가능(비현실적)
•LRU(Least Recently Used): 가장 오래 사용 안된 페이지 교체, 지역성 활용, 실용적, 구현 비용(스택/카운터)
•LFU(Least Frequently Used): 참조 횟수 적은 페이지 교체, 초기 참조 많으면 오래 유지
•Clock(Second Chance): FIFO + Reference 비트, 순환 리스트, LRU 근사, 효율적, Linux/Windows
•MRU(Most Recently Used): 특정 패턴(순차 접근)에서 유리

Reference/Dirty 비트: Reference(R) - 참조 여부, Dirty(D) - 수정 여부, Clock 알고리즘 활용

성능 비교: Optimal(최적) ≈ LRU > Clock > FIFO

Belady's Anomaly: FIFO에서 프레임 증가 시 페이지 폴트 증가하는 역설, LRU는 해당 없음

적용사례: Linux(Clock + LRU), Windows(Clock), 데이터베이스 버퍼 풀

비교: LRU(실용적/비용) vs FIFO(단순/Anomaly) vs Clock(효율/근사) vs Optimal(이론)

연관: 가상 메모리, 페이징, 페이지 폴트, 지역성, Clock