Page Relacement

Need for page replacement

4번의 load M은 instruction은 load 되어있는데 data는 안된 상태

Free Frame이 없다면

- 메모리에서 사용하지 않는 페이지를 찾아서 swap out ->Page replacement

- Page replacement algorithms for minimum number of page faults are required

- Modify bit to reduce overhead of page transfers; 수정된 페이지만 디스크로 다시 쓰일 수 있다

Basic Page replacement

1) 디스크에서 원하는 페이지가 있는 위치를 찾는다

2) Free Frame을 찾는다

Free Frame이 있으면 사용, 없으면 victim Frame을 선택하기 위해 page replacement 알고리즘을 사용한다

3) 원하는 페이지를 free frame에 넣고 페이지와 프레임 테이블을 업데이트한다

4) 프로세스를 재시작한다

Page Replacement Algorithm

1 FIFO page replacement

- 가장 오래된 페이지가 선택된다

- 위 그림을 보면 페이지 프레임이 3개인 데에 reference string이 하나씩 들어가고 있다. 0을 넣었을 때 안에 이미 0이 있기 때문에 page fault가 발생하지 않고 다음으로 넘어간다. 어쨌거나 새롭게 페이지 안에 값을 넣을 때 page fault가 발생한다

- Page Fault Rate = 15/20

- Belady's abnomaly : More Frames -> More Page Faults 가 발생할 수 있다

2 Optimal page replacement

- 있는 페이지들 중 앞으로 가장 오랫동안 쓰이지 않을 페이지를 교체한다 (미래를 본다)

- PFR = 9/20

3 LRU page replacement

- Least Recently Used algorithm

- 가장 오랫동안 쓰이지 않은 페이지를 교체한다 (과거를 본다)

- PFR = 12/20

- Implementation

* Counters : 모든 페이지 테이블 엔트리는 카운터가 있다. 페이지가 이 엔트리를 통해 참조될 때 clock is copied into the counter

* Stack : 페이지가 참조될 때 스택에서 제거되고 top으로 올라간다

=> Requires h/w supports

4 LRU-Approximation page replacement

- 몇 컴퓨터 시스템들만이 true LRU 알고리즘을 위해 적합한 하드웨어 서포트를 제공하기 때문에..

- reference bit을 이용한다

- Additional-reference-bits algorithm

* 각 페이지 테이블에 8bit byte

* regular interval에서 OS는 각 페이지의 8bit byte의 high-order bit의 reference bit을 1 이동하고 low-order bit은 버린다 ; 최근 8 time interval의 page use 기록

* 11000100의 페이지는 01110111보다 더 최근에 사용되었다 (앞에 1이 위치할수록 recently used)

- Second-Chance algorithm

* FIFO algorithm 기반

* 만약 reference bit이 1로 셋되어 있다면, 페이지에게 두번째 기회를 주고, 다음 FIFO 페이지를 선택하도록 한다

* 페이지가 두번째 기회를 얻으면 reference bit은 cleared

* 만약 모든 빗들이 set되어있으면 second-chance replacement는 FIFO replacement가 된다

- Enhanced Second-Chance algorithm

* Reference bit+modify bit

* 0 0 : 최근에 사용되지도, 수정되지도 않았다

  0 1 : 최근에 사용되지 않았지만 수정되었다 -> 페이지가 replacement 전에 written out

  1 0 : 최근에 사용되었지만 clean -> 곧 다시 사용될 것이다

  1 1 : 최근에 사용, 수정되었다

* 교체되어야 할 페이지가 찾아지기 전에 원형 큐를 여러 번 스캔해야 한다

5 Counting-Based page replacement

- 각 페이지에 대한 참조 회수를 카운트

- LFU (Least Frequently Used) Algorithm

* 카운트가 가장 적은, 적게 사용된 페이지 교체

* 활발하게 사용된 페이지는 큰 참조 회수를 가졌을 것이라 가정

_ MFU (Most Frequently Used) Algorithm

* 가장 큰 카운트의, 많이 사용된 페이지를 교체

* 적게 사용된 페이지들은 가져왔지만 아직 사용되지 않았다고 가정