[운영체제] 페이지 교체 알고리즘

✅  페이지 교체 알고리즘

Page Fault가 발생했을 때, 새로운 페이지를 메모리에 적재하려고 보면 이미 모든 프레임이 가득 찬 상태일 수 있다.

 

이 경우 기존에 있던 페이지 중 하나를 제거하고 새 페이지를 넣어야 하는데,

어떤 페이지를 제거할지를 결정하는 기준이 바로 페이지 교체 알고리즘이다.

 

---

 

📍 FIFO(First In First Out)

: 메모리에 들어온 페이지 중 가장 오래된 페이지를 교체

 

💡 장점

• 구현이 간단함
  • 큐 자료구조를 사용해 쉽게 구현 가능

 

🛠️ 단점

• 성능을 보장할 순 없음
  • 최근에 자주 사용되던 페이지가 오래됐다는 이유로 교체될 수 있음 
  • 이로 인해 Page Fault 증 가 가능
• Bleady 모순 발생 가능: 프레임의 개수를 늘려도 Page Fault가 더 많이 발생하는 모순
  • ex) 페이지 요청 순서: 1 2 3 4 1 2 5 1 2 3 4 5
    • 프레임 3개일 때: 1 2 3 4 1 2 5 1 2 3 4 5 -> Page Fault 9회 발생
    • 프레임 4개일 때: 1 2 3 4 1 2 5 1 2 3 4 5 -> Page Fault 10회 발생

 

---

 

📍 OPT (Optimal Page Replacement)

: 앞으로 가장 오랫동안 사용하지 않을 페이지 교체

 

💡 장점

• Bleady 모순이 발생하지 않음
• Page Fault를 최소화할 수 있음

 

🛠️ 단점

• 실현 가능성이 희박함(불가능)
  • 미래의 페이지 참조 형태를 알아야 하기 때문
  • 그래서, 주로 다른 알고리즘의 성능을 비교하기 위해 사용됨

 

---

📍 LFU (Last Frequently Used)

: 사용 빈도가 가장 적은 페이지 교체

 

활발하게 사용되는 페이지는 참조 횟수가 많아질 것이라는 가정

 

🛠️ 단점

• 각 페이지의 사용 횟수를 기록해야 하므로 구현이 쉽지 않음
• 최적 알고리즘이라고 보기 어려워 잘 사용하지 않음
  • 어떤 프로세스가 특정 페이지를 자주 사용하다가, 더 이상 사용하지 않아도 계속 메모리에 적재됨

 

---

📍 MFU (Most Frequently Used)

: 사용 빈도가 가장 적은 페이지 교체

 

참조 횟수가 가장 작은 페이지가 최근에 메모리에 올라온 페이지로, 앞으로 계속 사용될 것이라고 가정

 

🛠️ 단점

• 최적 알고리즘이라고 보기 어려워 잘 사용하지 않음

 

---

 

📍 LRU (Least Recently Used)

: 최근에 가장 오랫동안 사용하지 않은 페이지 교체

 

구현 방법에는 2가지가 있다.

1. 카운터로 구현: 각 페이지마다 사용된 시간을 카운터로 저장
2. 스택으로 구현: 가장 최근에 참조된 페이지는 스택의 top으로 이동, 스택의 bottom에 있는 페이지가 교체될 페이지

 

💡 장점

• FIFO 알고리즘보다 우수
• 가장 많은 운영체제가 채택하는 알고리즘

 

🛠️ 단점

• 사용된 페이지에 대한 시간 정보를 기록해야 함