Least Recently Used
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
Least Recently Used(LRU)는 가장 최근에 사용되지 않은 항목을 우선적으로 교체하는 캐시 알고리즘이다. 연결 리스트와 연관 배열을 조합하여 O(1)의 시간 복잡도로 계산할 수 있으며, CPU 캐시 메모리에서는 처리 간소화된 유사 LRU가 사용된다. 특정 패턴에서는 성능이 저하될 수 있으며, 최종 사용 시점과 캐시 복원 비용을 함께 고려한 파생형 알고리즘도 존재한다. 컴퓨터 캐시 외에도 정리법에도 활용되며, 사용하지 않는 물건을 가장자리로 밀어내는 방식으로 적용된다.
더 읽어볼만한 페이지
| Least Recently Used |
|---|
2. 구체적인 알고리즘
LRU 알고리즘은 크게 일반적인 경우와 CPU 캐시 메모리의 경우로 나눌 수 있다.
일반적인 경우, 연결 리스트와 연관 배열을 조합하여 사용하면 (예: Java의 LinkedHashMap[1]) O(1)의 시간 복잡도로 계산이 가능하다. 연관 배열을 통해 캐시에서 데이터를 가져오고 참조된 경우 연결 리스트의 끝으로 이동시키며, 캐시에 삽입하는 것 모두 O(1)이다.
CPU 캐시 메모리에서는 각 항목마다 "언제 사용했는지"를 나타내는 데이터를 저장하고, 항목을 사용할 때마다 이 데이터를 갱신하여 이상적인 LRU 알고리즘을 구현할 수 있다. 그러나 이 방법은 모든 항목의 시간 정보를 확인해야 하므로 처리 시간이 많이 소요되어(O(n)) 거의 사용되지 않는다.[1] LinkedHashMap과 같은 기법도 CPU 캐시 메모리에는 계산량이 너무 많아 사용하기 어렵다.[1]
대부분의 경우, 처리를 간소화한 유사 LRU 기법이 사용된다.[1] 예를 들어, 모든 항목에 "최근에 사용했는지"를 나타내는 플래그(dirty flag)를 설정한다. 이 플래그는 한 번 모두 리셋된 후, 항목이 사용될 때마다 설정된다. 일정 시점이나 항목 갱신 시에 이 플래그들을 확인하면 "최근에 사용되지 않은 항목"을 파악할 수 있으며, 적절한 시기에 모든 플래그를 다시 리셋한다.[1] 이러한 방식은 완전한 LRU는 아니지만, 대부분의 경우 LRU와 매우 근접한 성능을 보인다.[1]
단순히 최종 사용 시점뿐만 아니라, 캐시에 복원하는 비용 (예: 계산 결과의 캐시인 경우 재계산에 걸리는 시간)도 고려하여 알고리즘을 구축하는 방법 등이 있다.
2. 1. 일반적인 경우
연결 리스트와 연관 배열을 조합하여 사용하면 (예: Java의 LinkedHashMap[1]) O(1)의 시간 복잡도로 계산이 가능하다. 연관 배열을 통해 캐시에서 데이터를 가져오는 것은 O(1)이며, 참조된 경우 연결 리스트의 끝으로 이동시키면 되는데, 이 역시 O(1)이다. 캐시에 삽입하는 것도 마찬가지로 O(1)이다.2. 2. CPU 캐시 메모리의 경우
CPU 캐시 메모리에서는 각 항목마다 "언제 사용했는지"를 나타내는 데이터를 저장하고, 항목을 사용할 때마다 이 데이터를 갱신하는 방식으로 이상적인 LRU 알고리즘을 구현할 수 있다. 그러나 이 방법은 모든 항목의 시간 정보를 확인해야 하므로 처리 시간이 많이 소요되어(O(n)) 거의 사용되지 않는다.[1] LinkedHashMap과 같은 기법도 CPU 캐시 메모리에는 계산량이 너무 많아 사용하기 어렵다.[1]대부분의 경우, 처리를 간소화한 유사 LRU 기법이 사용된다.[1] 예를 들어, 모든 항목에 "최근에 사용했는지"를 나타내는 플래그(dirty flag)를 설정한다.[1] 이 플래그는 한 번 모두 리셋된 후, 항목이 사용될 때마다 설정된다.[1] 일정 시점이나 항목 갱신 시에 이 플래그들을 확인하면 "최근에 사용되지 않은 항목"을 파악할 수 있으며, 적절한 시기에 모든 플래그를 다시 리셋한다.[1]
이러한 방식은 완전한 LRU는 아니지만, 대부분의 경우 LRU와 매우 근접한 성능을 보인다.[1]
2. 3. 파생형
단순히 최종 사용 시점뿐만 아니라, 캐시에 복원하는 비용 (예: 계산 결과의 캐시인 경우 재계산에 걸리는 시간)도 고려하여 알고리즘을 구축하는 방법 등이 있다.3. 정리법
LRU는 컴퓨터뿐만 아니라 노구치 유키오의 『「초」정리법』에도 사용된다. 예를 들어, 다 읽은 책을 책장의 가장 오른쪽에 꽂으면, 왼쪽에는 자주 읽지 않는 책이 모이게 되어 버려야 할 책을 쉽게 고를 수 있다. 사용하지 않는 물건이 가장자리로 밀려나기 때문에, 노구치 유키오는 이 방법을 밀어내기법(밀어내기 파일링)이라고 부른다.[2]
참조
[1]
웹사이트
LinkedHashMap (Java SE 17 & JDK 17)
https://docs.oracle.[...]
2023-07-04
[2]
서적
「超」整理法―情報検索と発想の新システム
中央公論新社
1993-11-01
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com