Page Replacement Policy

Page Replacement Policy란?

• 시스템에서 새 페이지를 로드하려고 하는데 가용메모리가 부족할 때 어떤 페이지를 메모리에서 제거할지 결정하는 정책 또는 알고리즘이다.
• 주요 목적은 Cache miss를 최소화 하여 메모리 사용 효율성을 높이고, 프로세스 실행 속도를 최적화하는 것이다.

Cache는 CPU안의 메모리인데 왜 나왔을까?

Cache는 main memory보다 빠른 메모리지만 중간 단계의 메모리가 위와 아래의 Cache 역할을 한다고 할때도 쓰인다. 즉, main memory는 하드 디스크의 cache 역할을 한다.

Page Replacement Policy 종류

FIFO (First In, First Out)

• 가장 오래전에 메모리에 로드된 페이지를 먼저 제거한다. 즉 들어온 순서대로 replace하는 방식이다.
• 구현이 간단하지만, 최근에 자주 사용되는 페이지를 제거할 수 있어 성능 문제가 발생할 수 있다. 이를 Belady의 이상현상이라고 부른다.

Belady의 이상현상?

캐시의 크기가 늘어났음에도 불구하고 캐시 miss가 오히려 늘어나는 현상

LRU (Least Recently Used)

• 최근에 가장 적게 사용된 페이지를 메모리에서 제거한다. 즉 마지막으로 사용시간이 가장 오래된 page를 replace한다.
• 자주 사용되는 페이지를 메모리에 유지하여 성능을 향상시킬 수 있지만, 구현이 복잡하고, 페이지 접근 기록을 유지하는 데 추가적인 비용이 발생한다. ->(시간 오버헤드, 공간 오버헤드가 크다 -> page가 언제 접근되었는지 모두 기록하고 있어야 함)

LFU (Least Frequently Used)

• 사용 빈도가 가장 낮은 페이지를 제거한다. 즉 잘 안쓰는 page를 replace한다.
• 빈번하게 사용되는 페이지를 메모리에 유지하지만, 초기에 자주 사용되다가 더 이상 사용되지 않는 페이지가 메모리에 남아있을 수 있다.

OPT (Optimal Page Replacement)

• 미래에 가장 오랫동안 사용되지 않을 페이지를 선택하여 제거한다.
• 이론적으로 최적의 성능을 제공하자만, 실제 시스템에서는 미래의 페이지 접근 정보를 알 수 없어 구현이 불가능하다.
• 다른 알고리즘의 성능을 비교하는 비교군으로 사용된다.

Clock (혹은 Second Chance Algorithm)

• FIFO 방식에 접근 비트를 추가하여 한 번의 기회를 더 부여한다. 접근된 페이지는 접근 비트가 설정되고, 페이지 교체 시 접근 비트가 설정된 페이지는 비트를 클리어하고 다시 기회를 준다.
• LRU의 근사 알고리즘으로 성능과 구현의 복잡성 사이에서 균형을 유지하지만, 완벽한 LRU의 성능을 모방하지는 못한다.

cold start : 시스템에서 캐시된 데이터가 없는 상태로 시작되는 경우를 의미.

이외의 다른 전략들

NRU (Not Recently Used)

• 페이지들을 최근 사용 여부에 따라 분류하고, 가장 최근에 사용되지 않은 페이지를 교체 대상으로 선택
• 구현이 간단하며, 실행 비용이 낮지만, 어떤 페이지가 가장 오래전에 사용되었는지는 고려하지 않는다.

ARC (Adaptive Replacement Cache)

• 최근에 사용된 페이지와 자주 사용되는 페이지의 두 가지 정보를 모두 활용하여 교체 대상을 결정.
• ARC는 LRU와 LFU의 장점을 합친 형태
• 다양한 워크로드에 대해 높은 성능을 보이지만, 구현 복잡도가 높고, 메모리와 CPU 사용량이 증가할 수 있다.

MQ (Multi-Queue)

• 여러 개의 큐를 사용하여 페이지들을 다양한 우선순위로 관리한다.
• 각 큐는 페이지들의 사용 빈도나 최근성에 따라 다른 우선순위를 가진다.
• 다양한 접근 패턴을 효과적으로 관리할 수 있지만, 여러 큐를 관리해야 하기 때문에 구현이 복잡하며, 메모리 사용량이 증가할 수 있다.

CAR (Clock with Adaptive Replacement)

• Clock 알고리즘과 ARC의 아이디어를 결합한 것으로, 접근 빈도와 최근성을 모두 고려한다.
• ARC의 핵심 아이디어를 단순화하고, Clock 알고리즘의 구조를 사용하여 효율적인 페이지 교체 정책을 구현한다.
• ARC의 이점을 유지하면서 구현과 실행 비용을 줄일 수 있다.
• ARC에 비해 약간의 성능 저하가 발생할 수 있으나, 실제 환경에서는 큰 차이가 없을 수 있다.

• 각 페이지 교체 정책은 시스템의 요구사항, 하드웨어의 특성, 그리고 특정 애플리케이션의 워크로드에 크게 의존하기 때문에 다르게 성능을 나타낸다.
• 모든 상황에 최적인 알고리즘은 없기 때문에. 결정은 시스템의 성능 목표, 메모리 사용량, 애플리케이션의 특성 등을 고려하여 선택해야한다.

출처
https://hyeo-noo.tistory.com/102#--%--Simple%--Policy%--%-A%--FIFO%---Queue-