Page Replacement Algorithm

정의

- Page Fault가 발생했을 경우, 필요한 페이지를 주기억장치로 가져와야 한다. 이 때 가장 쓸모없는 페이지를 선택하여 교체하는 것이 시스템적으로 가장 효율적인데 이를 정하는 알고리즘

종류

• OPT(Optimal replacement)
• FIFO(First In First Out)
• LRU(Least Recently Used)
• LFU(Least Frequently Used)
• NUR(Not Used Recently)

---

OPT(Optimal replacement)

• 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 기법
• 가장 최적의 방법
• 현실적이지 않음

FIFO(First In First Out)

• 먼저 들어온 페이지를 먼저 교체시키는 방법
• 주기억장치 내에 가장 오래 있었던 페이지를 교체
• Belady's Anomarly
  - 페이지 프레임 수가 증가하면 Page Fault가 더 증가한다.
  

주기억장치에는 빈 프레임이다. 따라서 CPU가 1,2,3,4를 요청할 때 모두 Page Fault가 발생

그리고 1과 2를 요청할 때, 주기억장치에 이미 있으니 넘어감

5를 요청할 때, Page Fault가 발생하고 1,2,3,4 중 1이 가장 먼저 들어왔으니 교체

LRU(Least Recently Used)

• 비교적 가장 오래 전에 사용된 페이지를 교체하는 방법
• 각 페이지마다 계수기

주 기억장치에는 빈 프레임이다. 따라서 CPU가 1,2,3을 요청할 때 모두 Page Fault가 발생

4를 요청할 때 Page Fault가 발생

1,2,3 중 1이 가장 오래 전에 사용되었기 때문에 교체되어 4,2,3

1을 요청할 때 Page Fault가 발생

4,2,3 중 2가 가장 오래 전에 사용되었기 때문에 교체되어 4,1,3

3을 요청할 때, page가 있으니 넘어감

5를 요청할 때 Page Fault가 발생

4,1,3 중 4가 가장 오래 전에 사용되었기 때문에 교체되어 5,1,3

...

LFU(Least Frequently Used)

• 사용 빈도가 가장 적은 페이지를 교체하는 기법

NUR(Not Used Recently)

• 최근에 사용하지 않은 페이지를 교체하는 기법
• 참조비트, 변형비트 사용
  - 우선순위 : 참조비트 > 변형비트
  - 각 비트 값이 1인 것이 가장 나중에 교체될 페이지
• 참조비트
  - 페이지 호출 시에 1, 호출하지 않을 시 0
  
• 변형비트
  - 변경했을 때1, 변경하지 않을 때 0

NUR은 최근에 사용되지 않은 페이지를 교체하고,
LRU는 사용된지 가장 오래된 페이지를 교체하는 알고리즘인데 똑같은 느낌이다..

쓴지 오래된 페이지를 바꾸겠다는 소리가 아닌가?

찾아보니..

1. 페이지 사용량의 추적에서 다르다!
2. 구현 비용에서 다르다!

LRU는 계수기 같은 별도의 하드웨어가 필요하며, 시간적 오버헤드가 발생한다고 한다.