[정보처리기사] 페이지 교체 알고리즘

페이지 교체 알고리즘

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

• OPT (OPTimal replacement, 최적 교체)
  • 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 기법
  • 벨레이디(Belady)가 제안한 것으로, 페이지 부재 횟수가 가장 적게 발생하는 가장 효율적인 알고 리즘
• FIFO(First In First Out)
  • 각 페이지가 주기억장치에 적재될 때마다 그때의 시간을 기억시켜 가장 먼저 들어와서 가장 오래 있었던 페이지를 교체하는 기법
  • 이해하기 쉽고, 프로그래밍 및 설계가 간단함

• LRU(Least Recently Used)
  • 최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법
  • 각 페이지마다 계수기(Counter)나 스택(Stack)을 두어 현시점에서 가장 오랫동안 사용하지 않은, 즉 가장 오래전에 사용된 페이지를 교체함

• LFU (Least Frequently Used)
  • 사용 빈도가 가장 적은 페이지를 교체하는 기법
  • 활발하게 사용되는 페이지는 사용 횟수가 많아 교체되지 않고 사용됨

• SCR(Second Chance Replacement, 2차 기회 교체)
  • 가장 오랫동안 주기억장치에 있던 페이지 중 자주 사용되는 페이지의 교체를 방지하기 위한 것으로, FIFO 기법의 단점을 보완하는 기법
• NUR (Not Used Recently)
  • LRU와 비슷한 알고리즘으로, 최근에 사용하지 않은 페이지를 교체하는 기법
  • 최근에 사용되지 않은 페이지는 향후에도 사용되지 않을 가능성이 높다는 것을 전제로, LRU에 서 나타나는 시간적인 오버헤드를 줄일 수 있음
  • 최근의 사용 여부를 확인하기 위해서 각 페이지마다 두 개의 비트, 즉 참조 비트(Reference Bit)와 변형 비트(Modified Bit, Dirty Bit)가 사용됨