Page replacement policy

0. evict page

 

demand paging을 사용하면, 메인 메모리로 페이지를 가져와야 하는데 그러면 원래 메인 메모리에 박혀있는 페이지 하나를 뽑아줘야 한다.

 

이 때, 뽑을 페이지를 고르는 것도 전략적으로 골라야 컴퓨터 성능이 좋아지는데, 왜냐면 page fault가 나서 디스크를 참조하는 경우 시간이 엄~청 오래걸리기 때문이다.

 

전략적으로 evict할 page를 잘 골라서 최대한 page fault가 나지 않도록 하는 것이 중요하다.

 

지금부터 evict할 page를 고르는 여러가지 알고리즘들을 살펴보자

 

 

 

1. OPT (Belady's Algorithm)

 

앞으로 가장 오랫동안 사용되지 않을 페이지를 빼는 알고리즘

 

이는 수학적으로 증명된, 가장 page fault rate이 낮은 방법이다.

 

OPT

 

위의 예에서 알 수 있듯이, page fault가 나면, 가장 나중에 참조될 페이지를 빼는 방식이다.

 

하지만 이 방식은 미래에 어느 페이지가 참조될 지 알아야 한다는 단점이 있다. 대부분의 현실 컴퓨팅의 경우 미래에 어느 페이지가 참조될 지 아는 것은 불가능하다. 따라서 belady's algorithm은 다른 알고리즘의 효율성을 따지는 평가기준으로 많이 쓰인다. (이 방식이 가장 최적화된 방식이므로)

 

 

 

2. FIFO

 

가장 먼저 들어온 페이지를 가장 먼저 빼는 알고리즘

 

 

 

가장 직관적이고 가장 일반적인 방법이다. 하지만, 이 알고리즘은 치명적인 문제점이 있는데, 이를 belady's anomaly라고 부른다.

 

belady's anomaly란, page frame이 커졌지만, page fault rate이 증가하는 문제이다. 위의 예시에서 page frame이 3개일 때의 page fault rate은 9/12 지만, page frame이 4개일 때의 page fault rate은 10/12이다. 이런 경우를 belady's anomaly 라고 한다.

 

즉, 메모리하나 더 꼽느라 돈을 쓰고도, 컴퓨터 성능이 더 떨어진다는 것이다.

 

 

 

3. LRU (Least Recently Used)

 

가장 과거에 참조된 페이지를 빼는 알고리즘 (=가장 최근에 참조되지 않은 페이지를 빼는 알고리즘)

 

OPT 방식에서 변형된 것으로, 우리가 미래를 보고 판단할 수 없으니, 과거를 보고 미래를 예측하는 것이다.

 

만약, n개의 page frame을 가지고 있을 때, page frame이 1,2,3,4,...n 라는 페이지를 포함한다고 하자. 이 때, n+1개의 page frame으로 늘어나도 page frame이 1,2,3,4,...n을 무조건 포함하고 있는 경우를 stack algorithm이라고 한다. 그리고 stack algorithm은 belady's anomaly를 겪지 않는다.

 

LRU 알고리즘은 stack algorithm의 한 예시이다. 따라서 LRU는 belady's anomaly를 겪지 않는다.

 

LRU

 

위의 그림에서 page frame이 3개에서 5개로 늘어나도 상위 3개 프레임에 속해있는 페이지들은 page frame이 3개인 경우와 똑같다. 이런 특징이 앞서 설명한 stack algorithm의 특징이다.

 

LRU를 구현하는 방식은 크게 두가지가 있다.

 

[1] doubly linked list

 

페이지들을 linked list 형식으로 구현하여 관리하는 방식이다.

이 방식은 evict 할 때, tail을 자르면 되므로, evict 하기 빠르다는 장점이 있지만, linked list를 매번 업데이트 해줘야 하므로, 페이지를 참조할때는 느리다는 단점이 있다.

 

[2] clock or counters

 

각 page frame마다 시간을 기록할 수 있는 변수를 두고, 페이지가 참조될 때마다 clock을 업데이트해주는 방식이다.

이 방식은 참조될 때마다 clock을 업데이트해주기만 하면 되므로 페이지를 참조할 때 빠르다는 장점이 있지만, evict 페이지를 찾으려면 전체를 다 살펴봐야 하므로, evict 하기 느리다는 단점이 있다.

 

위의 두 방식은 참조할때 단점이 있거나, evict 할때 단점이 있거나, 어쨌거나 단점이 존재한다.

 

 

 

4. LRU Approximation Algorithm

 

위에서 언급한 단점 때문에 막 엄청 빡빡하게 가장 늦게 참조된 페이지를 찾는 것이 아니라 그냥 대충 근사적으로 늦게 참조된 페이지를 찾는 방식을 사용하는데, 이를 LRU Approximation Algorithm이라고 한다.

 

LRU Approximation algorithm은 크게 reference bit을 사용하는 방법과 second chance algorithm이라는 방식이 있다.

 

 

[1] reference bit 이용 LRU Apporximation algorithm

각 page를 나타내는 pte의 reference bit은 참조될 때마다 1로 세팅된다.

특정 시간간격을 두고 reference bit를 모아서, 모인 값이 가장 작은 페이지를 evict 하는 방식이다.

 

[2] second chance algorithm (clock algoritm)

 

clock algorithm

 

위의 그림처럼 페이지들이 시계 모양의 ring buffer 형식으로 구현되어 있는 상태에서 특정 페이지가 참조되면 reference bit을 1으로 바꿔준다.

그리고 만약 특정 페이지를 evict해야 한다면, 시계바늘이 가리키고 있는 페이지를 evict 하려고 한다. 다만 이 때, 시계바늘이 가리키는 페이지의 reference bit가 0이면 그냥 evict하고, 1이면 0으로 만들고 시계바늘을 한칸 옮긴다.

앞서 설명한 pte의 reference bit 사용하는 방식에 비해 더 approximate하므로 더 간단하다는 장점이 있다.

 

 

 

5. Counting based page replacement

 

페이지가 참조된 횟수를 기준으로 page replace 하는 알고리즘

 

가장 적게 참조된 페이지를 빼는 LFU와 가장 많이 참조된 페이지를 빼는 MFU라는 방식이 있다.

 

하지만, 이런 Counting based page replacement 방식은 counting을 하는데 생기는 오버헤드가 크다는 문제점과, 엄청 예전에 카운트가 많이 되고 최근에는 참조되지 않는 페이지가 evict 되지 않는다는 문제가 있어서 잘 안쓴다.

 

 

오늘 배운 내용을 정리해보면,

 

1. demand paging에서는 evict할 페이지를 고르는 알고리즘이 필요하다.

 

2. evict할 페이지를 잘 골라야지 성능이 좋아지므로, 고르는 과정은 매우 중요하다.

 

3. 가장 수학적으로 증명된 이상적인 방법은 belady's algorithm이지만, 평가기준으로 쓰인다.

 

4. FIFO 방식은 belady's anomaly가 발생한다

 

5. LRU 방식은 과거를 통해 미래를 예측하는 방식인데 구현상의 단점들이 존재한다.

 

6. 이 단점들을 보완하기위해 나온 것이 LRU Approximate 방식이다.

 

 

위 내용들은 공부하며 정리한 것으로, 오류가 있을 수 있습니다.