21. 페이지 교체 알고리즘

CPU가 주소를 내고 우리는 demand paging을 이용해서 가상 메모리를 만들고 있다.

 

앞 선 예로 우리는 프로세스 3개를 페이지 단위로 올리고 이는 원래는 용량이 부족하여 올리지 못하지만

 

필요한 페이지만 올리기 때문에 올릴 수 있고 아무 문제없이 실행할 수 있다.

 

 

이제 페이징 단위로 메모리들이 모두 꽉 차 있는 상황을 가정해보자. 

 

그리고 하드디스크에 있는 p3에 일부 페이지들이 올라가야 하는 상황이다. 

 

이때 page replacement를 통해 메모리에 있는 한 페이지를 선택해서 쫓아내고 빈자리에 넣어야 한다.( victim page)

 

이왕이면 modify 되지 않은 페이지 그리고 이 중에서는 여러 page replacement algorithms을 쓴다고 말하였다.

 

page replacement algorithms 에는 FIFO, OPT, LRU 등이 있고 이 각각의 성능을 비교하기 전에

 

Page reference string 을 통해서 비교하게 될 것이다.

 

CPU가 내는 내부 주소는 페이지번호와 변위로 나뉜다. 페이지 단위가 100바이트이고

 

CPU가 100번지를 내었을때 valid bit를 통해 인터럽트가 발생 후 페이지 fault가 일어나고 페이지 단위로 메모리로 가져

 

오기 때문에 100~199번지는 pagefault가 일어나지 않는다. 페이지 단위로 한꺼번에 가져오기 때문

 

따라서 페이지 번호가 1 1 1 4 6 1 1 6 6  일떄

 

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

 

 

이제 Page reference string 즉 페이지 참조 열을 7 0 1 2  0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1로 두어보자

 

그리고 메모리는 3개의 페이징을 올릴 수 있는 공간으로 생각해보자.

 

1. FIFO ( First-in First-Out )

 

메모리에 먼저 올라온 놈을 victim으로 선택한다. CPU가 주소를 내고 이를 페이지 참조 열로 바꾼 것이

 

7 0 1 2...이다. 

 

• 처음 메모리에는 아무것도 올라오지 않은 상황이고 7 에는 무조건 page fault가 난다. {7,,}

 

• 0 역시 page fault 후 들어가야 한다. {7,0,}

 

• 1 역시 page fault 후 메모리로 들어간다. {7,0,1}

 

• 2 역시 메모리에 없기 때문에 page fault가 난다. 하지만 2를 넣을 때는 이미 메모리는 꽉 차있는

상황이다. 이때 제일 먼저 하드디스크에서 메모리로 온 7이 victim으로 선정된다. 따라서 7 -> 2가 된다

 

{2,0,1}

 

• 5. 0은 메모리에 있으므로 일어나지 않는다. {2,0,1}

.

.

(이하 생략)

 

 

결과 :

 

Page fault는 15번이 일어나게 된다.

 

실제로 해본다면 First in First out 이기에 금방 쫓겨난 페이지를 쓰는 경우도 많이 보인다.

 

 

2. OPT ( Optimal )

 

앞 선 경우에서 보았듯 바로 그다음 쓰여야 하는 페이지가 교체되어서 다시 페이지 교체가 일어나는 현상이

 

있을 수 있다. 따라서 앞으로 가장 오랜 기간 동안 사용 안될 페이지를 골라서 page fault를 시키는 것. 즉

 

미래를 보고 결정하는 것

 

 

결과:

 

Page fault는 9번이 일어나게 된다.

 

하지만 이 방법은 비현실적이다. 앞으로 가장 사용 안될 페이지는 실제 컴퓨터가 실행되는 도중에는

 

알 수 없기 때문. ( CPU 스케쥴링에 SJF과 마찬가지이다 )

 

 

3. LRU ( Least Recently Used )

 

최근에 가장 적게 사용된 페이지를 victim으로 사용하자.  현실적으로 앞으로 가장 사용 안될 페이지를 찾아내

 

기는 불가능하다(Opt).  따라서 과거를 보고 결정하는 것

 

 

결과:

 

Page fault는 12번이 일어나게 된다.

 

대부분의 컴퓨터는 LRU 방식으로 페이지 교체를 하게 된다.

 

 

교체 방식에는 Global과 Local 방식이 있다.

 

Global 방식은 모든 프로세스 중에서 victim을 구하기 위해 페이지 교체 알고리즘을 사용

 

Local 방식은 메모리에 올라온 자신의 프로세스 중에서 victim을 구하기 위해 페이지 교체 알고리즘을 사용

 

즉 범위의 차이다.