[개념 정리/운영체제] 페이지 교체 알고리즘 - FIFO, LRU, NUR, LFU

페이지 교체 알고리즘

페이지 폴트 발생 시 스와핑이 일어날 때,

페이지 교체 알고리즘(page replacement algorithm)에 의해

페이지가 교체된다.

 

이론상의 알고리즘인 오프라인 알고리즘과,

실제 사용되는 4가지 알고리즘에 대해 알아보자.

 

오프라인 알고리즘

오프라인 알고리즘은 가장 좋은 알고리즘이라고 일컫는 알고리즘으로,

가장 먼 미래에 참조될 페이지와 현재의 페이지를 바꾸는 알고리즘이다.

LFD(Longest Forward Distance)라고도 한다.

 

예를 들어, 메모리에 세 자리가 있고, 0, 1, 2, 3, 4, 2 페이지가 순서대로 들어온다면

가장 먼 미래에 참조되는 2와 스와핑 하는 방식이다.  

 

그러나 미래에 사용될 프로세스를 미리 알 수 없기에,

현실에서는 사용할 수 없는 알고리즘이다.

대신 다른 알고리즘의 성능 비교를 위한 상한선을 제공하는 역할을 한다.

 

FIFO(First In First Out)

FIFO는 먼저 온 페이지부터 교체하는 방식이다.

페이지 폴트가 일어나면

가장 먼저 들어온 페이지가 새로운 페이지로 교체된다.

 

LRU(Least Recently Used)

LRU는 최근에 사용되지 않은 페이지를 바꾸는 방식이다.

즉, 참조가 오래된 페이지를 바꾼다.

이를 위해 각 페이지마다 최근 사용한 횟수를 나타내는 자료구조를 따로 만들어야 할 수도 있다.

 

예를 들어, 메모리에 4자리가 있고, 7, 0, 1, 2, 0, 3, 0, 4 순으로 페이지 요청이 들어온다면

아래와 같이 페이지 교체가 진행된다.

 

1. 처음 7 0 1 2를 담고 다음 0이 들어왔을 때는 스와핑이 일어나지 않는다.
2. 3이 들어왔을 때 참조가 가장 오래된 7을 교체한다.
3. 이후 0이 들어왔을 때 스와핑이 일어나지 않는다.
4. 4가 들어왔을 때 가장 오래된 1과 교체한다.

 

NUR(Not Used Recently)

LRU에서 발전한 알고리즘이자,

NRU(Not Recently Used)라고도 불리는 알고리즘이다.

일명 clock 알고리즘으로, 0과 1을 가진 비트를 사용한다.

 1은 최근에 참조되었음을, 0은 참조되지 않았음을 의미한다.

만약 clock이 한 바퀴 도는 동안 사용되지 않은 페이지는 0이 된다.

시계 방향으로 돌면서 0을 찾고,

0을 찾은 순간 해당 페이지와 교체하고, 해당 부분을 1로 바꾼다.

 

LFU(Least Frequently Used)

LFU 알고리즘은 가장 참조 횟수가 적은 페이지를 교체하는 알고리즘이다.

예를 들어, 3자리에 0, 1, 2, 0, 0, 1, 2, 3 순으로 요청이 들어온다면

다음과 같이 교체가 이루어진다.

 

1. 0, 1, 2를 그대로 담는다.
2. 0 페이지 히트. 0의 참조 횟수: 2
3. 0 페이지 히트. 0의 참조 횟수: 3
4. 1 페이지 히트. 1의 참조 횟수: 2
5. 2 페이지 히트. 2의 참조 횟수: 2
6. 3 페이지 히트. 가장 참조 횟수가 적은 1과 2중 1과 스와핑한다.

 

참고: inflearn 강의 'CS 지식의 정석 - 큰돌'