LRU(Least Recently Used) 캐시 알고리즘

LRU 캐시 알고리즘

- Least Recently Used (가장 최근에 사용한)

- 가장 오래전에 참조된, 덜 최근에 사용된 데이터를 내쫓는다. 최근에 참조된 것이 가까운 미래에 참조될 가능성이 높은 성질을 이용한 알고리즘이다.

- JAVA에서는 Queue 자료구조를 사용하여 구현할 수 있다. 

 

실행 과정

1) data : 1 , 캐시 비어있음. 캐시에 1 삽입

2) data : 2, 캐시 공간 있음. 캐시에 2 삽입

3) data : 3, 캐시 공간 있음. 캐시에 3 삽입

4) data : 4, 캐시 공간 있음. 캐시에 4 삽입

5) data : 1, 캐시에 이미 데이터 1이 있음. continue

6) data : 2, 캐시에 이미 데이터 2가 있음. continue

7) data : 5, 캐시가 꽉 찬 상태이며 데이터 5가 없음. 
    가장 덜 최근에 호출된 3을 내쫒고 5를 삽입

....