无法理解Belady的异常

所以Belady的Anomaly声明，当使用FIFO页面替换策略时，当添加更多页面空间时，我们会有更多的页面错误。我的直觉说我们应该减少或最多相同数量的页面错误，因为我们添加了更多的页面空间。如果我们将FIFO队列视为管道，添加更多页面空间就像使管道更大：

 ____
O____O  size 4

 ________
O________O  size 8

那么，为什么会出现更多页面错误？我的直觉说，使用更长的管道，你需要花费更长的时间来开始出现页面错误（因此，使用无限管道，你没有页面错误）然后你会遇到同样多的页面错误，就像通常与较小的管道一样。我的推理出了什么问题？

已邀请:

5 个回复

土投

之所以在使用FIFO时，增加页数会增加某些访问模式的故障率，是因为当你有更多页面时，最近请求的页面可以保留在FIFO队列的底部更长。考虑第三次在维基百科示例中请求“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的Anomaly没有说明有关高速缓存大小的故障率的一般趋势。所以你的推理（关于将缓存视为管道），在一般情况下是没有错的。综上所述： Belady的Anomaly指出，有可能利用这样一个事实，即较大的高速缓存大小可能导致高速缓存中的项目在FIFO队列中比较小的高速缓存大小提出，以便使更大的高速缓存大小在更高的高速缓存下具有更高的故障率。特定的（也可能是罕见的）访问模式。

镰茧钩

这句话是错误的，因为它过于概括： Belady的Anomaly指出，当使用FIFO页面替换策略时，当添加更多页面空间时，我们会有更多的页面错误这是一个更正版本： “Belady的Anomaly表示，当使用FIFO页面替换策略时，当添加更多页面空间时，一些内存访问模式实际上会导致更多页面错误。” 换句话说......是否观察到异常取决于实际的存储器访问模式。