LRU (Least Recently Used)

• 운영체제의 페이지 교체 알고리즘 중 하나
• 페이지를 교체할 때 가장 오랫동안 사용되지 않은 페이지를 교체 대상으로 삼는 기법

 

LRU Cache

• LRU Cache는 캐시에 공간이 부족할 때 가장 오랫동안 사용하지 않은 항목을 제거하고 새로운 녀석을 배치하는 형식으로 동작
• LRU Cache의 사용 관점 → '오랫동안 사용되지 않은 항목은 앞으로도 사용되지 않을 가능성이 높기에, 가장 오랫동안 참조되지 않은 녀석을 캐시에서 제거하자'
• LRU Cache를 통해 캐시 메모리의 히트율을 높이는 것은 입증됐으며, 현재 가장 많이 사용되는 알고리즘 중 하나임

 

구현 방식

• LRU Cache 의 구현은 Double Linked List를 이용
• Head에 가까운 데이터일수록 최근에 사용된 데이터
• Tail에 가까울 수록 오랫동안 사용되지 않은 데이터로 간주
• 새로운 데이터를 삽입할 때, Tail 값을 가장 먼저 삭제시키고 Head에 데이터를 삽입
• 캐시에 적재된 어떤 데이터를 사용한 경우, 해당 데이터를 Head로 옮겨 가장 최근에 사용된 값임을 표시 → 삭제 우선순위에서 멀어짐
• 캐시 교체 시간 복잡도 → O(1)

 

LRU Cache 순서 방식 도식화

 

참고 자료

• https://velog.io/@haero_kim/LRU-Cache-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0