无法理解Belady的异常

Question

因此，Belady的异常指出，使用FIFO页面替换策略时，添加更多页面空间时，我们将有更多页面故障。

我的直觉说，我们最多应该少或最多，与添加更多页面空间相同的页面故障。

如果我们将FIFO队列视为管道，那么添加更多的页面空间就像使管道更大：

 ____
O____O  size 4

 ________
O________O  size 8

那么，为什么要获得更多页面错误？我的直觉说，使用较长的管道，您需要更长的时间才能开始出现页面故障（因此，使用无限管道，您不会有页面故障）通常和较小的管道一样。

我的推理怎么了？

Answer 1

当使用FIFO时，增加页面数量可以在某些访问模式下增加故障率，因为当您有更多页面时，最近请求的页面可以保留在FIFO队列的底部。

考虑第三次在此处的Wikipedia示例中要求“ 3”：http://en.wikipedia.org/wiki/belady%27S_anomaly

页面故障用“ F”标记。

1:

Page Requests   3    2    1    0    3    2    4    3    2    1    0    4
Newest Page     3f   2f   1f   0f   3f   2f   4f   4    4    1f   0f   0
                     3    2    1    0    3    2    2    2    4    1    1
Oldest Page               3    2    1    0    3    3    3    2    4    4

2:

Page Requests   3    2    1    0    3    2    4    3    2    1    0    4
Newest Page     3f   2f   1f   0f   0    0    4f   3f   2f   1f   0f   4f
                     3    2    1    1    1    0    4    3    2    1    0
                          3    2    2    2    1    0    4    3    2    1
Oldest Page                    3    3    3    2    1    0    4    3    2

在第一个示例（较少的页面）中，有9页故障。

在第二个示例（有更多页面）中，有10页故障。

使用FIFO时，增加缓存的大小会更改删除项目的顺序。哪个 一些 案例可以增加故障率。

Belady的异常并未陈述有关缓存大小的断层率的总体趋势。因此，您的推理（将缓存视为管道），在一般情况下，这不是错误的。

总结：Belady的异常指出，有可能利用这样一个事实，即较大的缓存大小可能会导致高速缓存中的物品在FIFO队列中升高的尺寸比较小的高速缓存尺寸，以使较大的高速缓存尺寸具有更高的故障在特定（可能是罕见的）访问模式下的速率。

Answer 2

这个陈述是错误的，因为它是 过度概括:

Belady的异常指出，使用FIFO页面替换策略时，添加更多页面空间时，我们会有更多页面故障

这是一个更正的版本：

“ Belady的异常指出，使用FIFO页面替换策略时，添加更多页面空间时， 一些 内存访问模式实际上会导致更多页面故障。”

换句话说...是否观察到异常取决于实际的内存访问模式。

Answer 3

Belady的异常发生在页面替换算法中不关注堆栈算法。有时可能发生在FIFO中，甚至可能发生随机的页面更换，而不是LRU或最佳。

Answer 4

简而言之，我们可以说“添加更多帧可能会导致更多页面故障”。

Answer 5

Belady的异常发生在FIFO方案中，仅当当前被推荐的页面是从主内存中删除的页面。只有在这种情况下，即使您增加了更多的页面空间，您也会有更多的页面故障。