[운영체제 #15] Page Replacement

Page Replacement Algorithm

Optimal Algorithm

사실 페이지 교체 시 가장 이상적인 알고리즘은, 미래에 사용될 페이지 중 가장 적게 사용할 페이지를 교체해주는 것이다.

Optimal Page Replacement Algorithm

 

위에서도 frame이 7, 0, 1까지 채워진 상황에서 미래시를 보면 7을 가장 나중에 사용하기에 7을 2로 교체해준 것을 볼 수 있다. 그러나 당연히도 이 방법은 미래를 알 수 없기에, 이 알고리즘과 가장 비슷한 성능이 나오는 알고리즘을 찾고자 한다.

FIFO Algorithm

FIFO

 

기존의 FIFO와 동일한 개념으로, 가장 처음 들어온 페이지를 교체해준다. 언제나 단순한 방법이지만 그다지 좋은 성능을 보이지 못하며, 아래와 같이 특정 frame 수에서 오히려 page fault수가 늘어나는 Belady's Anomaly가 발생할 수 있다.

Belady's Anomaly

LRU Algorithm

LRU

 

LRU(Least Recently Used) 알고리즘은 미래 대신 가장 가까운 과거를 이용한다. 그래서 최근에 사용한 페이지는 두고, 가장 오랫동안 사용하지 않은 페이지를 교체한다. FIFO보다 더 좋은 성능을 내는건 맞지만, 구현이 어렵다.

• Counter Implementation : 페이지별로 마지막으로 사용한 시각을 counter에 저장하는 방식으로, counter값이 가장 적은 것이 오랫동안 사용안한 페이지다.
• Stack Implementation : 페이지가 Referenced될때마다 해당 페이지를 stack의 top으로 이동시키는 방식으로, stack의 맨 아래 페이지가 가장 오랫동안 사용안한 페이지다.

LRU가 FIFO보다 더 좋은 성능을 내는건 맞지만, 위와 같은 추가 구현이 필요하고 이에 대한 추가적인 하드웨어가 필요할 수도 있다. 따라서 Reference bit을 사용해서 참조된 페이지는 1, 참조되지 않은 페이지는 0으로 설정하여 bit가 0인 페이지를 교체하는 방식을 사용하기도 하는데, 이렇게 하면 LRU와 근사하다 해서 LRU Approximation Algorithm이라 한다. 이 방식에는 2가지의 알고리즘이 존재한다.

 

LRU Approximation : Additional-Reference-Bits Algorithm

한 프로세스 내의 각 페이지 별로 8bit의 counter를 둔다. 그럼 각 페이지 별로 Reference bit가 설정되면 해당 counter에 bit를 입력한다. bit는 왼쪽부터 입력하며 만약 bit가 8자리가 다 채워졌으면 right shift를 하면서 bit를 채운다.

 

3개의 페이지의 counter값이 다음과 같다고 가정하자.

• Page1 : 00011000
• Page2 : 11111111
• Page3 : 00000001

위의 counter을 해석하자면, 8번의 time interval동안 Page1은 4, 5번째에서 사용된 것이고, Page2는 매번 사용됐고, Page3는 1번째에서만 사용한 것이다. 그럼 Page3가 가장 오래된 페이지임을 알 수 있다. 따라서 이 counter를 일종의 수로 생각해서 가장 작은 값을 가진 페이지를 교체해주는 방식인 것이다.

LRU Approximation : Second-Chance Algorithm

Second Chance Algorithm

 

이 방법은 clock algorithm이라고도 불리는데, Reference bit를 가진 FIFO방식이라고 보면 된다. 포인터 하나를 두고 탐색 순서는 FIFO를 원칙으로 한다. 이때 포인터는 교체할 페이지를 찾을때까지 이동하며 다음과 같은 작업을 한다.

• Reference bit가 0 : 페이지를 교체
• Reference bit가 1 : bit을 0으로 변경

Enhanced Second-Chance Algorithm

 

여기서 만약 modify bit까지 고려하면 위와 같이 우선순위가 4가지로 나뉠 것이다. 여기서는 (0, 0)부터 교체해주고 우선순위는 위에서 아래이다.

Counting Algorithm

이 알고리즘은 페이지를 사용한 시간은 고려하지 않고 사용한 횟수만을 따진다.

• LFU(Least Frequently Used) Algorithm : 가장 적게 사용한 페이지를 교체
• MFU(Most Frequently Used) Algorithm : 가장 많이 사용한 페이지를 교체

Page-Buffering Algorithm

더 효율적인 페이지 교체를 하기 위한 추가 기법들로, 메모리 관리와 성능 최적화를 위해 버퍼를 활용한다.

• Pool로 free frame 관리하여 필요할 때 Pool에서 free frame을 가져오고, victim frame은 Pool에 다시 돌려놓는 방법
• 수정된 페이지를 디스크에 작성하여 modify bit을 0으로 reset해주며, 페이지를 자주 교체할 수 있게 하는 방법
• Pool로 free frame 관리 방식에 free frame 재사용을 위해 각 frame에 있었던 페이지를 기억하는 방식을 더한 방법

---

Thrashing

프로세스에 page frame을 할당하는 방식은 크게 2가지로 나눌 수 있다.

• Global Replacement : 다른 프로세스에 할당된 frame을 뺏을 수 있는 방법이다.
• Local Replacement : 자신에게 할당된 frame 내에서만 교체하는 방법이다.

근데 이 와중에 프로세스가 최소한의 page frame을 할당받지 못해서 실행보다 swapping에 더 많은 시간을 소모하여 CPU 활용도가 떨어지는 현상이 발생할 수 있는데, 이를 Thrashing이라 한다.

 

분명 프로세스 수가 늘어갈수록 CPU 활용도가 올라가는것이 맞지만, 어느 순간을 지나면 CPU 활용도가 유지되기는 커녕 급격히 떨어지게 된다. page frame을 받지 못한 프로세스가 발생하여 page fault가 급격히 늘어났기 때문이다.

 

이를 예방하기 위한 모델은 다음과 같다.

Working-Set Model

우선 다음 notation을 살펴보자.

• m : 실제 physical memory에서 사용 가능한 frame의 수
• △ : working-set window, 프로세스가 페이지를 참조하는데 주어진 시간
• WS : working-set, △동안에 참조한 페이지들의 집합
• WSS : working-set size, △동안에 참조한 페이지의 수, 이 WSS를 모두 더하면 D(total demand frames)라 한다.
  • △가 너무 작으면 변화하는 locality를 모두 반영할 수 없다.
  • △가 너무 크면 불필요하게 많은 locality를 반영한다.

Working-Set Model

 

여기서 working-set model은 △동안 참조된 페이지를 추적해서 WS를 유지하고, 페이지 교체가 필요할 때 현재의 WS를 기준으로 WS에 포함되지 않은 페이지를 교체한다. 또한 D값이 m보다 커지면 Thrashing이 발생하는 것인데, 이런 경우 프로세스 중 하나를 종료(suspend)시키고 다른 프로세스들에게 할당해준다.

PFF(Page-Fault Frequency)

PFF Scheme

 

page-fault의 상한과 하한을 두고, 상한보다 높아지면 frame을 더 할당하고 하한보다 낮아지면 할당된 frame 수를 줄인다.

Other Considerations

• Prepaging : 사용할것같은 페이지를 미리 불러들이는 기법
• Small page size : 사이즈가 너무 크면 내부단편화 문제가 있으므로 작은게 좋다.
• Program structure : 2차원 배열 로직에서 인덱스 고려를 잘 해야한다.

• I/O Interlock : I/O작업에 사용되는 페이지는 victim으로 선택되면 안되기에 lock을 하는 기법