페이지 교체 알고리즘 편집하기

페이지 교체 알고리즘(page replacement algorithm)은 [[가상 메모리]]에서 페이지 부재(page fault)가 발생했을 때, 어떤 페이지를 메모리에서 제거하고 새 페이지를 적재할지를 결정하는 전략이다. 제한된 물리 메모리 내에서 효율적인 페이지 관리를 통해 전체 시스템 성능을 유지하는 데 핵심적인 역할을 한다.
==개념==
프로세스가 참조한 페이지가 현재 메모리에 없을 때 페이지 부재가 발생하고, 이때 빈 공간이 없다면 기존 페이지 중 하나를 제거해야 한다. 어떤 페이지를 제거할지를 결정하는 기준이 바로 페이지 교체 알고리즘이다.
==평가 기준==
*'''페이지 폴트(page fault) 수 최소화'''
*'''현실적 구현 가능성'''
*'''지역성(locality)''' 반영 여부
*성능, 구현 난이도, 예측성 등의 균형
==주요 알고리즘==
*[[FIFO (페이지 교체 알고리즘)]]
**가장 먼저 들어온 페이지를 제거
**구현 단순하지만 성능 불안정 (Belady의 역설 가능)

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

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

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

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

*Second-Chance (2차 기회) 알고리즘
**FIFO를 기반으로 사용 비트가 1이면 기회를 한 번 더 줌
==비교 요약==
{| class="wikitable"
!알고리즘!!교체 기준!!장점!!단점
|-
|FIFO||가장 먼저 들어온 페이지||단순함||사용 여부 고려 안 함
|-
|LRU||가장 오랫동안 안 쓰인 페이지||지역성 반영||구현 복잡
|-
|LFU||사용 횟수 가장 적음||자주 쓰는 페이지 유지||오래된 정보 유지될 수 있음
|-
|OPT||미래 사용 정보 기반||페이지 폴트 최소화||실현 불가
|}
==같이 보기==
*[[가상 메모리]]
*[[페이지 부재]]
*[[캐시 알고리즘]]
*[[Belady의 역설]]
*[[메모리 관리 기법]]
==참고 문헌==
*Silberschatz, A., Galvin, P. B., & Gagne, G. (2020). Operating System Concepts. Wiley
*Tanenbaum, A. S., & Bos, H. (2014). Modern Operating Systems. Pearson
[[분류:운영체제]]