LFU 페이지 교정 알고리즘이 이상한 점이 있습니까?

Question

나는 LFU가 스택 알고리즘이라는 것을 온라인으로 발견했다. 그러나 내 강사에게 그가 belady의 변칙으로 고통 받았다고 말했지만 나는 많은 것을 시도했지만 많은 것을 시도했지만 이것을 증명하지 못했다. 그게 사실이라면 라고 말해 주시겠습니까? 또는 스택 알고리즘입니까? 예를 보여주십시오. 고마워요.

Answer 1

http://www.eecs.berkeley.edu/Pubs/TechRpts/1987/CSD-87-358.pdf 섹션 1.3에서는 스택 알고리즘을 정의하고 LFU에 대한 예제를 통해 작업을 마칩니다. 기본적으로 메모리 페치의 추적을 따라 스택을 유지 관리 할 수 ​​있습니다. 스택의 맨 위 i 항목은 메모리에있는 항목의 용량이있는 경우 메모리에 보유 될 항목입니다. 그런 스택을 유지할 수 있기 때문에 더 큰 메모리는 더 작은 메모리를 위해 코어에 보관 된 모든 항목을 항상 보유해야하므로 Belady의 예외는 불가능합니다.

물론 이것은 무한 용량의 카운터가있는 LFU의 정확한 구현을 가정합니다.