23. Page Replacement

 

---

---

 

컴퓨터가 메모리보다 디스크에 접근하는게 수만배 느리다.

---

 

Page replacement의 목적은 page fault를 최소화 하는 것이다.

---

 OPT 

OPT : 모든 상황에서 어떤 Page replacement policy보다 낫다.

가장 Page Fault가 낮다.

---

 

4번에서 Page fault가 발생한다.

누구를 뽑아낼 것이냐?

가장 나중에 참조될 것 같은 애를 뽑아낸다. 

3이 가장 나중에 참조될 것 같으니 3을 뺀다.

---

Hit Ratio는 5/12 이고

Page Fault Ratio는 7/12 이다.

Page Fault Ratio는 낮을수록 좋은 것

---

 

그러나 Belady Algorithm은 미래에 누가 참조될지를 알 때 가능하다.

실제 system에 적용하긴 힘들고 수학적은 minimum이 언제인지를 알 때 쓰인다.

평가 기준으로 쓰인다.

---

 First-In First-Out 

먼저 들어온 애를 빼자 !

---

 

 

가장 옛날에 들어온 애를 빼버리자

---

 

그러나 FIFO는 Belady's Anomaly에 굉장히 좋지않다.

---

 

4개 frame으로 해줬는데도 fault 수가 증가한다. 더 안좋아지는 현상이다.

fault가 증가하는 현상 : Belady Anomaly

Belady Anomaly가 있으면 좋지 않은 것이다.

---

---

 Least Recently Used 

Least Recently Used : 가장 최근에 사용되지 않는 얘를 뽑자.

과거의 행적을 보고 미래를 판단하겠다.

---

---

 

LRU는 Belady Anomaly를 격지 않는다.

메모리를 더 주면 Page fault가 늘어나지 않는다.

FIFO는 메모리를 더 줘도 Page fault가 일어날 수 있다 = Belady Anomaly

---

Stack Algorithm이라서 Belady Anomaly를 격지 않는다.

---

 LRU를 구현하는 2가지 방법 

 

 

LRU를 lniked list로 만들면 참조할 때마다 overhead가 크다.

 

LRU를 구현할 때 각 Page frame마다 언제 썼는지에 대한 필드(time-of-use filed)를 저장해 놓고

참조할 때마다 언제 썼는지에 대한 Counter를 업데이트 한다.

만약 누군가를 빼야 하면 가장 작은 Counter를 가진 애를 뺀다. 

---

 Additional-Reference-Bits Algorithm 

bit를 저장할 새로운 Table에다가 Reference bit을 저장하고, Shift 해주고,

원래 Page Table의 Reference bit을 주기적으로 초기화 해준다.

 

MMU는 Refenece bit을 1로 셋팅하기만 하고,

운영체제가 주기적으로 Reference bit을 shift해서 넣어주고 원래 Page Table을 clear해준다.

 

새로운 Table에 2진수로 쌓이게 되고, 숫자가 작은 것이 과거의 것이다.

 

---

근데 일정 주기마다 다 clear 해주기가 힘들다. 그래서 나온 것

 Second-Chance Algorithm 

기회 한번만 더주세요!

 

 

누군가를 빼야되는 상황이 오면 1로 reference bit이 된 것을 0으로 clear만 하고 빼지 않는다.

---

handle 이 가리키면서 동작한다.

모든 페이지들이 다 참조가 되어 있으면 한바퀴 뺑 돌아야 하지만 그래도 낫다.

 

---

---

 

잘 사용되지 않는다. Counting Based는