[운영체제(OS)] 16. 페이지 교체 알고리즘

SungBum Park·2020년 2월 5일

운영체제 KOCW 양희재 교수님 강의 정리

목록 보기

16/19

페이지 교체 알고리즘을 살펴보기 전에 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 = 100bytes 일때

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)

FIFO은 가장 간단한 알고리즘이다. 가장 먼저 page-in 한 페이지를 먼저 page-out 시킨다. 이를 사용한 이유는 초기화 코드가 더 이상 사용되지 않을 것이라는 아이디어에서 시작되었다.

1.1. 예제

페이지 참조열(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
조건은 위와 같고 최초의 메모리는 비어있는 상태이다.

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	7	0	1

```
           프레임 상태: {}
```
Page-in: 7 => 프레임 상태: {7} Page fault 수: 1 First Page: 7
Page-in: 0 => 프레임 상태: {7, 0} Page fault 수: 2 First Page: 7
Page-in: 1 => 프레임 상태: {7, 0, 1} Page fault 수: 3 First Page: 7
Page-in: 2 => 프레임 상태: {2, 0, 1} Page fault 수: 4 Page-out: 7 First Page: 0
Page-in: 0 => 프레임 상태: {2, 0, 1} Page fault 수: 4 First Page: 0
Page-in: 3 => 프레임 상태: {2, 3, 1} Page fault 수: 5 Page-out: 0 First Page: 1
Page-in: 0 => 프레임 상태: {2, 3, 0} Page fault 수: 6 Page-out: 1 First Page: 2
Page-in: 4 => 프레임 상태: {4, 3, 0} Page fault 수: 7 Page-out: 2 First Page: 3
Page-in: 2 => 프레임 상태: {4, 2, 1} Page fault 수: 8 Page-out: 3 First Page: 1
Page-in: 3 => 프레임 상태: {4, 2, 3} Page fault 수: 9 Page-out: 1 First Page: 4
Page-in: 0 => 프레임 상태: {0, 2, 3} Page fault 수: 10 Page-out: 4 First Page: 2
Page-in: 3 => 프레임 상태: {0, 2, 3} Page fault 수: 10 First Page: 2
Page-in: 2 => 프레임 상태: {0, 2, 3} Page fault 수: 10 First Page: 2
Page-in: 1 => 프레임 상태: {0, 1, 3} Page fault 수: 11 Page-out: 2 First Page: 3
Page-in: 2 => 프레임 상태: {0, 1, 2} Page fault 수: 12 Page-out: 3 First Page: 0
Page-in: 0 => 프레임 상태: {0, 1, 2} Page fault 수: 12 First Page: 0
Page-in: 7 => 프레임 상태: {7, 1, 2} Page fault 수: 13 Page-out: 0 First Page: 1
Page-in: 0 => 프레임 상태: {7, 0, 2} Page fault 수: 14 Page-out: 1 First Page: 2
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는 말그대로 가장 효율적인 페이지 교체 알고리즘이다. 이 알고리즘은 가장 오랫동안 사용되지 않을 페이지를 희생양 페이지로 선택한다.

2.1. 예제

페이지 참조열(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로 가장 큰 값으로 한다.)

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	7	0	1

```
           프레임 상태: {}
```
Page-in: 7 => 프레임 상태: {7} Page fault 수: 1 dist: {15}
Page-in: 0 => 프레임 상태: {7, 0} Page fault 수: 2 dist: {14, 3}
Page-in: 1 => 프레임 상태: {7, 0, 1} Page fault 수: 3 dist: {13, 2, 11}
Page-in: 2 => 프레임 상태: {2, 0, 1} Page fault 수: 4 Page-out: 7 dist: {5, 1, 10}
Page-in: 0 => 프레임 상태: {2, 0, 1} Page fault 수: 4 dist: {4, 2, 9}
Page-in: 3 => 프레임 상태: {2, 0, 3} Page fault 수: 5 Page-out: 1 dist: {3, 1, 4}
Page-in: 0 => 프레임 상태: {2, 0, 3} Page fault 수: 5 dist: {2, 4, 3}
Page-in: 4 => 프레임 상태: {2, 4, 3} Page fault 수: 6 Page-out: 0 dist: {1, INF, 2}
Page-in: 2 => 프레임 상태: {2, 4, 3} Page fault 수: 6 dist: {4, INF, 1}
Page-in: 3 => 프레임 상태: {2, 4, 3} Page fault 수: 6 dist: {3, INF, 2}
Page-in: 0 => 프레임 상태: {2, 0, 3} Page fault 수: 7 Page-out: 4 dist: {2, 5, 1}
Page-in: 3 => 프레임 상태: {2, 0, 3} Page fault 수: 7 dist: {1, 4, INF}
Page-in: 2 => 프레임 상태: {2, 0, 3} Page fault 수: 7 dist: {2, 3, INF}
Page-in: 1 => 프레임 상태: {2, 0, 1} Page fault 수: 8 Page-out: 3 dist: {1, 2, 5}
Page-in: 2 => 프레임 상태: {2, 0, 1} Page fault 수: 8 dist: {INF, 1, 4}
Page-in: 0 => 프레임 상태: {2, 0, 1} Page fault 수: 8 dist: {INF, 2, 3}
Page-in: 7 => 프레임 상태: {7, 0, 1} Page fault 수: 9 Page-out: 2 dist: {INF, 1, 2}
Page-in: 0 => 프레임 상태: {7, 0, 1} Page fault 수: 9 dist: {INF, INF, 1}
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는 최근에 사용되지 않으면 나중에도 사용되지 않을 것이라는 개념으로 과거의 페이지 기록을 통해 희생양 페이지를 선태한다.