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

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

물리 메모리(프레임)가 모두 사용 중일 때 새로운 페이지를 적재하기 위해 교체할 희생 페이지를 선택하는 알고리즘

목적: 페이지 폴트율 최소화, 메모리 활용 효율 극대화, 시스템 성능 유지

특징: 참조 비트/수정 비트 활용, 지역성(Locality) 기반, 오버헤드-성능 트레이드오프

알고리즘 유형

• •OPT(Optimal/Belady): 가장 오랫동안 사용되지 않을 페이지 교체, 이론적 최적(구현 불가), 성능 비교 기준
• •FIFO(First-In First-Out): 가장 먼저 적재된 페이지 교체, 단순, Belady의 모순(프레임 증가 시 폴트 증가) 발생 가능
• •LRU(Least Recently Used): 가장 오랫동안 참조되지 않은 페이지 교체, OPT 근사, 구현 비용 높음(타임스탬프/스택)
• •LFU(Least Frequently Used): 참조 횟수가 가장 적은 페이지 교체, 빈도 기반, 초기 집중 사용 후 미사용 페이지 잔류 문제
• •Clock(Second Chance): 참조 비트 기반 원형 큐, FIFO 개선, 참조 비트 1이면 0으로 리셋 후 통과, 0이면 교체
• •Enhanced Clock(NRU): (참조비트, 수정비트) 쌍으로 4등급 분류, (0,0)→(0,1)→(1,0)→(1,1) 순 교체 우선

Belady의 모순: FIFO에서 프레임 수 증가 시 오히려 페이지 폴트 증가하는 역설, LRU/OPT에서는 발생하지 않음(스택 알고리즘)

워킹 셋 (Working Set): 일정 시간 창(Δ) 내 참조된 페이지 집합, 프로세스별 적정 프레임 수 결정, 스레싱 방지

PFF (Page Fault Frequency): 페이지 폴트율 상한/하한 설정, 상한 초과 시 프레임 추가, 하한 미달 시 프레임 회수

장점: 메모리 효율적 관리, 멀티프로그래밍 지원, 프로세스 격리

단점: 알고리즘 오버헤드, 페이지 폴트 시 디스크 I/O 지연(ms 단위)

적용사례: Linux(Clock 변형/PFRA), Windows(Working Set), 데이터베이스 버퍼 관리

비교: OPT(최적/불가능) vs LRU(시간기반/근사최적) vs FIFO(순서기반/단순/Belady모순) vs Clock(참조비트/효율적)

연관: 가상 메모리, 페이지 폴트, 스레싱, 워킹 셋, 지역성