#24. 페이지 교체(Page replacement)

- Demand Paging

  * 요구되어지는 페이지만 backing store에서 가져온다.

  * 프로그램 실행 계속에 따라 요구 페이지가 늘어나고,

언젠가는 메모리가 가득 차게 된다.

 

- Memory full

  * 메모리가 가득 차면 추가로 페이지를 가져오기 위해 어떤 페이지는 backing store로 몰아내고 (page-out)

  * 그 빈공간으로 페이지를 가져온다 (page-in)

  * 용어 : victim page (기왕이면 modify되지 않는 것)

 

- Victim Page

- 어떤 페이지를 몰아낼 것인가?

  * 시간 절약을 위해 기왕이면 modify되지 않은 페이지를 victim으로 선택 (이때 페이지 별로 modified bit를 두어 수정 여부를 체크 = dirty bit)

 

- Page reference string

  * CPU가 내는 주소 : 100 101 102 432 612 103 104 611 612

  * Page Size : 100 byte

  * 페이지 번호 1 1 1 4 6 ...

(여기서 만약 CPU가 100번지 주소를 냈는데 page default가 발생해서 backing store에서 찾아 와야 하는 상황이 생겼다고 가정해보자. 그렇다면 101주소 부터는 default가 발생하지 않는다. 왜?

page default 발생 시 backing store에서 1번 페이지를 통째로 메모리에 올리기 때문. 즉, 100~199번지 까지 하나의 페이지이고 절대 page default가 발생 할 수 없다. )

 

=> 만약 모든 페이지에서 page default가 발생했다면?

Page reference string = 1 4 6 1 6 이다.

 

- Page Replacement Algorithms

  * FIFO (First-In First-Out)

  * OPT (Optimal)

  * LRU (Least-Recently-Used)

 

 

First-In First-Out (FIFO)

(Victim Page를 메모리에 가장 먼저 올라온 페이지를 희생양으로 삼는다)

- Simplest

  - Idea : 초기화 코드는 더 이상 사용되지 않을 것.

- 예제

  * 페이지 참조열 = 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

  * # of frames = 3

  * 15 page faults

- Belady`s Anomaly

  * 프레임 수 (= 메모리 용량) 증가에 PF 회수 증가?

(7 0 1 은 프레임 3 개만 올릴 수 있는 메모리에 page fault가 발생하여 Page-in이 일어난다.

이후 2번째 페이지를 참조하려고 보니 없어서 page fault가 발생하여 FIFO 알고리즘에 따라 7번째 페이지를 page-out하고 2번 페이지를 page in 한다.

x -> 7 page in

x -> 0 page in

x -> 1 page in

7 page out -> 2 page in

x -> x

0 page out -> 3 page in

1 page out -> 0 page in

....

 

이걸 생각해 보면 0페이지를 page out 하지 않았다면 3번 페이지 이후 다시 0번 페이지를 page in 하는 상황이 생기지 않았을 것이다. 이런 방식으로 페이지 참조열에 따라 15번의 페이지 fault가 발생한다.