페이지 교체 알고리즘

1. 페이지 교체 알고리즘이란

- 페이지 부재가 발생하여 새로운 페이지를 할당하여야하는 상황에서 현재 할당된 페이지 중 어떤 것으로 교체할 지 결정하는 방법

1. 가상메모리는 요구 페이지 기법을 통해 필요한 페이지만 메모리에 적재함.
2. 하지만 필요한 페이지만 올려도 메모리는 가득차게 될 수 있음.
3. 이때 추가로 페이지를 가져오기 위해 안쓰는 페이지는 out, 해당 공간에 현재 필요한 페이지를 in 해야함.
4. 여기서 어떠한 페이지를 out 해야할 지(victim page) 정하는 방식이 페이지 교체 알고리즘이다.
   • 기왕이면 수정이 되지 않는 페이지를 선택하는 것이 좋음 (만약 수정되면 메인 메모리에서 내보낼 때, 하드디스크에서 또 수정을 해야하므로 시간이 오래 걸리게 되기 때문)

2. Page Reference String(페이지 참조열)

• 페이지 교체 알고리즘을 계산하기 위해서는 페이지 단위로 계산해야 함.
• 하지만 CPU가 내는 주소는 이진수 단위이므로 페이지 단위로 변형해야 함.
• Page Reference String은 연속된 페이지는 생략하고 하나의 페이지 번호로만 나타낸 것

- CPU가 내는 주소 = {100, 101, 102, 402, 692, 103, 104, 611, 612}

if 페이지의 크기 = 100 bytes
- 페이지 주소 = {1, 1, 1, 4, 6, 1, 1, 6, 6}
- Page Reference String = {1, 4, 6, 1, 6}

---

3. 페이지 교체 알고리즘 종류(FIFO, OPT, LRU)

1) FIFO(First-In First-Out) : 가장 먼저 page-in한 페이지 순으로 out 시킨다.

• Page Reference String : {7,0,1,2,0,7,0,1,2,3}

• 프레임 개수 : 3

  번호	1	2	3	4	5	6	7	8	9	10
  PRS	7	0	1	2	0	7	0	1	2	3
  status	7	7 0	7 0 1	2 0 1	2 0 1	2 7 1	2 7 0	1 7 0	1 2 0	1 2 3
  Page Fault	1	2	3	4	4	5	6	7	8	9

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

- Belady's Anomaly

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

2) OPT(Optimal) : 가장 오랫동안 사용되지 않을 페이지를 out 시킨다.

• 가장 오랫동안 사용되지 않을 페이지를 계산하기 위해 현재 시점에서 그 이후에 최초로 나타나는 시점의 거리를 distance로 두어 계산한다. distance가 가장 큰 페이지를 교체하는 규칙. (해당 페이지가 이후에 나오지 않는 경우는 INF로 지정한다.)

  번호	1	2	3	4	5	6	7	8	9	10
  PRS	7	0	1	2	0	7	0	1	2	3
  status	7	7 0	7 0 1	7 0 2	7 0 2	7 0 2	7 0 2	1 0 2	1 0 2	1 3 2
  distance	5	4 3	3 2 5	2 1 5	1 2 4	INF 1 3	INF INF 2	INF INF 1	INF INF INF	INF INF INF
  Page Fault	1	2	3	4	4	4	4	5	5	6

• 최종 page fault는 6, FIFO와 비교했을 때 많이 줄어든 모습을 볼 수 있으나 현실적으로 OPT의 방법은 불가능하다. 실제 컴퓨터에서는 미래에 어떤 프로세스가 사용될 지 알 수 없으므로 어느 프로세스가 가장 오래 사용되지 않는 지를 계산할 수 없다.

3) LRU(Least-Recently-Used) : 최근에 사용되지 않은 page를 out시킨다.

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

  번호	1	2	3	4	5	6	7	8	9	10
  PRS	7	0	1	2	0	7	0	1	2	3
  status	7	7 0	7 0 1	2 0 1	2 0 1	2 0 7	2 0 7	1 0 7	1 0 2	1 3 2
  Page Fault	1	2	3	4	4	5	5	6	7	8

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