Page Replacement

Page Replacement

• Demand Paging을 통해 요구되는 페이지만 backing store에서 불러오게 되는데
• 이때 요구되는 페이지는 점차 늘어나고 결국 메모리가 가득차는 문제가 발생한다
• 이때 메모리가 가득찼는데도 추가로 페이지를 가져오기 위해
• 어떤 페이지는 backing store로 다시 보내고
• 남은 빈 공간에 페이지를 가져와야 한다.
• page를 다시 backing store로 보내기 -> page-out
• 빈 공간에 페이지 가져오기 -> page-in

Page Replacement Algorithm

• Page Replacement를 수행하면서 어떤 페이지를 다시 backing store로 보낼까?
• 그때 사용되는것이 Page Replacement Algorithms 이다.

First-In First-Out (FIFO)

• 가장 먼저 메모리에 올라온 페이지를 victim 대상으로 선정
• 가장 간단한 알고리즘
• 단, Belady's Anomaly 현상 발생 가능
  • Belady's Anomaly?
    • 프레임 갯수가 많아저도 page-fault가 지속해서 늘어나는 현상

Optimal (OPT)

• 가장 앞으로 오랜동안 사용하지 않을 페이지를 victim 대상으로 선정
• 모든 페이지 교체 알고리즘에서 가장 page-fault 발생 가능성이 낮음
• 하지만, 앞으로 사용할 프로세스가 무엇인지를 미리 알고 있어야함
  • 실제로 구현하기 거의 불가능

Least Recently Used (LRU)

• 가장 오랫동안 사용하지 않은 페이지를 교체
• 성능이 좀 좋은 편
• 대부분의 운영체제가 사용

Least Frequently Used (LFU)

• 참조 횟수가 가장 적은 페이지를 교체하는 알고리즘
• 참조 횟수를 전부 파악해야 함
• 참조 횟수가 동일한 경우, LRU를 적용해서 교체

Most Frequently User (MFU)

• LFU와 반대되는 알고리즘
• 참조 횟수가 가장 많은 페이지를 교체