페이지 교체 알고리즘
페이지 참조열 (Page Reference String)
CPU가 내는 주소가 {100, 101, 102, 432, 612, 103, 104, 611, 612} 이고, 페이지 사이즈가 100바이트라고 하자.
CPU가 내는 주소를 페이지 번호로 나타내보면 {1, 1, 1, 4, 5, 1, 1, 6, 6} 이다.
한 페이지에 100바이트 씩 들어가므로, 100 ~ 199는 1 페이지, 200 ~ 299는 2 페이지, ...
페이지 참조열 (Page Reference String)은 페이지 번호 중에서 중복값을 제거한 값들이다. 한번 Page Fault가 발생하면 같은 페이지를 사용하는 동안에는 해당 페이지에서 절대로 페이지 부재가 일어나지 않기 때문이다.
따라서 주어진 예시의 페이지 참조열 (Page Reference String) 은 {1, 4, 6, 1, 6} 이다.
First-In First-Out (FIFO)
흔히 말하는 선입 선출의 개념이다.
한번 초기화된 코드는 더이상 사용되지 않을 것이라는 아이디어에서 시작된 매우 간단한 알고리즘이다.
페이지 참조열 : {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1}
프레임 개수 : 3| Page In | 프레임 상태 | Page fault 횟수 | Page Out | First Page |
|---|---|---|---|---|
| 7 | {7} | 1 | - | 7 |
| 0 | {7, 0} | 2 | - | 7 |
| 1 | {7, 0, 1} | 3 | - | 7 |
| 2 | {2, 0, 1} | 4 | 7 | 0 |
| 0 | {2, 0, 1} | 4 | - | 0 |
| 3 | {2, 3, 1} | 5 | 0 | 1 |
| 0 | {2, 3, 0} | 6 | 1 | 2 |
| 4 | {4, 3, 0} | 7 | 2 | 3 |
| 2 | {4, 2, 1} | 8 | 3 | 1 |
| 3 | {4, 2, 3} | 9 | 1 | 4 |
| 0 | {0, 2, 3} | 10 | 4 | 2 |
| 3 | {0, 2, 3} | 10 | - | 2 |
| 2 | {0, 2, 3} | 10 | - | 2 |
| 1 | {0, 1, 3} | 11 | 2 | 3 |
| 2 | {0, 1, 2} | 12 | 3 | 0 |
| 0 | {0, 1, 2} | 12 | - | 0 |
| 7 | {7, 1, 2} | 13 | 0 | 1 |
| 0 | {7, 0, 2} | 14 | 1 | 2 |
| 1 | {7, 0, 1} | 15 | 2 | 7 |
총 Page Fault : 15
FIFO는 바로 직전에 Page Out 된 페이지를 그 다음에 바로 Page In하게 되면 Page Fault가 발생하므로 비효율적이라고 볼 수 있다.
Belady's Anomaly
프레임 수 (메모리 용량)가 증가하면 Page Fault가 감소할 것으로 예상되지만, 어떤 경우에는 프레임 수가 증가했는데 Page Fault 수가 더 증가하는 경우가 있다.
Optimal (OPT)
가장 효율적인 알고리즘이다. 앞으로 가장 오랫동안 사용되지 않을 것 같은 페이지를 교체한다.
이 때 앞으로 가장 오랫동안 사용되지 않을 것 같은 페이지는 현재 위치해있는 페이지의 값이, 그 이후 가장 처음 등장하는 위치와의 거리로 계산한다. 앞으로 값이 나오지 않는다면 가장 큰 값으로 한다.
페이지 참조열 : {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1}
프레임 개수 : 3| Page In | 프레임 상태 | Page fault 횟수 | Page Out | Dist |
|---|---|---|---|---|
| 7 | {7} | 1 | - | {15} |
| 0 | {7, 0} | 2 | - | {14, 3} |
| 1 | {7, 0, 1} | 3 | - | {13, 2, 11} |
| 2 | {2, 0, 1} | 4 | 7 | {5, 1, 10} |
| 0 | {2, 0, 1} | 4 | - | {4, 2, 9} |
| 3 | {2, 0, 3} | 5 | 1 | {3, 1, 4} |
| 0 | {2, 0, 3} | 5 | - | {2, 4, 3} |
| 4 | {2, 4, 3} | 6 | 0 | {1, INF, 2} |
| 2 | {2, 4, 3} | 6 | - | {4, INF, 1} |
| 3 | {2, 4, 3} | 6 | - | {3, INF, 2} |
| 0 | {2, 0, 3} | 7 | 4 | {2, 5, 1} |
| 3 | {2, 0, 3} | 7 | - | {1, 4, INF} |
| 2 | {2, 0, 3} | 7 | - | {2, 3, INF} |
| 1 | {2, 0, 1} | 8 | 3 | {1, 2, 5} |
| 2 | {2, 0, 1} | 8 | - | {INF, 1, 4} |
| 0 | {2, 0, 1} | 8 | - | {INF, 2, 3} |
| 7 | {7, 0, 1} | 9 | 2 | {INF, 1, 2} |
| 0 | {7, 0, 1} | 9 | - | {INF, INF, 1} |
| 1 | {7, 0, 1} | 9 | - | {INF, INF, INF} |
총 Page Fault : 9
FIFO에 비해 Page Fault는 확연히 줄어들었다. 하지만 OPT는 비현실적인 방법이다. 왜냐하면 미래에 어떤 프로세스를 사용할지는 아무도 모르기 때문이다. 사용하지 않을 것 같아서 Page Out한 페이지가 예상치 못하게 필요할 경우가 생기기 마련이다.
Least-Recently-Used (LRU)
가장 오랜 기간동안 사용되지 않았던 페이지를 교체하는 방법이다. 최근에 사용되지 않으면 나중에도 사용되지 않을 것이라는 아이디어에서 나온 방법으로, 근사값을 활용한다.
마찬가지로
페이지 참조열 : {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1}
프레임 개수 : 3를 분석해보면, 총 12번의 Page Fault가 발생한다.
OPT에 비해서는 Page Fault가 많이 발생하고, FIFO 보다는 적게 발생한다. 하지만 OPT는 비현실적인 방법이므로 대부분의 환경에서는 LRU를 많이 사용한다.
