가짜 LRU 알고리즘에 대한 설명에는 이진 검색 트리를 사용하고 트리에 액세스 할 때마다 검색중인 노드에서 플래그를 "포인트 어웨이"로 설정하는 것이 포함됩니다.가짜 LRU 트리 알고리즘
이것은 LRU의 합리적인 근사값을 유도합니다. 그러나 LRU로 간주되는 모든 노드는 리프 노드라고 설명하는 것으로 보입니다. 리프가 아닌 노드가 적합한 LRU 후보인지 결정하는 동안 여전히 안정적으로 수행되는 정적 트리를 처리하는 의사 LRU 알고리즘이 있습니까?
편집 : 이미 해시 맵과 연결된 목록을 사용하여 LRU를 구현했습니다. 나는 pseudo lru tree를 사용할 때 성능에 미치는 영향 (특히 동시 읽기)에 관심이있다. 그래서 내가 pseudo lru tree 알고리즘에 대해 구체적으로 물어 보았습니다.하지만 분명하게 이해해야합니다.
항상 빨간색의 검은 색 나무를 사용하여 내부 노드를 리프로 밀어 넣을 수 있습니다.
나무를 균형있게 유지하면 힘들 수 있습니다. 그러나 어떤 하위 트리를 밀어 내려야 할지를 선택할 수 있으므로 불가능할 수도 있습니다.
동시 읽기를 허용하도록 트리 구조를 정적으로 유지하려고합니다. 성능상의 이유로 (깃발에 경주 조건이 있다는 것을 알지만 어쨌든 의사 LRU이므로 걱정하지 않아도됩니다.) – patros
어떻게 나무를 고정적으로 유지합니까? 제거하려는 노드와 추가하는 노드에는 동일한 키가 없으므로 트리의 다른 부분으로 이동합니다. 당신은 "캐시 히트 중에 정적"을 의미하므로 룩업을 위해 읽기 잠금을 사용할 수 있습니까? –
키는 동일하게 유지됩니다. 내 데이터를 임의의 인덱스 (0에서 (2^깊이) -1)에 매핑합니다. 내가 "제거"할 때 나는 그 노드의 노드를 사용 가능한 노드 목록에 추가합니다. 추가 할 때 노드를 추가하지 않고 단순히 노드가 보유한 데이터를 덮어 씁니다. 이렇게하면 트리 구조가 정적으로 유지되지만 데이터는 여전히 변경 가능합니다. – patros
Study of Different Cache Line Replacement Algorithms in Embedded Systems에 제시된 벤치 마크 번호에 따르면 pseudo-LRU (PLRUm, PLRUt, MPLRU)는 구현 후보로 가장 적합합니다 .
아마도 이렇게하면 hashtable + linkedlist를 사용하게됩니다. http://stackoverflow.com/questions/2504178/lru-cache-design/2504317#2504317 –