캐시알고리즘 - LRU(Least-recently-used) Page Replacement

출처 - http://egloos.zum.com/judoboyjin/v/4545185

LRU(Least-recently-used) Page Replacement


앞에서 언급한 최상의 OPT알고리즘이 실현 불가능하기 때문에 차선책으로 고안해낸것이 바로 이 알고리즘이다. Optimal 알고리즘이 앞으로 가장 적게 사용될것을 선택하는 것과는 달리 이 알고리즘은 과거에 가장 오랫동안 사용되지 않은 것을 선택하게 된다.



예) 다음의 reference string과 3 frames이 있다고 가정하고, Page fault를 체크해보자.



7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1



최초의 7 0 1 이 프레임에 들어가고 2가 프레임에 들어가기 위해서 7을 victim으로 선택하게 된다. 7 0 1 모두 한번씩 호출되었고, 7이 가장 오래전에 호출된 것이기 때문이다. 그 다음의 page fault를 유발하는 3의 경우, 1과 교체가 된다. 0이 아닌 1과 교체가 되는 이유는 0은 2번, 1은 한번밖에 호출안되었다. 1이 호출된 시점이 두번째 0이 호출된 시점보다 훨씬 이전이다. 즉, 오래된것이다. (아래 그림 참고)









LRU 알고리즘을 구현하기 위해서는 해당 프레임이 언제 사용되었는지를 알아야한다. 이를 위해서 두가지 방법이 있는데.



첫번째로, Counter를 이용하는 방법이 있다. CPU clock을 이용해서 매번 page호출이 일어날때 마다 시간을 체크하는 것이다. 그래서 page replace가 일어나야 할경우 time이 가장 오래된것을 선택하게 된다. 이 방법은 매번 replacement가 발생할때마다 Page table에서 가장 오래된것을 찾아야 하며, Page table이 변경될때마다 해당 페이지의 시간도 같이 변경 되어야 하는 단점이 있다.



다음으로는 Stack을 이용하는 방법이다. 여기서 Stack은 일반적인 스택의 기능에 doubly linked list가 추가된 것이어야 한다. 매번 page가 호출될때마다 그 페이지 번호를 스택에 저장하는 방식이다. 페이지가 호출될때 스택에 이미 그 페이지가 있을 경우에는 해당 페이지를 스택에서 pop()시키고 새로 push()한다. 스택에 존재하지 않을 경우에는 그냥 push()한다.



예) 4 7 0 7 1 0 1 2 1 2 7 1 2



위와 같은 reference string이 있다고 가정하고 stack에 어떻게 저장되는지 보면



4, 7, 0 까지는 그대로 스택에 push()된다. 그리고 7이 호출되면 7이 이미 스택에 있으니까, 스택속의 7이 pop()되고나서 다시 7이 push()된다. 그래서 스택의 모양은 (4 7 0)에서 (4 0 7)로 바뀌게 된다. 그리고 다음에 1이 호출되면 그냥 스택에 바로 들어간다. 이제 스택은 (4 0 7 1) 이 된다. 다음 호출 페이지인 0은 이미 스택속에 있으니까, 0을 pop()하고 다시 push()하면 스택은 (4 7 1 0)의 모습으로 변한다. 이런식으로 매번 페이지가 호출될때마다 스택에 저장되며 스택의 가장 밑부붙(bottom)부분의 페이지가 Least-recently-used 페이지가 되며, 이 페이지를 Victim frame으로 지정하면 된다. (아래 그림 참고)







이제 왜 stack + doubly linked list가 필요한지 알것이다. 일반적인 stack에서 pop()이 마지막에 들어간것을 제거하는것에 비해, 앞에서의 변형된 stack은 pop()을 하면 마지막의 것이 아닌 새로 들어갈 것과 같은 이름의 element가 제거된다. 이렇게 할경우 일반적인 stack보다 구현에 있어 좀더 비용면에서 불리하다고 할수도 있지만, frame replace가 일어날때 couter방식처럼 search를 할필요가 없이 그냥 tail을 선택하면 되기 때문에 나름대로 괜찮은 방법이다.