페이지 교체 알고리즘

* 페이지 부재(Page Fault) 가 발생하면 가상기억장치에서 필요한 페이지를 찾아 주기억장치에 적재 해야하는데, 이때 주기억장치의 모든 페이지 프레임이 사용중이면 어떤 페이지 프레임을 선택하여 교체할 것인지를 결정하는 기법

=> 페이지 부재 : CPU가 엑세스한 가상 페이지가 주기억장치에 없는 경우

OPT(Optimal replacement, 최적 교체)

• 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체
• 벨레이디(Belady)가 제안
• 페이지 부재가 가장 적게 발생함 => 효율적

FIFO (First In First Out)

• 페이지가 주 기억장치에 적재될 때마다 그때의 시간을 기억시켜 가장 먼저 들어와서 가장 오래 있었던 페이지를 교체하는 기법
• 이해가 쉬움
• 프로그래밍 및 설계가 간다.

LRU (Least Recently Used)

• 최근에 가장 오랫동안 사용하지 않은 페이지를 교체
• 각 페이지마다 계수기(Counter)나 스택(Stack)을 두어 현시점에서 가장 오랫동안 사용하지 않은 페이지 교체

Counter(계수기) : 페이지 별로 존재시킴, 해당 페이지가 사용될 때 0으로 초기화 => Counter 제일 높은 것 교체

LFU (Least Frequently Used)

• 사용 빈도가 가장 적은 페이지를 교체
• 활발하게 사용되는 페이지는 사용 횟수가 많아 교체되지 않고 사용됨

NUR (Not Used Recently)

• LRU와 비슷한 알고리즘
• 최근에 사용하지 않은 페이지를 교체
• 최근에 사용되지 않은 페이지는 향후에도 사용되지 않을 가능성이 크다를 전제로 함
• LRU에서 나타나는 시작적인 오버헤드를 줄일 수 있다.
• 최근 사용 여부 확인 => 각 페이지마다 두 개의 비트(참조 비트, 변형 비트)가 사용됨
  • 참조 비트 : 페이지가 호출되지 않았을 때는 0, 호출되었을 때는 1
  • 변형 비트 : 페이지 내용이 변경되지 않았을 때는 0, 변경되었을 때는 1
  •  

참조 비트	0	0	1	1
변형 비트	0	1	0	1
교체 순서	1	2	3	4

 

SCR (Second Change Replacement, 2차 기회 교체)

• 가장 오랫동안 주 기억장치에 있던 페이지 중 자주 사용되는 페이지의 교체를 방지
• FIFO 기법의 단점을 보완