페이지 교체 알고리즘

페이지 교체 알고리즘(page replacement algorithm)은 가상 메모리에서 페이지 부재(page fault)가 발생했을 때, 어떤 페이지를 메모리에서 제거하고 새 페이지를 적재할지를 결정하는 전략이다. 제한된 물리 메모리 내에서 효율적인 페이지 관리를 통해 전체 시스템 성능을 유지하는 데 핵심적인 역할을 한다.

1 개념

프로세스가 참조한 페이지가 현재 메모리에 없을 때 페이지 부재가 발생하고, 이때 빈 공간이 없다면 기존 페이지 중 하나를 제거해야 한다. 어떤 페이지를 제거할지를 결정하는 기준이 바로 페이지 교체 알고리즘이다.

2 평가 기준

• 페이지 폴트(page fault) 수 최소화
• 현실적 구현 가능성
• 지역성(locality) 반영 여부
• 성능, 구현 난이도, 예측성 등의 균형

3 주요 알고리즘

• FIFO (페이지 교체 알고리즘)
  • 가장 먼저 들어온 페이지를 제거
  • 구현 단순하지만 성능 불안정 (Belady의 역설 가능)

• LRU (페이지 교체 알고리즘)
  • 가장 오랫동안 사용되지 않은 페이지 제거
  • 지역성 가정에 적합, 실제 성능 우수

• LFU (페이지 교체 알고리즘)
  • 가장 적게 참조된 페이지 제거
  • 장기 캐시 오염(Cache Pollution) 발생 가능

• OPT (최적 페이지 교체)
  • 앞으로 가장 오랫동안 사용되지 않을 페이지 제거
  • 실제 구현 불가능 (이론적인 최적 기준)

• Clock 알고리즘
  • LRU의 근사 알고리즘, 하드웨어적으로 구현 용이
  • 각 페이지에 사용 비트(use bit)를 두어 원형 큐 방식으로 관리

• Second-Chance (2차 기회) 알고리즘
  • FIFO를 기반으로 사용 비트가 1이면 기회를 한 번 더 줌

4 비교 요약

알고리즘	교체 기준	장점	단점
FIFO	가장 먼저 들어온 페이지	단순함	사용 여부 고려 안 함
LRU	가장 오랫동안 안 쓰인 페이지	지역성 반영	구현 복잡
LFU	사용 횟수 가장 적음	자주 쓰는 페이지 유지	오래된 정보 유지될 수 있음
OPT	미래 사용 정보 기반	페이지 폴트 최소화	실현 불가

5 같이 보기

• 가상 메모리
• 페이지 부재
• 캐시 알고리즘
• Belady의 역설
• 메모리 관리 기법

6 참고 문헌

• Silberschatz, A., Galvin, P. B., & Gagne, G. (2020). Operating System Concepts. Wiley
• Tanenbaum, A. S., & Bos, H. (2014). Modern Operating Systems. Pearson