페이지 교체 알고리즘

1. FIFO(first in first out)

• 메모리에서 가장 오래된 페이지를 교체한다.
• 타임스탬프나 큐를 사용해서 순서를 확인한다.
• 단순한 알고리즘이지만, 사용빈도를 고려하지 않기 때문에 Page Fault가 자주 발생할 위험이 있다.

---

2. LRU(least-recently-used)

• 가장 오랫동안 사용되지 않은 페이지를 교체한다.
• 단순하지만 효과적인 알고리즘이다.

---

3. 계수-기반(Counting-Based) 페이지 교체

각 페이지가 현재까지 참조된 횟수를 카운팅하는 방법이다. 이 방법을 이용해 두 가지의 알고리즘을 만들 수 있다.

1) LFU(least-frequently-used)

• 참조 횟수가 가장 작은 페이지를 교체한다.
• 교체 대상이 여러 개일 경우, LRU에 따라 선택한다.
• 초기에 자주 사용된 이후에 사용되지 않는 페이지가 잔존하는 문제가 발생한다.

2) MFU(most-frequently-used)

• 참조 횟수가 가장 많은 페이지를 교체한다.
• 참조 횟수가 많다는 것은 이미 충분히 사용되어 더 이상 사용되지 않을 것이라는 판단이다.

 

그러나 위 두 알고리즘은 LRU에 비해 구현이 복잡하지만 성능이 잘 나오지 않기 때문에 잘 사용되지 않는다.