[알고리즘] 페이지 교체 알고리즘

💡 tl;dr

---

• FIFO (First In First Out)
• LFU (Least Recently Used)
• LRU (Least Recently Used)

FIFO (First In First Out)

---

• 페이지가 주기억장치에 적재된 시간을 기준으로 교체될 페이지를 선정하는 기법
• 단점
  • 중요한 페이지가 오래 있었다는 이유만으로 교체되는 불합리
  • 가장 오래 있었던 페이지는 앞으로 계속 사용될 가능성

LFU (Least Frequently Used)

---

• 가장 적은 횟수를 참조하는 페이지를 교체
• 단점
  • (참조될 가능성이 많음에도 불구하고) 최근에 사용된 프로그램을 교체시킬 가능성
  • 해당 횟수를 증가시키므로 오버헤드 발생

LRU (Least Recently Used)

---

• 가장 오랫동안 참조되지 않은 페이지를 교체
• 단점 : 프로세스가 주기억장치에 접근할 때마다 참조된 페이지에 대한 시간을 기록해야함. 큰 오버헤드가 발생

참조

---

• LRU 알고리즘