Page Replacement Algorithm
Page fault 가 발생했을 때, 즉 페이지 테이블의 valid bit가 0일 경우, 페이지를 메모리로 올릴 공간이 남아있다면 디스크에서 메모리로 페이지를 올리고 테이블을 갱신해준다.
그러나, 해당 페이지를 올릴 메모리 공간이 없고, 메모리에 있는 페이지의 일부를 디스크에 내보내고, 해당 페이지를 메모리에 올려야 한다. (page out -> page int)
이때 어떤 페이지를 메모리 밖으로 내보낼 것인지 정하는 알고리즘이 Page replacement Algorithm에 해당된다.
- FIFO
First In First Out을 줄여 FIFO이다. 선입선출 방식.
시간과 우선 순위와 관련된 데이터를 정리하고 이용하는 방식을 말한다.
말 그대로 가장 먼저 적재된 페이지를 가장 먼저 내보내는 것이다. (Queue 사용)
단점: 오래 전에 적재되어 반복적으로 사용되는 페이지가 교체 될 수도 있다.
Belady의 이상현상 발생 : 프로세스의 더 많은 수의 페이지 프레임을 할당할 경우 오히려 Page fault가 더 많이 발생할 수 있다. - LRU 페이지 교체
Least Recently Used의 줄임말.
가장 오랫동안 사용되지 않은 페이지를 교체하는 방법이다. (참조 시간, 링크드리스트를 사용)
페이지가 참조되 때마다 그때의 시간을 기록하고, 참조시간이 가장 오래된 페이지를 교체한다.
페이지가 참조되면 리스트의 선두로 옮기고, 리스트의 끝에 있는 페이지를 교체한다.
-LRU 사용시 FIFO를 사용했을 때 발생했던 Belady와 같은 현상이 발생하지 않으며, 많은 경우 최적화 원칙에 가장 알맞는 선택을 할 수 있다.
단점: 경험적 판단이 맞지 않는 상황도 존재하고, 오버헤드가 발생할 가능성이 높다.
