페이지 교체 정책(Page Replacement Policy)
페이지 교체 정책은 요구 페이징 시스템에서 물리 메모리가 가득 찬 경우, 새로운 페이지를 적재하기 위해 기존 페이지 중 어느 것을 제거할지 결정하는 알고리즘이다.
FIFO (First-In, First-Out)
개념
- 가장 먼저 메모리에 적재된 페이지를 가장 먼저 교체하는 방식.
- 큐(Queue)를 사용하여 페이지를 관리.
장점
- 구현이 단순하며, 시간 순서에 따라 처리하기 쉽다.
단점
- Belady's Anomaly: 프레임 수가 증가해도 페이지 폴트가 감소하지 않는 현상이 발생할 수 있다.
- 오래된 페이지가 꼭 덜 사용된 페이지는 아닐 수 있다.
OPT (Optimal Page Replacement)
개념
- 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 방식.
- 이론적으로 가장 효율적인 알고리즘으로, 페이지 폴트 수를 최적화.
장점
- 최적의 성능(최소 페이지 폴트).
단점
- 미래의 페이지 접근 패턴을 미리 알아야 하므로 현실적으로 구현이 불가능.
- 주로 비교 기준으로 사용됨.
LRU (Least Recently Used)
개념
- 가장 오랫동안 사용되지 않은 페이지를 교체.
- 과거 접근 기록을 기반으로 페이지 교체를 결정.
장점
- OPT에 근접한 성능을 제공하며, 현실적으로 구현 가능.
단점
- 오버헤드: 각 페이지의 최근 사용 시간을 저장하거나 갱신해야 하므로 구현 비용이 높다.
- 자주 갱신되는 데이터 구조가 필요(예: 스택, 해시맵 등).
LFU (Least Frequently Used)
개념
- 사용 빈도가 가장 적은 페이지를 교체.
- 페이지가 메모리에 머누는 동안 참조된 횟수를 기준으로 판단.
장점
- 사용 빈도가 낮은 페이지를 제거하여 페이지 교체 효율성을 높임.
단점
- 최근에 참조된 페이지가 사용 빈도가 낮을 경우 부적절한 교체가 발생할 수 있음.
- 오래된 페이지가 높은 참조 횟수를 유지할 수 있어 잘못된 판단 가능(이를 개선한 LFU 변형 알고리즘도 존재).
NUR (Not Recently Used)
개념
- 하드웨어가 제공하는 참조 비트(Reference Bit)와 변경 비트(Dirty Bity)를 사용하여 페이지 교체를 결정.
- 참조 비트와 변경 비트로 페이지를 4가지 그룹으로 분류:
- (0, 0): 최근에 참조되지 않았으며 변경되지 않음(최우선 제거)
- (0, 1): 최근에 참조되지 않았지만 변경됨
- (1, 0): 최근에 참조되었지만 변경되지 않음
- (1, 1): 최근에 참조되었으며 변경됨(제거 우선순위 낮음)
장점
- 구현이 비교적 간단하며, 하드웨어 지원이 있는 경우 효율적.
단점
- 참조 및 변경 비트가 시간 경과에 따른 사용 패턴을 완벽히 반영하지 못할 수 있음.
정리
- FIFO: 가장 단순한 방식(오래된 페이지를 제거).
- OPT: 이론적으로 최적(미래를 알아야 함).
- LRU: 최근 사용되지 않은 페이지 교체(효율적이지만 구현 비용 높음).
- LFU: 사용 빈도가 낮은 페이지 교체(참조 횟수 기반).
- NUR: 참조/변경 비트를 사용하여 교체(단순하고 효율적).
Thrashing (스레싱)
개념
- 과도한 페이지 폴트로 인해 CPU 시간이 거의 모두 페이지 교체 처리에 소비되는 상태.
- 프로세스가 필요한 페이지를 계속 디스크에서 로드해야 하는 상황이 반복됨.
원인
- 물리 메모리가 부족하여 한 프로세스에 필요한 최소 페이지 수를 유지할 수 없을 때 발생.
- 다수의 프로세스가 동시에 실행되면서 메모리 경쟁이 심해질 때.
결과
- 시스템 성능이 급격히 저하되며, 처리량이 거의 0에 가까워짐.
해결 방안
- 워크셋(Working Set) 정책: 프로세스가 자주 참조하는 페이지 집합(워크셋)을 메모리에 유지하여 스레싱 방지.
- 다단계 큐(Multi-Level Queue) 사용: 프로세스 우선순위를 기반으로 메모리 자원을 배분.
- 적응형 페이지 교체: 페이지 폴트율을 기반으로 메모리 할당 크기를 동적으로 조정.
Turning Vision into Reality.