Page Replacement 알고리즘
Page Fault 가 발생하면 OS는 프로세서가 요구하는 워드를 포함한 페이지를 하드디스크로부터 물리메모리(메인메모리)로 이동시키는 데, 이때 이미 메인 메모리에 저장되어 있던 page를 교체하는 방법
가상메모리 시스템 중 교체 알고리즘에 대한 예제
FIFO, LRU, Clock 세 가지
|
HIT |
USED |
FIFO교체
메모리 내에 가장 오랫동안 있었던 페이지를 교체하는 알고리즘이다. 이 방법은 가장 오래전에 적재된페이지가 다시 사용될 확률이 적다는 논리를 이용해서, 메모리에 가장 오래 있었던 페이지를 교체하는 것이다. 각 페이지가 주기억장치에 적재될 때마다 그때의 시간을 기억시켜 둬야 한다.
2, 3, 4, 2, 6, 2, 5, 6, 1, 2 페이지에 대한 요청
|
요청 |
2 |
3 |
4 |
2 |
6 |
2 |
5 |
6 |
1 |
2 |
|
PF0 |
2 |
2 |
2 |
2 |
6 |
6 |
6 |
6 |
1 |
1 |
|
PF1 |
|
3 |
3 |
3 |
3 |
2 |
2 |
2 |
2 |
2 |
|
PF2 |
|
|
4 |
4 |
4 |
4 |
5 |
5 |
5 |
5 |
적중률은 3/10 = 30% 이다.
LRU교체
메모리 내에 적재된 페이지 중에서 사용되지 않은 채 가장 오래 있었던 페이지를 교체하는 알고리즘이다. 각 페이지가 참조될 때마다 그때의 시간을 테이블에 기억시켜 두고, 페이지가 교체될 때마다 가장 오랫동안 있었던 페이지를 교체한다. 지역성의 원리를 따른다면, 이 페이지는 향후 참조될 가능성이 가장 적을 것으로 판단된다. 구현이 어려우며, 참조될 때마다 시간을 기억하는 것은 오버헤드가 많다.
|
요청 |
2 |
3 |
4 |
2 |
6 |
2 |
5 |
6 |
1 |
2 |
|
PF0 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
1 |
1 |
|
PF1 |
|
3 |
3 |
3 |
6 |
6 |
6 |
6 |
6 |
6 |
|
PF2 |
|
|
4 |
4 |
4 |
4 |
5 |
5 |
5 |
2 |
적중률은 3/10 = 30% 이다.
Clock교체
FIFO알고리즘을 수정한 것으로서, 주기억장치 내에 적재된 페이지의 시간과 사용빈도를 고려한다. 그래서 이 교체 방법을 FINUFO라고도 한다. 이 방법을 구현하는 데는 페이지 사용을 나타내는 사용 비트와 페이지가 적재되는 위치를 나타내는 포인터가 사용된다.
|
Pnt |
Pnt+1 |
|
REQ |
2 |
|
3 |
|
2 |
|
4 |
|
6 |
|
2 |
|
5 |
|
6 |
|
1 |
|
4 |
|
6 |
|
|
PF0 |
0 |
2 |
0 |
2 |
1 |
2 |
1 |
2 |
0 |
2 |
1 |
2 |
1 |
2 |
1 |
2 |
0 |
2 |
0 |
4 |
0 |
4 |
|
PF1 |
|
|
0 |
3 |
0 |
3 |
0 |
3 |
0 |
6 |
0 |
6 |
0 |
6 |
1 |
6 |
0 |
6 |
0 |
6 |
1 |
6 |
|
PF2 |
|
|
|
|
|
|
0 |
4 |
0 |
4 |
0 |
4 |
0 |
5 |
0 |
5 |
0 |
1 |
0 |
1 |
0 |
1 |
Clock 알고리즘은 사용비트가 1이면 사용 비트를 0으로 변경 후 포인터를 증가시킨다. 새로운 포인터가 가리키는 곳에 Page가 변경이 되면 포인터를 다시 증가시킨다. Hit시에는 포인터가 증가하지 않음
적중률은 4/11 = 36% 이다.