First-In-First-Out(FIFO) 알고리즘
가장 오랜시간 동안 메모리에 존재하고 있는 page frame을 victim page로 선택하는 방식. 메모리 상의 page들은 탑재되는 순서에 따라 들어오는 순서가 매겨진다. 구현이 용이하고, replace될 victim page를 선택하는 방법 또한 용이하다. 하나의 FIFO queue만 사용하여 구현가능하기 때문이다.
페이지 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 들을 참조해야 한다고 가정해보자. 그리고 메모리에 한번에 3개의 페이지만 올라올 수 있다. --> 3 프레임
처음 참조할 때는 무조건 page fault가 일어난다.
|1|2|3|
1! 2! 3!
4! 2 3
4 1! 3
4 1 2!
5! 1 2
5 3! 2
5 3 4!
따라서 9번의 page fault가 발생한다.
4개의 프레임이 있다고 해보자.
|1|2|3|4|
1! 2! 3! 4!
5! 2 3 4
5 1! 3 4
5 1 2! 4
5 1 2 3!
4! 1 2 3
4 5! 2 3
10번의 page fault가 발생한다.
위와 같이 frame 수가 증가했는데 page fault가 증가하는 경우를 belady'a anomaly라고 한다.
Optimal 알고리즘
belady에 의해 제안된 알고리즘으로 anormaly를 개선하였다.
현존 page 중 향후 가장 오랫동안 사용되지 않을 page를 victim page로 선정한다. 이 알고리즘이 page fault 횟수를 최소화 시키는 것으로 알려져있다. 그러나 비현실적이다. 향후 프로그램의 수행을 예측할 수 있어야하기 때문이다. 그러므로 다른 현실적 replacement 알고리즘의 성능을 비교하기 위한 척도로 사용된다.
위와 같은 스트림을 다 알아야 한다. 위 사진은 optimal 알고리즘을 사용한 예시이다.
hit: 11
fault: 9
LRU(Least Recently used) 알고리즘
현존 page 중 과거 가장 오랫동안 참조되지 않았던 페이지를 victim 페이지로 선정한다. page 참조의 recentness에 따라서 페이지들의 재순서가 필요하다. Counter 혹은 Stack을 사용하여 구현이 가능하다.
메모리를 매번 참조할 때마다 stack의 내용들의 순서가 변경되어야 하기 때문에 성능저하를 야기시킬 수 있다.
위 사진은 스택을 사용하지 않은 모습이다.
7, 0, 1을 참조하고 2를 참조할 때 가장 오래전에 참조한 페이지인 7를 2와 교체한 것을 볼 수 있다.
hit: 8
fault: 12
위 사진은 스택을 사용한 모습이다. 페이지를 참조할 때마다 순서를 바꾸는 것을 볼 수 있다.
top은 가장 최근에 참조한 페이지, bottom은 가장 오래전에 참조한 페이지이다.
hit: 5
fault: 7
Clock 알고리즘
victim 선정이 한번에 이루어지지 않고 두번째에서 이루어지므로, 다른말로 second-chance 혹은 FINUFO(First-In-Not-Used-First-Out, 먼저 들어왔지만 사용되지 않은 것)알고리즘이라고도 한다.
Circular queue + use-bit + pointer P(다음에 교체될 페이지를 가리키는 포인터)를 사용한다.
use-bit는 초기 탑재 시 0으로 초기화되고, 해당 page가 참조될 때, 연관된 use-bit는 1로 변경된다.
if use-bit == 1
-use-bit = 0, use-bit가 0인 것을 찾을 때까지 포인터를 증가시킨다.
-찾았으면 페이지를 교체하고 포인터를 증가시킨다.
else
-페이지 교체, 포인터 증가
위와 같은 방법으로 victim page를 선정한다.
