[2019.07.03] Page Replacement

Replacement Policy : 어떤 page가 대체 (swap) 될 것인가? 대체되는 Page는 나중에 가장 참조될 가능성이 적은 애이다.

Basic Replacement Algorithms
- FIFO : memory에 가장 오래 있던게 대체된다.
- Optimal Policy : 제일 긴 시간 후에 사용될 page를 대체한다. 하지만 예측할 수 없으므로 사용 못한다.
- Least Recently Used : 가장 오래전에 사용된 page를 대체한다. 근데 시간을 저장하므로 시간, 비용이 많이 든다.
- Clock Policy : LRU와 비슷하지만 근사한시킨 알고리즘을 사용한다. use bit을 설정하여 0인 page를 대체한다.
 성능은 OPT > LRU > CLOCK > FIFO 순이다. (OPT는 현실적이지 않다.)
- Enhanced Clock Policy
 use bit과 modified bit를 pair로 참조한다. 최근 사용 여부와 내용 수정 여부를 확인했을 때 둘 다 (0,0)인 page가 가장 우선적으로 대체된다.

Trashing
- Degree of multiprogramming : memory에 있는 process의 갯수
 process의 조각이 필요하기 전에 그 조각이 swapping (대체)되면 page fault가 발생한다. process가 충분한 page를 갖고 있지 않으면 page fault rate가 높다. -> 낮은 CPU 이용률을 초래한다. OS는 multiprogramming의 degree를 높여야겠구나 라고 생각한다. 다른 process가 추가되고 process 당 memory frame이 적어진다.
 CPU 이용률이 증가함에 따라 degree도 늘어나다가 모든 process들이 page fault 당해서 CPU 이용률이 갑자기 낮아지는 상태 -> Trashing (processor가 user instruction 실행보다 swapping pieces에 대부분의 시간을 사용함)
 memory에 들어와있는 모든 process의 locality 크기와 working set size가 memory 크기보다 크면 trashing이 일어난다. 이에대한 해결은 memory의 process 수를 줄이는 것이다. -> Process Suspension

Page-Fault Frequency Scheme
 page-fault rate가 upper bound보다 크다는 것은 page-fault를 너무 자주 당한다는 것이다. -> 해당 process에 공간을 더 준다. (frame 갯수를 늘인다.)
 page-fault rate가 lower bound보다 작다는 것은 다른 process보다 page-fault를 적게 당한다는 것이다. -> frame 갯수를 줄인다. 다른 애들한테도 골고루 공간을 주기 위함.
 lower bound - upper bound 사이가 되도록 하는 것이 page-fault Frequency Scheme이다.