无法理解Belady的异常

Question

所以Belady的Anomaly指出,当使用FIFO页面替换策略时,当添加更多页面空间时,我们会有更多的页面错误.

我的直觉说我们应该减少或最多相同数量的页面错误,因为我们添加了更多的页面空间.

如果我们将FIFO队列视为管道,添加更多页面空间就像使管道更大:

 ____
O____O  size 4

 ________
O________O  size 8

那么,为什么会出现更多页面错误？我的直觉说,使用更长的管道,你需要花费更长的时间才能开始出现页面错误(因此,使用无限管道,你没有页面错误)然后你会遇到同样多的页面错误,就像通常与较小的管道一样.

我的推理出了什么问题？

Answer 1

之所以在使用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队列中比较小的高速缓存大小提出,以便导致更大的高速缓存大小具有更高的故障特定(可能是罕见的)访问模式下的速率.

Answer 2

这句话是错误的,因为它过于概括:

Belady的Anomaly指出,当使用FIFO页面替换策略时,当添加更多页面空间时,我们会有更多的页面错误

这是一个更正版本:

"Belady的Anomaly表示,当使用FIFO页面替换策略时,当添加更多页面空间时,一些内存访问模式实际上会导致更多的页面错误."

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