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

운영체제는 주기억장치(Main Memory) 보다 더 큰 용량의 프로그램을 실행하기 위해 프로그램의 일부만 주기억장치에 적재하여 사용한다. 이를 가상메모리 기법이라고 한다. 

✔️ 페이지 교체(page replacement)란?

페이지 교체란 ? 
 
페이징 기법으로 메모리를 관리하는 운영체제에서 필요한 페이지가 주기억장치(=Main Memory)에 적재되어 있지 않을 시, 해당 페이지를 찾아 주기억장치의 빈 프레임에 로딩해야한다.
하지만 이때 빈 프레임이 없을 경우 1)메모리에 올라와 있는 페이지 중 하나를 디스크로 쫓아내(page-out), 2)메모리에 빈 공간을 확보한 후 3)새로운 페이지를 메모리에 올려야한다(page-in).

이러한 과정이 페이지 교체(page replacement) 이다. 

• Victim Page : page-out 된 페이지

 

어떻게 Victim Page를 고르는지 페이지 교체 알고리즘(Page Replacement Algorithm)에 대해서 알아보자 !

---

✔️FIFO(First In First Out) 알고리즘

• FIFO 알고리즘은 가장 먼저 메모리에 올라온 페이지를 가장 먼저 내보내는 알고리즘이다. 

FIFO 알고리즘

• 구현은 간단하지만, 성능은 좋지 않다. 
• Belady's Anomaly 문제가 발생할 수 있다. 

Belady's Anomaly

• Belady's Anomaly : 프레임 수를 증가시킴(= 메모리 용량 증가)에도 불구하고 페이지 부재(=Page Fault)가 증가하는 현상 

---

✔️OPT(Optimal) 알고리즘

• OPT 알고리즘은 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 알고리즘

OPT 알고리즘

• 모든 페이지 교체 알고리즘 중 page-fault 발생이 가장 적다. 
• 프로세스가 앞으로 사용할 페이지를 미리 알아야하는 문제점 → 실제로 구현하기 불가능한 알고리즘

---

✔️ LRU(Least Recently Used) 알고리즘 

• LRU 알고리즘은 가장 오랫동안 사용하지 않은 페이지를 교체하는 알고리즘이다.

LRU 알고리즘

• 성능이 좋은편이여서 많은 OS가 채택하는 알고리즘이다.
• 가장 오랫동안 사용하지 않은 페이지를 찾기위해 LRU page를 추적해야하는 문제점이 있다. 

---

✔️ Clock Algorithm

LRU와 비슷한 알고리즘으로, LRU와 달리 페이지 교체(page replacement)를 위해 하드웨어적인 지원을 통해 동작한다. 

 

• System의 모든 페이지들이 circular list를 구성함. 
• Victim Page를 찾기 위해 페이지의 'reference bit'를 확인함. 
• bit가 1이면, 페이지가 최근에 사용되었다는 뜻으로 0으로 바꾼 후 지나간다. 
• bit가 0이면, 페이지가 최근에 사용되지 않았다는 뜻으로 page를 교체한다. 

 

 

#참고

https://doh-an.tistory.com/28

https://code-lab1.tistory.com/60

https://github.com/alstjgg/cs-study/blob/main/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C/%ED%8E%98%EC%9D%B4%EC%A7%95%20%EA%B5%90%EC%B2%B4%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98.md