[운영체제/OS] Page Replacement Algorithms

FIFO (First-In-First-Out) Algorithm

When a page must be replaced, the oldest page is chosen

사용한 지 가장 오래된 page부터 replace 해주는 방법

 

Problem

- frame 개수가 늘어나면, page fault는 줄어야 하는데, page fault가 늘어나는 현상이 발생

- 자주 사용하는 page가 old page일 수도 있다

 

Belady's anomaly

: page fault는 할당된 frame이 increase함에 따라 increase 할 수도 있다.

 

 

Optimal Algorithm

가장 낮은 page fault를 발생시키는 알고리즘

앞으로 사용하지 않을 page를 replace 시키는 알고리즘으로, 가장 최적화된 방식이다.

 

Problem

- 미래를 예측하여 미래의 정보를 바탕으로 알고리즘을 구현하기 때문에 구현하기가 어렵다.

 

하지만, 이 방법은 최적의 알고리즘이기 때문에 실제로 구현되는 알고리즘들과 비교하여 이를 바탕으로 실제로 구현되는 알고리즘들을 평가할 수 있다. 

 

LRU (Least Recently Used) Algorithm

가장 오랫동안 사용하지 않은 page가 미래에도 사용하지 않을 확률이 높다

과거의 지식을 이용하여 미래를 예측하는 방식

Generally good algorithm이고, 빈번하게 사용된다.

 

How to implement LRU replacement

• Use counter : 시간 기록하여 counter 값이 작은 process부터 실행
  • Every page entry는 counter를 가져양하고, page를 참조할 때 마다 counter를 copy해줘야 한다.
  • page를 replace 할 때, counter값이 가장 작은 것부터 replace 해준다.
    • Problem 
    • page를 replace하기 위해 search 하는 데 시간이 많이 필요하다 (complexity O(N) with N frames)
    • Counter은 memory를 참조할 때 마다 update 해줘야 한다.

• LRU implementation requires Hardware support (due to speed)

 

 

Additional-Reference-Bits Algorithm

8-bit byte for each page in a table in memory

At regular intervals, the reference bit for each page is shifted right by 1-bit

 

Example

1) 00000000 : page has not been used for 8 time periods

2) 11111111 : page has been used at least once in each period

3) 11000100 vs 01110111 : 가장 왼쪽 bit가 최근꺼이므로 11000100 이 01110111보다 더 최근 bit이다

 

-> 이진수가 큰 bit일수록 (정수가 클수록), 최근 page이고, 이진수가 작은 bit일수록 (정수가 작을수록), 오래된 page이다.

 

 

Second-chance Algorithm (Clock Algorithm)

circular list를 사용하여 page 당 하나의 reference bit을 사용하는 알고리즘

Pointer는 replace 될 다음 page를 가리킨다.

• If reference bit = 1이면, reference bit을 0으로 설정하고, 다음 page를 가리킨다.
• If reference biy = 0이면, replace 한다.
  • second chance 이었다
  • 만약 이 page가 지난 cycle에서 참조 됐었다면, reference bit은 1 이었어야했는데, 0이므로, 지난 cycle에서 참조한 적이 없었다는 것을 의미한다.