Page Replacement
- Page Fault가 낮을 수록 좋다.
OPT
- 최적 페이지 교체
- 전제조건 : 프로세스가 앞으로 사용할 페이지를 미리 알아야 한다.
- page를 뽑는데 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체
- Belady's Algorithm
- 실제 구현 불가
FIFO
- 메모리에 올라온지 가장 오래된 페이지를 교체
LRU
- Leas Recently Used
- 가장 오래 사용되지 않은 페이지를 교체
- 과거의 데이터를 바탕으로 페이지가 사용될 시간 예측하여 교체
- OPT와 비슷한 효과를 낼 수 있는 방법
- 메모리를 더 줄수록 page fault가 늘어나진 않는다. 성능이 똑같거나 나아진다.
- n frames는 n+1 frames에 포함된다.
Implementation
Linked List : 단점 : 메모리 참조할 때마다 ovehead 장점 : 접근은 편하다.
Clock or count : 참조할때마다 count 증가, count값이 가장 작은 것을 뺀다. 장점 : page를 참조할 때마다 MMU가 clock count만 보면 됨.
단점 : 누군가 빼려면 clock값이 가장 작은 것을 찾아야함. 메모리 스캔 문제
LRU Approximation Algorithms
- 페이지 참조가 있을 때마다 하드웨어가 그 페이지에 대한 참조 비트 설정
- Additional-Reference-Bits Algorithm
- 일정한 간격마다 참조 비트를 기록
- page 참조마다 모든 page의 reference bit를 shifg
- 가장 작은 값을 가지는 page가 replacement의 대상
value를 저장할 수 있는 table이 있고 각각 page table에는 reference bit가 있고 주기적으로 운영체제가 reference bit를 table로 shift하고 옛날꺼부터 빠져주고 새로운 것은 넣고 원래 reference bit은 0으로 clear하면서 반복한다.
- Second-Chance Algorithm
- reference bit가 1이면 0으로 바꾸어서 넘어가고 0이면 해당 page를 victim으로 결정
- page가 참조되면 reference bit가 1이 되므로 replace할 page를 찾을 때는 page를 거쳐가며 확인하면서 referece bit를 0으로 만든다.
- 시계방향으로 탐색
- address space를 circular하게 놓는다.
Enhanced Second-Change Algorithm
- Reference bit와 Modify bit를 둘 다 사용
- 입/출력 횟수를 줄이기 위해 변경된 페이지에 우선 순위를 준다.
- 교체될 페이지를 찾기까지 여러 번의 순환 큐를 검사할 수 있다.
- 두 비트가 모두 0일때 replace되기에 좋은 page이다.
Counting-Based Page Replacement
- 페이지 참조 시마다 각 페이지가 현재까지 참조된 횟수를 카운팅하는 방법
- LFU(Least Frequently Used)
- 참조 횟수가 가장 작은 페이지 교체
- 교체 대상인 페이지가 여러 개일 경우, LRU 알고리즘을 따라 가장 오래 사용되지 않은 페이지로 교체
- MFU(Most Frequently Used)
- 참조 횟수가 가장 많은 페이지를 교체
=> 문제점 : 구현 비용이 많이 들고, OPT만큼 유사하게 구현해내지 못한다.
