IT 학습 용어
LRU (Least Recently Used)
hippo 데브옵스
2022. 6. 27. 00:27
- 운영체제의 페이지 교체 알고리즘 중 하나
- 페이지를 교체할 때 가장 오랫동안 사용되지 않은 페이지를 교체 대상으로 삼는 기법
LRU Cache
- LRU Cache는 캐시에 공간이 부족할 때 가장 오랫동안 사용하지 않은 항목을 제거하고 새로운 녀석을 배치하는 형식으로 동작
- LRU Cache의 사용 관점 → '오랫동안 사용되지 않은 항목은 앞으로도 사용되지 않을 가능성이 높기에, 가장 오랫동안 참조되지 않은 녀석을 캐시에서 제거하자'
- LRU Cache를 통해 캐시 메모리의 히트율을 높이는 것은 입증됐으며, 현재 가장 많이 사용되는 알고리즘 중 하나임
구현 방식
- LRU Cache 의 구현은 Double Linked List를 이용
- Head에 가까운 데이터일수록 최근에 사용된 데이터
- Tail에 가까울 수록 오랫동안 사용되지 않은 데이터로 간주
- 새로운 데이터를 삽입할 때, Tail 값을 가장 먼저 삭제시키고 Head에 데이터를 삽입
- 캐시에 적재된 어떤 데이터를 사용한 경우, 해당 데이터를 Head로 옮겨 가장 최근에 사용된 값임을 표시 → 삭제 우선순위에서 멀어짐
- 캐시 교체 시간 복잡도 → O(1)
LRU Cache 순서 방식 도식화
참고 자료