Page Replacement

Page Replacement

Page fault가 발생할 경우 disk에 가서 필요한 page를 가져와야 한다.

그런데 memory에 empty frame이 없을 경우 기존에 있던 frame을 제거해야 한다.

 

기본적인 page replacement는 다음과 같다.

• disk에서 원하는 page의 위치를 찾는다.
• victim frame (메모리에서 뺄 frame)을 선택하고 뺀다.
• 필요한 page를 읽어서 free frame(victim frame)에 넣는다.
• page table을 update 한다.
• 중단된 process를 다시 시작한다.

 

page fault가 일어나면 2 * EAT(everage access time) 이 소요된다.

victim page를 swap out하고, 새로운 page를 swap in 해야 하기 때문이다.

 

---

Page Replacement Algorithm

어떤 frame을 victim frame으로 선택하는가를 결정할 때 사용된다.

 

page relacement algorithm은 성능을 결정한다.

알고리즘에 따라서 나중에 계속해서 replacement가 일어날 수 있기 때문이다.

 

다음과 같은 알고리즘들이 있다.

• FIFO (First In First Out) algorithm : 먼저 들어온 순서대로 victim으로 선택한다.
• Optimal algorithm : 가장 먼 미래에 사용되는 frame을 victim으로 선택한다.
• LRU (Least Recently Used) algorithm : 마지막으로 참조된 시점이 가장 오래 전인 frame을 victim으로 선택한다.
• LRU approximation algorithm : LRU에 근사한 알고리즘
  • reference bit
  • additional reference bit
  • second chance algorithm
• Counting algorithm

 

---

FIFO (First In First Out) Algorithm

가장 먼저 메모리에 올라온 frame을 victim frame으로 선택한다.

 

문제

그러나 physical memory가 커짐에도 동일한 상황에서 page fault가 증가함을 야기한다. (Belady's anomaly : 예측함과 다름)

따라서 사용하기에 좋지 않은 알고리즘이다.

 

예제

CPU가 memory를 참조하는 순서를 나타낸 것을 reference string이라 한다.

reference string이 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 라고 하면 FIFO algorithm은 다음과 같이 page replacement를 일으킨다.

 

아래 첫번째 예제는 memory에 최대 3개의 frame이 들어올 수 있는 경우로, 총 9 번의 page fault가 일어난다.

두번째 예제는 memory에 최대 4개의 frame이 들어올 수 있는 경우로, 총 10번의 page fault가 일어난다.

 

---

Optimal Algorithm

Page fault가 발생한 후에 가장 오래동안 참조되지 않을 것을 victim으로 설정한다.

즉, reference string을 미리 알아서 page fault가 일어났을 때 가장 먼 시점에 참조되는 frame을 victim으로 선택한다.

 

가장 이상적이고 가장 적은 page fault가 일어난다.

 

문제

그러나 reference string을 미리 알아야 하기 때문에 실제로는 사용되지 못한다.

다만, 다른 알고리즘과의 성능을 비교하는데 사용한다.

 

예제

 

---

LRU(Least Recently Used) Algorithm

최근에 가장 적게 사용된 frame을 victim으로 선택한다.

즉, 마지막으로 참조된 시점이 가장 오래 전인 frame을 victim을 선택한다.

 

Optimal 알고리즘은 미래를 판단하지만, LRU 알고리즘은 과거를 판단한다.

따라서 optimal 알고리즘과 LRU 알고리즘은 시간적으로 대칭으로 볼 수 있다.

 

Locality

LRU 알고리즘은 temproal locality를 잘 활용하기 때문에 현실적으로 사용할 수 있는 알고리즘 중에서 가장 성능이 좋다.

• temproal locality : 어떤 주소를 참조했을 때 그 주소가 조만간 다시 참조될 가능성이 높다.
• spatial locality : 어떤 주소를 참조했을 때 그 주변의 주소를 참조할 가능성이 높다.

 

구현

두 가지 구현 방법이 있다.

• counter 이용
  • 마지막으로 사용된 시간을 의미한다.
  • 모든 page entry는 counter를 가지고 있다.
  • 해당 entry가 참조되면 참조된 시점을 counter에 기록한다.
  • 따라서 counter가 가장 작은 것은 가장 오래 전에 참조되었음을 의미한다.
• stack 이용
  • 참조된 순서만 기억한다.
  • page number가 기록된다.
  • page가 참조되면 해당 page number를 스택의 가장 맨 위로 올린다.
  • 따라서 stack의 bottom에 있을 수록 최근데 사용되지 않은 것이다.
  • doubly linked list를 이용하는 것이 가장 좋은 구현이다.

 

문제

page의 참조는 매우 빈번하게 발생하기 때문에 counter와 stack을 이용해서 매번 기록할 수 없다.

성능적인 비용이 너무 크기 때문에다.

 

작은 시스템에서는 하드웨어를 추가해서 hardware support를 이용한다.

그러나 일반적인 경우에서는 가성비가 떨어진다.

 

따라서 LRU에 근사한 LRU appriximation algorithm을 사용한다.

 

---

LRU Approximation Algorithm

• reference bit
• additional reference bit
• second chance algorithm

 

Reference Bit

Page table에 reference bit을 추가해서 이용한다.

초기값은 0이고, page가 참조되면 하드웨어에 의해 1로 set 된다.

다른 page가 참조되면 자신의 reference bit은 0으로 초기화 한다.

 

그러나 이는 너무 오차가 크다.

따라서 additional reference bit을 이용한다.

 

Additional Reference Bit

각 page 마다 8bit을 추가한다.

일정 시간마다 운영체제는 reference bit을 오른쪽으로 shift 한다.

도중에 참조하면 MSB를 1로 set 한다.

 

가장 작은 값을 가진 page가 가장 최근에 참조되지 않은 것이므로 victim으로 선택한다.

 

주로 interval을 100ms로 한다.

따라서 100ms 정도의 오차가 존재한다.

그렇기 때문에 완전한 LRU는 아니다.

 

reference bit을 늘리거나, shift 하는 interval을 줄이면 LRU에 더 근접해진다.

그러나 메모리나 성능 상에 비용이 커지게 된다.

 

Second Chance

FIFO 알고리즘과 reference bit을 함께 사용한다.

1. FIFO 순서대로 page를 검색한다.
   1. reference bit이 0이면 page를 교체한다.
   2. reference bit이 1이면 기회를 한번 더 준다.
      1. reference bit을 0으로 clear 한다.
      2. 메모리에 page를 냅두고 다음 page 검사로 옮긴다.
      3. reference bit을 0으로 초기화하기 때문에 다음 검사 때는 교체의 대상이 될 수 있다.

 

Worst Case

모든 page의 reference bit이 1인 경우가 worst case이다.

이 때는 전체 page를 FIFO 순서로 돌면서 reference bit을 0으로 초기화한다.

다시 처음으로 돌아가서 검색할 때 모든 reference bit은 0이 된다.

따라서 FIFO에서 처음의 page가 victim이 된다.

 

---

Counting Algorithm

LRU 알고리즘과는 다르다.

 

참조의 빈도를 이용해서 replacement를 수행한다.

따라서 참조의 빈도를 위한 counter를 이용한다.

 

LRU 알고리즘 보다는 성능이 좋지는 않다.

 

두 가지 알고리즘이 있다.

LFU와 MFU 중 어느 것이 더 좋은지는 모른다.

• LFU (Least Frequently Used) Algorithm
  • 참조된 횟수가 가장 적은 것을 선택한다.
• MFU (Most Frequently Used) Algorithm
  • 참조된 횟수가 가장 많은 것을 선택한다.