페이지 교체기법 (page replacement strategy)
새로이 적재되어야 할 페이지를 위해 기존의 어느 페이지가 주기억장치로부터 제거되어야 할지를 결정하는 전략
1. 최적화 원칙 (principle of optimality, 최적 교체)
* 최적의 성과를 얻기 위해서 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 기법
* 예측이 맞지 않을 경우가 발생되므로 실현 가능성이 낮은 기법이다
* OPT, MIN 등의 방법이 있다
2. 무작위 페이지 교체 (random page replacement)
* 무작위하게 어떤 페이지든지 교체될 수 있는 방법
* 최악의 경우 바로 참조될 페이지가 교체될 수도 있기 때문에 거의 사용하지 않는다
3. FIFO (First In First Out) 페이지 교체
* 가장 먼저 들어온 페이지를 교체하는 방법
* 각 페이지가 주기억장치로 들어올 때 마다 타임 스탬프를 찍어 그 시간을 기억하고 있다가 페이지 교체 요청시 가장 먼저 주기억장치에 들어온 페이지를 교체한다.
* 벨레이디의 모순 (Belady's anomaly)
* 페이지 프레임 수가 증가하면 페이지 부재가 더 증가되는 현상이 발생한다
4. LRU (Least Recently Used) 페이지 교체기법
* 최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법
* 각 페이지마다 계수기를 두어 교체시점에서 가장 오래 전에 사용된 페이지를 교체하는 방법
5. LFU (Least Frequently Used) 페이지 교체기법
* 페이지의 호출 빈도수가 가장 적은 페이지를 교체하는 기법
6. NUR (Not Used Recently) 페이지 교체기법
* 최근에 사용하지 않은 페이지를 교체하는 기법
* 각 페이지마다 2개의 하드웨어 비트 (호출 비트, 변형 비트)가 사용된다
* 호출 비트는 최근 참조를, 변형 비트는 최근 변형을 체크하여 가장 최근에 참조도 안 되고 변형도 안 된 페이지를 우선교체 한다
| 페이지 |
1 |
2 |
3 |
4 |
| 호출(참조)비트 |
0 |
0 |
1 |
1 |
| 변형 비트 |
0 |
1 |
0 |
1 |
| 교체 순서 |
1 |
2 |
3 |
4 |
7. 2차 기회 페이지 교체기법
* FIFO 기법의 단점을 보완하는 기법
* 가장 오랫동안 주기억장치에 있던 페이지 중 사용되는 페이지의 교체를 방지하기 위함
* 가장 오래된 페이지의 참조 비트를 조사하여 비트가 Off(0)이라면 페이지 교체
8. 클록 페이지 교체기법
* 2차 기회 알고리즘의 변형.
* 선형 리스트 대신 원형 리스트를 사용하여 페이지를 배열시켜 놓아 리스트의 포인터가 시계바늘처럼 그 원형 리스트를 돌아가게 하는 것
