[운영체제] 페이지 교체 알고리즘

가상 메모리 시스템에서 페이지 부재(Page Fault)가 발생했을 때, 새로운 페이지를 메모리에 불러오기 위해 어떤 페이지를 제거할지 결정하는 방법입니다. 페이지 교체 알고리즘은 메모리 효율성을 극대화하고 페이지 부재를 최소화하는 것이 목표입니다.

주요 페이지 교체 알고리즘

1. FIFO (First-In, First-Out) 알고리즘
   • 개념: 가장 먼저 메모리에 들어온 페이지를 가장 먼저 제거하는 방식입니다.
   • 특징:
     • 구현이 단순하고, 큐를 사용하여 페이지를 관리합니다.
     • **Belady의 모순(Belady’s Anomaly)**이 발생할 수 있습니다. 즉, 프레임 수가 증가해도 페이지 부재가 줄어들지 않고 오히려 증가할 수 있습니다.
2. OPT (Optimal Page Replacement) 알고리즘
   • 개념: 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 방식입니다.
   • 특징:
     • 이론적으로 가장 적은 페이지 부재를 보장하는 이상적인 알고리즘입니다.
     • 실제로는 앞으로의 페이지 요청을 예측할 수 없으므로, 주로 성능 비교의 기준으로 사용됩니다.
3. LRU (Least Recently Used) 알고리즘
   • 개념: 가장 최근에 사용되지 않은 페이지를 교체하는 방식입니다.
   • 특징:
     • 페이지의 사용 패턴을 기반으로 교체할 페이지를 결정하여, 실질적인 성능이 좋습니다.
     • 최근 사용 시간을 추적해야 하므로 추가적인 메모리와 오버헤드가 발생합니다.
   • 구현 방법:
     • 카운터 기반: 각 페이지에 시간 스탬프를 부여해 가장 오랫동안 사용되지 않은 페이지를 교체.
     • 스택 기반: 페이지가 참조될 때마다 스택의 가장 위로 이동시키고, 스택의 맨 아래에 위치한 페이지를 교체.
4. LFU (Least Frequently Used) 알고리즘
   • 개념: 사용 빈도가 가장 낮은 페이지를 교체하는 방식입니다.
   • 특징:
     • 페이지의 참조 횟수를 추적하여, 자주 사용되지 않는 페이지를 제거함으로써 페이지 부재를 줄입니다.
     • 최근에 사용된 페이지라 하더라도 참조 횟수가 적으면 교체될 수 있음. LRU에 비해 오랜 시간 동안의 사용 패턴을 반영합니다.
5. MFU (Most Frequently Used) 알고리즘
   • 개념: 사용 빈도가 가장 높은 페이지를 교체하는 방식입니다.
   • 특징:
     • 초기에는 자주 사용되었지만, 현재는 덜 사용될 가능성이 있는 페이지를 교체합니다.
     • 최근에 사용 빈도가 높은 페이지는 앞으로도 계속 사용될 확률이 높다는 점에서 LFU와 반대되는 관점을 가지고 있습니다.
6. Second Chance (Clock) 알고리즘
   • 개념: FIFO 방식에 참조 비트를 추가하여 최근에 사용된 페이지에 한 번 더 기회를 주는 방식입니다.
   • 특징:
     • 페이지가 교체 후보일 때 참조 비트가 1로 설정되어 있으면 비트를 0으로 바꾸고, 교체 순서를 다음 페이지로 이동합니다.
     • 참조 비트가 0인 페이지는 교체 대상이 됩니다.
     • 효율적이고 오버헤드가 적으며, FIFO 방식의 단점을 보완합니다.

페이지 교체 알고리즘의 비교

알고리즘설명장점단점

FIFO	가장 먼저 들어온 페이지 제거	구현이 간단	Belady의 모순 발생 가능
OPT	앞으로 가장 오랫동안 사용되지 않을 페이지 제거	최소한의 페이지 부재	실제 구현 불가
LRU	가장 오래 전에 사용된 페이지 제거	실질적인 성능이 좋음	추가 메모리 필요, 시간 복잡도 높음
LFU	참조 횟수가 가장 적은 페이지 제거	자주 사용되지 않는 페이지 교체 가능	초기 사용 페이지가 자주 교체될 수 있음
MFU	참조 횟수가 가장 많은 페이지 제거	사용 빈도 높은 페이지는 적게 사용될 가능성	최근 사용 패턴을 잘 반영하지 못함
Second Chance (Clock)	FIFO + 참조 비트로 최근 사용 페이지에 기회 부여	FIFO 단점 보완, 효율적	참조 비트 사용으로 약간의 오버헤드

선택 기준

• OPT는 가장 이상적인 방식이지만, 실제 구현이 불가능하여 성능 비교에 사용됩니다.
• LRU는 최근 사용된 페이지가 앞으로도 사용될 가능성이 높다고 가정하여 성능이 좋은 편입니다.
• Second Chance는 효율적이고 단순하며, FIFO의 단점을 보완해 실무에서 많이 사용됩니다.

페이지 교체 알고리즘은 메모리 관리의 핵심 요소로, 메모리 사용 패턴에 맞는 최적의 알고리즘을 선택하면 시스템 성능을 크게 향상시킬 수 있습니다.