[운영체제(OS)] 10-2) Page Replacement Algorithm

---

<Page Replacement Algorithm>

: 이전 포스팅(https://geukggom.tistory.com/276)에서 Demand paging할 때 어떤 frame의 victim page를 대체할지를 정해야하는데, 이를 위한 알고리즘입니다. 

 

* page reference string : 참조되는 일련의 page 번호입니다.

알고리즘의 성능 평가는 page reference string이 pauge fault를 얼마나 내는지를 조사하는 방식으로 이뤄집니다.

 

---

1. OPT(Optimal Algorithm)

: 가장 먼 미래에 참조될 page를 대체하는 방법입니다. 항상 최적의 결과를 가지지만, 미래의 참조를 모두 알고 있어야 가능하기 때문에 실제로 사용할 수는 없고 다른 알고리즘의 성능에 대한 upper bound를 제공하는 역할을 합니다.

 

---

2. FIFO(First In First Out) Algorithm

: 가장 먼저 들어온 page를 대체하는 방법입니다. 

• 장점 : 모든 page가 평등하게 frame에 거주하고, 구현하기 쉽습니다.
• 단점 : 자주 필요한 page도 대체합니다.

 

* Belady's anomaly : frame이 늘어날 때 특정 구간에서 page fault가 감소하지 않고 오히려 늘어나는 현상입니다.

3 -> 4개로 늘어날 때 page fault가 오히려 증가함

---

3. LRU(Least Recently Used) Algorithm

: 가장 오래전에 참조된 page를 대체하는 알고리즘입니다. 연결리스트로 구현하면 제일 최근에 참조된 page를 가장 앞으로 옮겨서 O(1)만에 page를 찾고 삽입할 수 있습니다.

• 장점 : Optimal에 근접하며, Belady's anomaly가 발생하지 않습니다.
• 단점 : 구현하기 어렵고, 접근하는 빈도를 고려하지 않습니다.

---

4. LFU(Least Frequently Used) Algorithm

: 참조 횟수가 가장 적은 page를 대체하는 알고리즘입니다. 최저 참조 횟수인 page가 2개 이상이면 임의의 page를 선정하는데, 성능 향상을 위해 가장 오래 전에 참조된 page를 지우는 식으로 구현할 수 있습니다.

• 장점 : LRU보다 장기적으로 보기 때문에 page의 사용 빈도를 더 정확하게 반영할 수 있습니다.
• 단점 : 최근성은 반영하지 못합니다.

---

5. Second Chance Algorithm (Clock Algorithm)

: LRU, LFU 알고리즘은 운영체제가 참조한지 오래되거나 적게 참조한 page를 정확하게 알기 어렵기 때문에 실제로 paging system에서 사용할 수 없습니다. 이에 대한 해결 방법으로 Clock Algorithm을 사용합니다.

Clock Algorithm은 LRU와 비슷한 알고리즘으로, 최근에 참조되었는지 여부를 나타내는 Reference bit을 사용합니다.

reference bit가 0인 page를 찾을 때까지 포인터를 한 바퀴 이동시킵니다.

• reference bit가 0 -> page로 교체합니다. 
• reference bit가 1 -> 0으로 교체해줍니다.

한 바퀴를 돌았을 때 교체할 page를 찾지 못했으면 한 바퀴 더 돕니다. reference bit를 0으로 교체해준 page가 그대로이면 해당 page를 교체하고, 그렇지 않으면 자주 사용되는 page이므로 다음 page로 포인터를 이동시킵니다.

 

* Modified bit(dirty bit) : Enhanced Second Chance Algorithm에서 추가된, 최근에 해당 page가 변경되었는지를 나타내는 지표입니다. Modified bit가 1이면 page가 변경되었기 때문에 교체하려면 디스크에 이를 반영해야하고, I/O 작업이 동반되어 시간이 오래 걸립니다.

Reference bit == 0 -> Modified bit == 0 순서로 우선순위를 가지며 확인합니다.