LRU(Least Recently Used) 알고리즘

문제를 풀던 중, LRU라는 개념에 대해 다시 복기할 수 있었다.
그래서 개념을 정리해두고자 한다.

https://dailylifeofdeveloper.tistory.com/355
이 분의 블로그에 잘 정리되어 있어서 참고했다!

간단히 정리해보자면

리스트에 값(v)을 넣는 과정에서,
1. 해당 값(v)이 이미 리스트에 있다면 리스트에서 해당 값(v)을 삭제하고 새로운 값(v)을 front에 넣는다. (push_front(v))
2. 리스트가 꽉 차있으면 가장 뒤 (back) 에 있는 값을 뺀다. (pop_back())
- 이유 : 여태 참조를 안 하고 있었으니 빠지지도 않고 맨 뒤까지 밀렸을 것
3. 리스트에도 없는 값이고, 꽉 차있지도 않다면 리스트 맨 앞에 새롭게 넣는다. (push_front(v))

사실 이 알고리즘은 페이지 교체 알고리즘의 종류 중 하나이다.

페이지 교체 알고리즘?

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

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

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

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

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

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

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

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