Page Replacement Algorithm Examples: NRU/FIFO/LRU/Second Chance
포스트 난이도: HOO_Middle
[Notice] 포스트 난이도에 대한 설명
안녕하세요, HOOAI의 Henry입니다. Bro들의 질문에 대한 내용을 우선적으로 포스팅이 되다 보니 각각의 포스트에 대한 난이도가 달라서 난이도에 대한 부분을 작성하면 좋겠다는 의견을 들었습니다
whoishoo.tistory.com
# Example 1
| Page | Loaded | Last reference | Referenced | Modified |
| 0 | 120 | 280 | 1 | 0 |
| 1 | 230 | 260 | 0 | 1 |
| 2 | 140 | 270 | 0 | 0 |
| 3 | 110 | 290 | 1 | 1 |
Page replacement algorithm의 문제 조건으로 위와 같은 전제 조건이 주어졌을 때 LRU, NRU, FIFO, Second chance를 구해보도록 하자.
우선 FIFO를 먼저 살펴보기 위해서는 제일 오래된 페이지를 찾아야 한다.
따라서 이 표에 있어서는 Loaded time 살펴볼 필요가 있다.
페이지가 오래되었다는 것은 Loaded time이 제일 빠르다는 걸 의미한다.
따라서 Page 3가 110으로 Loaded time이 제일 빠르기 때문에 FIFO에 있어서는 Page 3가 교체된다.
다음으로 LRU 알고리즘을 적용하면, 최근에 가장 사용되지 않은 페이지를 찾아야 한다.
페이지가 최근에 사용되지 않았다는 것은 Last reference time이 제일 오래된 페이지를 찾으면 된다.
Page 1의 경우 마지막 참조된 시간이 260이기에 상대적으로 다른 페이지에 비해 사용이 되지 않고 있기 때문에 LRU에서는 Page 1이 교체된다.
다음으로 NRU를 살펴보기 위해서는 Referenced bits와 Modified bits를 참고해야 한다.
LRU와 헷갈릴 수 있는 알고리즘이 NRU인데, NRU는 Not Recently Used라는 의미를 가진 알고리즘이다.
NRU는 참조나 수정 자체가 이루어지지 않았던 페이지를 찾아서 우선적으로 교체해주는 알고리즘이다.
따라서 이 문제에서 NRU를 통해 페이지 교체를 하게 되면, R과 M bits가 모두 0인 Page 2가 교체된다.
마지막으로 Second Chance를 살펴보도록 하자.
Second chance는 FIFO에서 응용된 페이지 교체 알고리즘이라고 이해하면 쉽다.
FIFO 방식을 통해 교체할 페이지를 찾지만 Referenced bits가 1인 경우 해당 페이지를 교체하지 않고 교체할 다음 페이지를 FIFO로 찾는다.
다만 페이지 교체가 이루어지지 않았던 페이지의 경우에는 R bits가 1에서 0으로 초기화가 된다.
따라서 이 문제에서 FIFO 알고리즘을 통해서 교체할 페이지를 찾게 되면 페이지 3가 해당되지만, Second chance에서는 R bits가 1이기 때문에 0으로 초기화를 해준 다음에 다음 오래된 페이지를 찾는다.
Page 3 다음으로 오래된 페이지는 페이지 0이지만, Page 0도 Referenced bits가 1이기 때문에 이를 0으로 초기화 해준 다음, 다른 페이지를 찾는다.
Page 0 다음 오래된 페이지는 Page 2이고 마침 R bits도 0이기 때문에 Page 2가 최종적으로 교체된다.
# Example 2
| Page | Loaded | Last reference | Referenced | Modified |
| 0 | 200 | 260 | 1 | 1 |
| 1 | 120 | 200 | 1 | 0 |
| 2 | 190 | 310 | 0 | 1 |
| 3 | 310 | 400 | 0 | 0 |
Answer)
FIFO: Page 1
LRU: Page 1
NRU: Page 3
Second Chance: Page 2
댓글