为什么LRU不会遭受Belady的异常？

Question

我有一个关于页面替换算法的问题.FIFO受到Belady的Anomaly的影响,但LRU没有.有谁知道为什么LRU不受影响？我一直在互联网上寻找原因,但没有运气.

Answer 1

因为LRU是堆叠算法,并且使用k帧将始终是LRU的k + n帧的子集.因此,对于k +帧,也可能发生k + n帧可能发生的任何页面错误,这反过来意味着LRU不会遭受Belady的异常.

Answer 2

由于FIFO假定这一事实,一个页面已经被占用的内存很长一段时间,这是更换最安全的,而实际上,根本不是这样的.相反,在FIFO失败的情况下,统计上,如果频繁调用页面,则比最近调用的另一个页面更可能再次调用.换句话说,频率是一个比年龄更好的页面加载决定因素.

Answer 3

与 Caspar 的回答类似，但是我发现我的教科书（略有编辑）中的解释更清楚一些。

[ LRU属于]对类的页面替换算法，称为堆栈算法，[其中]永远不能表现出Belady的异常。

堆栈算法是一种算法，它可以证明内存中 N 帧的页面集始终是内存中包含 N + 1 帧的页面集的子集。[因此，额外的帧永远不会导致额外的页面错误。]

对于 LRU 替换，内存中的页面集将是 N 个最近引用的页面。如果帧数增加，这 N 个页面仍将是最近引用的页面，因此仍会在内存中。

Silberschatz, A., Galvin, PB, & Gagne, G. (2014)。操作系统概念（第 9 版）。新加坡：威利。