[Python] LRU(Least Recently Used) 알고리즘

페이지 교체 알고리즘

페이지 부재가 발생 하여 새로운 페이지를 할당하기 위해 현재 할당된 페이지 중 어느 것과 교체할지를 결정하는 방법이다. 이 알고리즘이 사용되는 시기는 페이지 부재가 발생해 새로운 페이지를 적재 해야하나 페이지를 적재할 공간이 없어 이미 적재되어 있는 페이지 중 교체할 페이지를 정할 때 사용된다.

 

LRU(Least Recently Used)

페이지 교체 알고리즘의 종류로 페이지 부재가 발생했을 경우 가장 오랫동안 사용되지 않은 페이지를 제거하는 알고리즘이다. 이 알고리즘은 가장 오래동안 사용되지 않은 페이지는 앞으로도 사용할 확률이 적다는 가정 하에 사용한다.

 

참조 값 : 4 2 3 4 5 6 5 4 7

캐시 적중 (cache hit) : 살색 배경

캐시 실패 (cache miss) : 빨간색 배경

 

 

맨 왼쪽 흰색 배경이 초기의 캐시이고 밑으로 갈 수록 오래 된 페이지라고 가정한다.

위와 같이 참조하는 값이 캐시안에 없으면 가장 오래 전에 참조한 값을 빼고 현재 값을 캐시에 넣어준다.

반대로 참조하는 값이 캐시안에 있으면 해당 값을 캐시의 가장 최근 위치에 넣어준다.

 

Python 코드

 

 

2018 KAKAO BLIND RECRUITMENT 코딩테스트에 LRU 알고리즘을

사용하는 문제가 있으니 풀어보면 좋을 것 같다.^_^

 

 

https://gingerkang.tistory.com/28

[프로그래머스] 캐시(LRU) / Python / 2018 KAKAO BLIND RECRUITMENT