Paging을 이용하여 Virtual memory를 구현했을 때, 프로그램이 실행되다 보니 내가 읽어야 하는 페이지가 주기억장치에 없는 경우가 있다!

이 경우를 Page Fault(페이지 부재)라고 한다.

Page Fault가 발생한 경우 필요한 페이지를 주기억장치에 적재해야 하는데, 이 때 주기억장치가 꽉 차 있다면 누구를 퇴출시킬지를 정하는 알고리즘이다.

대표적으로는 OPT, FIFO, LRU, LFU, NUR, SCR 등이 있다. 하나씩 araboza

OPT

Optimal Replacement의 줄임말.
앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 방법이다.
당연히 최적의 알고리즘이다.
근데 사실상 구현할 수가 없다.
궁예도 아니고...뭐가 오랫동안 안쓰일지 어케 알겠음
이론적으로 optimal한 알고리즘이다.

FIFO

First In - First Out 알고리즘.
각 페이지가 주기억장치에 적재될 때마다 그 때의 시간을 기록해두고, 가장 먼저 들어왔던 페이지를 교체하는 알고리즘이다.
구현하기가 쉽다.

LRU

Least Recently Used 알고리즘.
각 페이지마다 타이머(Counter나 Stack)을 두어 해당 페이지가 사용될 때마다 0으로 초기화하고, 가장 오랫동안 사용되지 않은 (낡은!) 페이지를 교체한다.

LFU

Least Frequently Used 알고리즘.
각 페이지마다 참조된 횟수를 기록해두고, 가작 참조된 횟수가 적은 페이지를 교체한다.

NUR

Not Used Recently.
LRU와 비슷한 알고리즘.
LRU - 가장 오랫동안 참조하지 않은 페이지
NRU - 최근에 참조/변형하지 않은 페이지
참조 비트, 변형 비트를 사용하여 최근 사용 여부를 확인한다.