algorithm - LFU 页面回收算法有 belady 异常吗？

Question

我在网上发现 LFU 是一种堆栈算法，但是当我问我的讲师他说它患有 belady 异常，但我已经尝试了很多例子，但没有找到任何证据来证明这一点，所以有人可以告诉我是否可以真的患上了吗？还是堆栈算法？如果确实存在问题，请举个例子，谢谢!

Answer 1

http://www.eecs.berkeley.edu/Pubs/TechRpts/1987/CSD-87-358.pdf 1.3 节定义了堆栈算法，并通过 LFU 的示例完成。基本上，您可以在跟踪内存提取时维护一个堆栈，如果您的内存中有 i 个条目的容量，则堆栈的顶部 i 条目是将保存在内存中的条目。由于您可以维护这样一个堆栈，因此更大的内存必须始终保存核心中为任何更小的内存保留的所有条目，因此 Belady 的异常是不可能的。

当然，这假设了具有无限容量计数器的 LFU 的精确实现。