Page Replacement Algorithm

페이지 교체 알고리즘에 대해 알아본다.

1. Page reference string

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

|CPU 논리 주소|요청할 페이지 번호| |:-------:--------|:--------:----------------| |100|1| |101|1| |432|4| |612|6| |103|1| |104|1| |611|6| |612|6|

예를 들어, CPU가 내는 주소를 위와 같이 표현해보자. 편의를 위해 주소는 십진수로 표현했다. 만약 페이지 크기를 100이라 하면, 우측과 같이 된다. 주소 100번지는 1번 페이지에서 offset이 0인 위치이고, 101은 1번 페이지의 offset 1인 위치라고 볼 수 있다.

마지막으로 페이지 번호로 나타낸 것을 page reference string으로 나타내면 {1, 4, 6, 1, 6}이다. 이는 간단히 말하면 연속된 페이지는 생략하고 하나의 페이지 번호만 나타낸 것으로 볼 수 있다. 이 이유는 연속된 페이지를 참조할 때는 한 번 page fault가 발생하면 같은 페이지를 사용하는 동안에는 절대 page fault가 발생할 수 없기 때문이다. 즉, CPU가 가리키는 page의 번호가 연속적으로 동일하다면, disk로 가서 page를 가져올 필요가 없으므로, 위의 번호들만 가지고 판단하는 것이 바람직하다.

2. First-In First-Out(FIFO)

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

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
• 최초의 메모리는 비어있는 상태이다.

|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|

order	page-in	frame states	Page fault count	page-out	first page
1	7	{7}	1		7
2	0	{7, 0}	2		7
3	1	{7, 0, 1}	3		7
4	2	{2, 0, 1}	4	7	0
5	0	{2, 0, 1}	4		0
6	3	{2, 3, 1}	5	0	1
7	0	{2, 3, 0}	6	1	2
8	4	{4, 3, 0}	7	2	3
9	2	{4, 2, 1}	8	3	1
10	3	{4, 2, 3}	9	1	4
11	0	{0, 2, 3}	10	4	2
12	3	{0, 2, 3}	10		2
13	2	{0, 2, 3}	10		2
14	1	{0, 1, 3}	11	2	3
15	2	{0, 1, 2}	12	3	0
16	0	{0, 1, 2}	12		0
17	7	{7, 1, 2}	13	0	1
18	0	{7, 0, 2}	14	1	2
19	1	{7, 0, 1}	15	2	7

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

2.2 Belady’s Anomaly

프레임 수가 증가하면(= 메모리 용량이 증가하면) page fault 수가 줄어드는 것이 정상적이다.

하지만 위의 FIFO를 사용했을 때, 그래프를 그려보면 다음과 같은 결과가 나온다.

이와 같이 특정한 페이지 참조열에 대해서는 프레임 수가 증가해도 page fault 수가 오히려 증가하는 이상 현상이 발생한다. 이를 Belady’s Anomaly라 한다.

3. Optimal(OPT)

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

3.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|

order	page-in	frame states	Page fault count	page-out	dist
1	7	{7}	1		{15}
2	0	{7, 0}	2		{14, 3}
3	1	{7, 0, 1}	3		{13, 2, 11}
4	2	{2, 0, 1}	4	7	{5, 1, 10}
5	0	{2, 0, 1}	4		{4, 2, 9}
6	3	{2, 0, 3}	5	1	{3, 1, 4}
7	0	{2, 0, 3}	5		{2, 4, 3}
8	4	{2, 4, 3}	6	0	{1, INF, 2}
9	2	{2, 4, 3}	6		{4, INF, 1}
10	3	{2, 4, 3}	6		{3, INF, 2}
11	0	{2, 0, 3}	7	4	{2, 5, 1}
12	3	{2, 0, 3}	7		{1, 4, INF}
13	2	{2, 0, 3}	7		{2, 3, INF}
14	1	{2, 0, 1}	8	3	{1, 2, 5}
15	2	{2, 0, 1}	8		{INF, 1, 4}
16	0	{2, 0, 1}	8		{INF, 2, 3}
17	7	{7, 0, 1}	9	2	{INF, 1, 2}
18	0	{7, 0, 1}	9	1	{INF, INF, 1}
19	1	{7, 0, 1}	9	2	{INF, INF, INF}

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

4. Least-Recently-Used(LRU)

OPT는 최적해를 구할 수 있지만 미래를 알 수 없으므로 현실적으로 불가능한 방법이었는데, 최적의 해는 아니더라도 근사의 해를 구하기 위해서 LRU가 나왔다. LRU는 최근에 사용되지 않으면 나중에도 사용되지 않을 것이라는 개념으로 과거의 페이지 기록을 통해 희생양 페이지를 선택한다.

4.1 예제

LRU는 근사 해를 구하므로 OPT보다는 page fault가 많이 발생하지만, FIFO보다는 일반적으로 적게 일어난다. 그러므로 현재 대부분 환경에서는 LRU를 사용하고 있다.

Reference

• KOCW 양희재 교수님 - 운영체제
• 양희재 교수님 블로그(시험 기출 문제)
• codemcd 님의 정리글
• 세마포 사진
• Operating System Concepts, 9th Edition - Abraham Silberschatz