为什么LRU不会遭受贝拉迪异常？
我有一个关于页面替换算法的问题。 FIFO 会受到 Belady 异常 的影响，但 LRU 不会。有谁知道为什么 LRU 不受影响？我一直在互联网上寻找原因但没有运气。
I have a question about page replacement algorithms. FIFO suffers from Belady's Anomaly but LRU doesn't. Does anyone know why LRU doesn't suffer? I've been searching for the reason on the internet but no luck.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
因为LRU是一种堆叠算法，并且使用k帧将始终是LRU的k+n帧的子集。因此，任何可能在 k + n 帧中发生的页面错误也将在 k 帧中发生，这又意味着 LRU 不会遭受 Belady 异常的影响。
Because LRU is a stacking algorithm, and using k frames will always be a subset of k + n frames for LRU. Thus, any page-faults that may occur for k + n frames will also occur for k frames, which in turn means that LRU doesn't suffer Belady's anomaly.
因为 FIFO 假设某个页面已占用内存很长时间，更换它是最安全的，但实际上情况并非如此。相反，从统计上看，FIFO 失败的地方是，如果一个页面被频繁调用，那么它比最近被调用的另一个页面更有可能被再次调用。换句话说，频率比年龄更能决定页面加载。
Because FIFO assumes that the mere fact that a page has been occupying memory for a long time that it is the safest to replace, where in reality that simply isn't the case. Rather, where FIFO fails is that statistically, if a page has been called frequently, it's more likely to be called again than another page which has been called recently. In other words, frequency is a far better determiner of page loading than age.
与卡斯帕的答案类似，但我发现我的教科书（稍作编辑）中的解释更清楚一些。
Silberschatz, A.、Galvin, PB 和加涅，G.（2014）。操作系统概念（第 9 版）。新加坡：威利。
Similar to Caspar's answer, however I found the explanation from my textbook (slightly edited) to be a bit more clear.
Silberschatz, A., Galvin, P. B., & Gagne, G. (2014). Operating System Concepts (9th ed.). Singapore: Wiley.