LRU 알고리즘 (Least Recently Used Algorithm)

가장 오랫동안 참조되지 않은 페이지를 교체하는 기법

페이지 교체 알고리즘이란?

페이지 교체 알고리즘은 페이징 기법으로 메모리를 관리하는 운영체제에서, 페이지 부재가 발생하여 새로운 페이지를 할당하기 위해 현재 할당된 페이지 중 어느 것과 교체할지를 결정하는 방법이다.

페이지 교체 알고리즘의 예로, FIFO, LFU, LRU 알고리즘 등이 있다.

FIFO

페이지가 주기억장치에 적재된 시간을 기준으로 교체될 페이지를 선정하는 기법

단점

중요한 페이지가 오래 있었다는 이유만으로 교체되는 불합리. 가장 오래 있었던 페이지는 앞으로 계속 사용될 가능성이 있음.

LFU

가장 적은 횟수를 참조하는 페이지를 교체

단점

참조될 가능성이 많음에도 불구하고 횟수에 의한 방법이므로 최근에 사용된 프로그램을 교체시킬 가능성이 있고, 해당 횟수를 증가시키므로 오버헤드 발생

LRU

가장 오랫동안 참조되지 않은 페이지를 교체

단점

프로세스가 주기억장치에 접근할 때마다 참조된 페이지에 대한 시간을 기록해야함. 큰 오버헤드가 발생

참조링크

오늘은 그 중, LRU 알고리즘에 대해 공부해보겠다.

LRU 알고리즘 그림 설명

Input : 123145

Output : 5413

4초 : 1은 재참조된 것이므로, 가장 오랫동안 참조되지 않은 순으로 저장된 순서를 변경한다.

6초 : cache size가 가득차 5가 들어갈 수 없으므로, 가장 오랫동안 참조되지 않은 2를 제거한 후 저장한다.