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

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

저번에 페이징에 대해서 포스팅을 했던적이 있는데요?

페이지 교체 알고리즘에 대해선 안다뤘었습니다.

그래서 이번 기회에 한번 다뤄보려고 합니다.

바로 ㄱㄱ

---

페이지 교체 알고리즘

페이지 교체 알고리즘은 운영체제가 가상 메모리를 효율적으로 관리하기 위해 사용하는 방법 중 하나로, 메모리 부족 상황에서 어떤 페이지를 교체할지 결정하는 역할을 합니다. 페이지 교체 알고리즘은 무수히 많지만, 하지만 오늘은 그중 많이 다루는 몇가지만 다루려고 합니다.

페이지 교체 알고리즘들.png

---

 

1. FIFO (First In, First Out)

• 개념: 가장 먼저 들어온 페이지를 가장 먼저 교체합니다. (큐를 사용해서 구현)
• 장점: 구현이 간단합니다.
• 단점: 오래된 페이지가 여전히 많이 사용되는 경우 성능 저하 유발합니다. 페이지 수가 늘어날 수록 page fault가 발생하는 빈도가 늘어나는 경우(Belady's Anomaly)가 생길 수 있습니다.

---

2. OPT (Optimal)

4번 시점에서 이후에 A와 B 페이지가 사용될 것을 알고 있기 때문에 C 페이지를 대상 페이지로 선정해 스왑 아웃시킨다.

• 개념: 앞으로 가장 오래 사용되지 않을 페이지를 교체합니다.
• 장점: 가장 적은 페이지 폴트를 보장합니다. (이론상 최강).
• 단점: 미래의 페이지 접근 패턴을 알아야 하는데, 이는 실질적으로 구현이 불가능하다고 합니다.

---

3. LRU (Least Recently Used)

• 개념: 가장 오랫동안 사용되지 않은 페이지를 교체합니다.
• 장점: FIFO보다 성능이 좋습니다.
• 단점: 최근 사용 기록을 저장하고 갱신하는 비용이 발생합니다.

---

4. LFU (Least Frequently Used)

• 개념: 사용 빈도가 가장 낮은 페이지를 교체합니다.
• 장점: 자주 사용되는 페이지를 보호할 수 있습니다.
• 단점: 페이지의 사용 빈도를 저장하고 갱신하는 비용이 발생하게 됩니다. 최신 페이지가 비교적 불리한 방향이므로 특정 상황에서 성능 저하가 생길 수 있습니다.

---

5. Clock (Second Chance)

위 그림과 같이 대상 페이지를 가리키는 포인터를 사용하는데, 이 포인터가 큐의 맨 아래로 내려가면 시계처럼 다음번에는 다시 큐의 처음을 가리키게 된다.

교체 시, 비트가 0일 경우 교체, 1일 경우 다음 포인터로 넘어가서 다시 검사

• 개념: FIFO 변형으로, 각 페이지에 사용 비트를 사용합니다. (1이면 사용 중)
• 장점: 최근에 사용된 페이지는 교체되지 않습니다. LRU처럼 과거 사용 기록을 저장하지 않아도 됩니다.
• 단점: 참조 비트만으로는 페이지가 얼마나 자주 사용되었는지, 최근에 사용되었는지 구체적으로 알 수 없습니다. 구현이 비교적 복잡하고 페이지의 사용 비트를 저장 및 갱신하는 비용이 발생합니다.

---

현대 OS는 어떤 알고리즘을 주로 사용할까?

일반적으로 운영체제는 LRU와 Clock을 실제로 사용하는 경우가 많습니다.

LRU와 Clock을 혼용하여 가장 오랫동안 사용되지 않은 페이지를 교체하며, 최근에 참조된 페이지를 보존하는데 효과적이도록 페이지 교체를 수행한다고 합니다.