배경

• Frame: 메모리를 나눈 조각. 따라서 메모리는 Frame의 집합
• Page: 프로세스를 나눈 조각. 따라서 프로세스는 Page의 집합
• 프로세스가 특정 페이지를 요구할 때
  - if 페이지가 이미 메모리에 올라가 있다 👉 그걸 참조
  - else page fault 👉 페이지를 찾아 빈 프레임에 할당
  • ❗️ 빈 페이지가 없다면? 👉 교체할 희생 프레임을 찾는 페이지 교체 알고리즘 필요

페이지 교체 알고리즘

Page fault가 발생했을 때 어떤 페이지 프레임을 교체할 지 결정하는 알고리즘

FIFO

메모리에 올라온지 가장 오래된 페이지를 교체하는 알고리즘
따라서, 페이지가 올라온 시간을 기록하거나 Queue를 사용해야 함

👉 활발하게 사용중인 페이지가 계속 교체되어 page fault가 빈번하게 일어나고 실행속도가 느려질 수 있음 !!

Optimal

앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 알고리즘
즉, 프로세스가 앞으로 사용할 프로세스를 알아야하는데 이는 실제에서 불가능

LRU

Least-Recently Used, 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘
과거의 데이터를 이용해 페이지가 사용될 시간을 예측하는 기법. 많은 운영체제가 채택

LFU: Counting-Based

각 페이지가 현재까지 참조된 횟수를 카운딩하는 Counting-Based 알고리즘!

Least-Frequently Used, 참조된 횟수가 가장 적은 페이지를 교체하는 알고리즘
만약 동일 count인 페이지들이 있다면, LRU를 따름

👉 초기에 많이 참조되고 쓰지지 않는 페이지가 있다면, 참조횟수가 많아 계속 남아있기 때문에 많은 page fault를 유발함

MFU: Counting-Based

Most-Frequently Used, 참조된 횟수가 가장 많은 페이지를 교체하는 알고리즘
지금까지 적게 참조된 페이지가 앞으로는 많이 쓰일거라는 아이디어!

근데 구현비용이 비싸고 LRU 성능이 좋아서 LFU, MFU는 잘 쓰이지 않음