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

📌 페이징 기법으로 메모리를 관리하는 운영체제에서 필요한 페이지가 주기억장치에 적재되지 않았을 시, 어떤 페이지 프레임을 선택하여 교체할 것인지 결정하는 방법 ( → 메모리가 꽉 찼을 때 어떤 페이지를 스왑 영역으로 내보낼지 결정하는 알고리즘)

🧷 프레임 : 물리 메모리를 일정한 크기로 나눈 블록
🧷 페이지 : 가상 메모리를 일정한 크기로 나눈 블록

---

 

▶️ 페이지 교체 알고리즘의 종류

1️⃣ FIFO(First In First Out) 알고리즘 : 가장 먼저 메모리에 올라온 페이지를 가장 먼저 내보내는 알고리즘

• 구현이 간단하지만 성능은 좋지 않은 편
• 들어온 시간을 저장하거나 올라온 순서를 큐를 이용해 저장할 수 있음
• Belady’s Anomaly 현상이 발생할 수 있음
• 🔑 Belady’s Anomaly : 프레임의 갯수가 많아져도 page-fault가 줄어들지 않고, 늘어나는 현상

2️⃣ OPT (Optimal) : 앞으로 가장 오랫동안 사용되지 않을 페이지 교체

• 가장 이상적임
• 모든 페이지 교체 알고리즘 중 page-fault 발생이 가장 적음
• Belady’s Anomaly 현상이 발생하지 않음
• 프로세스가 앞으로 사용할 페이지를 미리 알아야 함 → 실제로 구현하기 거의 불가능
• 비교 연구 목적을 위해 사용됨

3️⃣ LRU(Least Recently Used) 알고리즘 : 가장 오랫동안 사용하지 않은 페이지를 교체하는 알고리즘

• 최적 알고리즘과 비슷한 효과를 낼 수 있음
• 성능이 좋은 편
• 많은 운영체제가 채택하는 알고리즘
  
  

4️⃣ LFU(Least Frequently Used) 알고리즘 : 참조횟수가 가장 적은 페이지를 교체하는 알고리즘

• 교체 대상이 여러 개라면 가장 오랫동안 사용하지 않은 페이지를 교체
  
  

5️⃣ MFU(Most Frequently User) 알고리즘 : LFU와 반대로 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘

 

6️⃣ NUR(Not Used Recently, Not Recently Used), 클럭 알고리즘 : 최근에 사용하지 않은 페이지 교체

• 교체되는 페이지의 참조 시점이 가장 오래되었다는 것을 보장하지는 못함
• 적은 오버헤드로 적절한 성능
• 동일 그룹 내에서 선택 무작위
• 각 페이지마다 두 개의 비트 → 참조 비트(Reference Bit)와 변형 비트(Modified Bit, Birty Bit)가 사용됨
  • 참조 비트 : 페이지가 참조되지 않았을 때 0, 호출되었을 때 1 (모든 참조비트를 주기적으로 0으로 변경)
  • 변형 비트 : 페이지 내용이 변경되지 않았을 때는 0, 변경되었을 때 1
  • 우선 순위 :: 참조비트 > 변형비트
    
    
    

---

참고자료

OS는 할껀데 핵심만 합니다. 17편 페이지 교체 알고리즘(FIFO, LRU, LFU , NUR, 2차 기회 알고리즘, 시계 알고리즘)