[OS] 페이지 교체 알고리즘

페이지 교체 알고리즘

페이지 교체 알고리즘을 살펴보기 전에 Page reference string 이라는 용어를 알아야 한다. CPU가 내는 주소는 이진수 단위이지만, 페이지 교체 알고리즘을 계산하기 위해서는 이진수 주소 단위가 아닌 페이지 단위로 계산해야한다.

 

CPU가 내는 주소를 간단히 십진수로 {100, 101, 102, 432, 612, 103, 104, 611, 612}라고 하자. 만약 페이지 크기가 100bytes 라면, 위 주소를 페이지 번호로 나타내면 {1, 1, 1, 4, 6, 1, 1, 6, 6}이다. 주소 100번지는 1번 페이지에서 offset이 0 인 위치이고, 101은 1번 페이지의 offset 1인 위치라고 볼 수 있다.

 

마지막으로 페이지 번호로 나타낸 것을 page reference string으로 나타내면 {1, 4, 6, 1, 6}이다. 이는 간단히 말하면 연속된 페이지는 생략하고 하나의 페이지 번호만 나타낸 것으로 볼 수 있다. 이 이유는 연속된 페이지를 참조할 때는 한번 page fault가 발생하면 같은 페이지를 사용하는 동안에는 절대 page fault가 발생할 수 없기 때문이다.

 

정리하자면 page size가 100일 때 아래와 같이 요약할 수 있다.

CPU 주소 = {100, 101, 102, 432, 612, 103, 104, 611, 612}
Page 번호 = {1, 1, 1, 4, 6, 1, 1, 6, 6}
Page reference string = {1, 4, 6, 1, 6}

1. First In First Out(FIFO)

예제

페이지 참조열 (page reference string) : {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 7, 0, 1}

프레임 개수(number of frame) : 3

 

조건은 위와 같고 최초의 메모리는 비어있는 상태이다.

 

 

   0. 프레임 상태 : {}

1. Page-in: 7 => 프레임 상태: {7} Page fault 수: 1 First Page: 7
2. Page-in: 0 => 프레임 상태: {7, 0} Page fault 수: 2 First Page: 7
3. Page-in: 1 => 프레임 상태: {7, 0, 1} Page fault 수: 3 First Page: 7
4. Page-in: 2 => 프레임 상태: {2, 0, 1} Page fault 수: 4 Page-out: 7 First Page: 0
5. Page-in: 0 => 프레임 상태: {2, 0, 1} Page fault 수: 4 First Page: 0
6. Page-in: 3 => 프레임 상태: {2, 3, 1} Page fault 수: 5 Page-out: 0 First Page: 1
7. Page-in: 0 => 프레임 상태: {2, 3, 0} Page fault 수: 6 Page-out: 1 First Page: 2
8. Page-in: 4 => 프레임 상태: {4, 3, 0} Page fault 수: 7 Page-out: 2 First Page: 3
9. Page-in: 2 => 프레임 상태: {4, 2, 1} Page fault 수: 8 Page-out: 3 First Page: 1
10. Page-in: 3 => 프레임 상태: {4, 2, 3} Page fault 수: 9 Page-out: 1 First Page: 4
11. Page-in: 0 => 프레임 상태: {0, 2, 3} Page fault 수: 10 Page-out: 4 First Page: 2
12. Page-in: 3 => 프레임 상태: {0, 2, 3} Page fault 수: 10 First Page: 2
13. Page-in: 2 => 프레임 상태: {0, 2, 3} Page fault 수: 10 First Page: 2
14. Page-in: 1 => 프레임 상태: {0, 1, 3} Page fault 수: 11 Page-out: 2 First Page: 3
15. Page-in: 2 => 프레임 상태: {0, 1, 2} Page fault 수: 12 Page-out: 3 First Page: 0
16. Page-in: 0 => 프레임 상태: {0, 1, 2} Page fault 수: 12 First Page: 0
17. Page-in: 7 => 프레임 상태: {7, 1, 2} Page fault 수: 13 Page-out: 0 First Page: 1
18. Page-in: 0 => 프레임 상태: {7, 0, 2} Page fault 수: 14 Page-out: 1 First Page: 2
19. Page-in: 1 => 프레임 상태: {7, 0, 1} Page fault 수: 15 Page-out: 2 First Page: 7

결과는 최종 page fault 수는 15이다. 예제를 수행하며 이전에 page-out한 페이지를 그 다음 바로 page-in 하려면 다시 page fault가 발생하므로 비효율적인 것을 볼 수 있다.

 

Belady's Anomaly

프레임 수가 증가하면(== 메모리 용량이 증가하면) page fault 수가 줄어드는 것이 정상적이나 특정한 페이지 참조열에 대해서는 프레임 수가 증가해도 page fault 수가 오히려 증가하는 이상 현상이 발생한다. 이를 belady's anomaly라 한다.

2. Optimal(OPT)

OPT는 가장 효율적인 페이지 교체 알고리즘이다. 이 알고리즘은 가장 오랫동안 사용되지 않을 페이지를 victim page로 선택한다.

 

예제

페이지 참조열 (page reference string) : {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 7, 0, 1}

프레임 개수(number of frame) : 3

 

여기서 가장 오랫동안 사용되지 않을 페이지를 계산하기 위해 현재 시점에서 그 이후에 최초로 나타나는 시점의 거리를 dist로 둔다. 이 값이 가장 큰 페이지가 가장 오랫동안 사용되지 않은 페이지로 정한다. (해당 페이지가 이후에 나오지 않는 경우는 INF로 가장 큰 값으로 한다.)

 

 

   0. 프레임 상태 : {}

1. Page-in: 7 => 프레임 상태: {7} Page fault 수: 1 dist: {15}
2. Page-in: 0 => 프레임 상태: {7, 0} Page fault 수: 2 dist: {14, 3}
3. Page-in: 1 => 프레임 상태: {7, 0, 1} Page fault 수: 3 dist: {13, 2, 11}
4. Page-in: 2 => 프레임 상태: {2, 0, 1} Page fault 수: 4 Page-out: 7 dist: {5, 1, 10}
5. Page-in: 0 => 프레임 상태: {2, 0, 1} Page fault 수: 4 dist: {4, 2, 9}
6. Page-in: 3 => 프레임 상태: {2, 0, 3} Page fault 수: 5 Page-out: 1 dist: {3, 1, 4}
7. Page-in: 0 => 프레임 상태: {2, 0, 3} Page fault 수: 5 dist: {2, 4, 3}
8. Page-in: 4 => 프레임 상태: {2, 4, 3} Page fault 수: 6 Page-out: 0 dist: {1, INF, 2}
9. Page-in: 2 => 프레임 상태: {2, 4, 3} Page fault 수: 6 dist: {4, INF, 1}
10. Page-in: 3 => 프레임 상태: {2, 4, 3} Page fault 수: 6 dist: {3, INF, 2}
11. Page-in: 0 => 프레임 상태: {2, 0, 3} Page fault 수: 7 Page-out: 4 dist: {2, 5, 1}
12. Page-in: 3 => 프레임 상태: {2, 0, 3} Page fault 수: 7 dist: {1, 4, INF}
13. Page-in: 2 => 프레임 상태: {2, 0, 3} Page fault 수: 7 dist: {2, 3, INF}
14. Page-in: 1 => 프레임 상태: {2, 0, 1} Page fault 수: 8 Page-out: 3 dist: {1, 2, 5}
15. Page-in: 2 => 프레임 상태: {2, 0, 1} Page fault 수: 8 dist: {INF, 1, 4}
16. Page-in: 0 => 프레임 상태: {2, 0, 1} Page fault 수: 8 dist: {INF, 2, 3}
17. Page-in: 7 => 프레임 상태: {7, 0, 1} Page fault 수: 9 Page-out: 2 dist: {INF, 1, 2}
18. Page-in: 0 => 프레임 상태: {7, 0, 1} Page fault 수: 9 dist: {INF, INF, 1}
19. Page-in: 1 => 프레임 상태: {7, 0, 1} Page fault 수: 9 dist: {INF, INF, INF}

OPT의 결과로 총 9번의 page fault가 발생했다. 이는 FIFO의 15번보다 크게 줄어든 모습을 볼 수 있다. 하지만 OPT의 방법은 현실적으로 불가능하다. 실제 컴퓨터에서는 미래에 어떤 프로세스가 사용되는지 알 수 없다. 그러므로 어느 프로세스가 가장 오래 사용 안되는지를 계산할 수가 없다.

3. Least Recently Used(LRU)

OPT는 최적해를 구할 수 있으나 미래에 어떤 프로세스가 사용되는지 알 수 없어 현실적으로 불가능하다. 하지만 근사값을 구하기 위해 LRU가 등장했다. LRU는 최근에 사용되지 않으면 나중에도 사용되지 않을 것이라는 개념으로 과거의 페이지 기록을 통해 victim page를 선택한다. OPT 보다는 page fault 가 많이 발생하지만 FIFO보다는 일반적으로 적게 일어난다. 그래서 현재 대부분 환경에서는 LRU를 사용한다.