#페이지 교체 알고리즘

페이지 교체 알고리즘

메모리가 가득 차서 프로세스에게 자원을 할당할 수 없는 경우가 발생한다. 이런 경우에는 현재 할당된 메모리 공간 중 사용하지 않는 공간을 선점하여 프로세스에게 할당할 수 있겠지만, 점유된 공간 중 어떤 곳을 선점해야할지가 시스템의 관점에서 이슈거리가 된다. 이 상태를 해소하기 위해 ‘페이지 교체(page replacement)’ 기법을 사용할 수 있으며, 이 기법을 구현하기 위한 알고리즘은 다음과 같다

알고리즘	설명
FIFO	● 메모리에 적재된 시간이 가장 오래된 페이지 교체 (페이지들을 큐로 관리) ● 구현 간단하나 최적 성능 보장 못함 ● Belady의 모순 (Belady’s anomaly) : 프레임 개수가 많아지더라도 페이지 부재율이 높아지는 현상
OPT	● 최적 페이지 교체 (Optimal Page Replacement) : 앞으로 가장 오랜 시간 동안 사용되지 않을 페이지 교체 ● 다른 모든 알고리즘보다 페이지 부재율이 낮으면서 Belady의 모순이 발생하지 않는 페이지 교체 알고리즘 ● OPT 혹은 MIN으로 표기
LRU	● Least-Recently-Used : 가장 오랫동안 사용되지 않은 페이지 교체 ● OPT에 근사하는 방법 ● 최근의 과거 참조를 기반으로 미래 참조 형태의 근사치 결정 ● Belady의 모순 현상이 나타나지 않는 페이지 교체 알고리즘 ● LRU 페이지 교체의 정확한 구현은 어려움 - 추가 하드웨어가(참조 시간)가 지원되지 않는 시스템이 있음 - 메모리 참조 때마다 참조 시간 정보/스택을 매번 갱신
NRU	● Not-Recently-Used : 시간 정보 대신 과거의 참조 유무를 조회하여 교체 페이지 선정 ● 기본적인 LRU 근사 알고리즘 ● 페이지 테이블에 참조 비트 (reference bit) 추가 - 초기에 모두 0이며 페이지가 참조될 때 1로 설정 - 페이지 교체 시 혹은 주기적으로 0으로 재초기화 ● 추가 참조 비트 (additional reference bit) 알고리즘 - 참조 비트를 확장하여 추가 정보로 활용
카운팅	● 각 페이지의 참조 횟수를 기록하여 활용 ● 실제 구현은 쉽지 않고, 최적 알고리즘에 잘 근사하지 못함 ● LFU (Least Frequently Used) 알고리즘 - 참조 횟수가 가장 적은 페이지 교체 - 참조 빈도와 참조 시간은 정확히 일치하지 않음 ● MFU (Most Frequently Used) 알고리즘 - 참조 횟수가 가장 많은 페이지 교체 - 참조 횟수가 적은 페이지는 최근에 적재되었고 앞으로 참조될 가능성이 높을 것이라는 직관에 의존

참고 자료

엄영익·정태명 공저, 『컴퓨터 운영체제론』, 생능출판사