srcmini在LRU和最佳页面替换算法的情况下, 可以看出, 如果我们增加帧数, 则页面错误的数量将减少。但是, Balady发现, 在FIFO页面替换算法中, 页面错误数将随着帧数的增加而增加。
在某些情况下, 这是FIFO算法显示的奇怪行为。这是一个异常, 称为Belady’s Anomaly。
让我们研究这样的例子：
参考字符串为0 1 5 3 0 1 4 0 1 5 34。让我们分析两种情况下FIFO算法的行为。
情况1：帧数= 3
| Request | 0 | 1 | 5 | 3 | 0 | 1 | 4 | 0 | 1 | 5 | 3 | 4 |
| Frame 3 | 5 | 5 | 5 | 1 | 1 | 1 | 1 | 1 | 3 | 3 | ||
| Frame 2 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 5 | 5 | 5 | |
| Frame 1 | 0 | 0 | 0 | 3 | 3 | 3 | 4 | 4 | 4 | 4 | 4 | 4 |
| Miss/Hit | Miss | Miss | Miss | Miss | Miss | Miss | Miss | Hit | Hit | Miss | Miss | Hit |
页面错误数= 9
情况2：帧数= 4
| Request | 0 | 1 | 5 | 3 | 0 | 1 | 4 | 0 | 1 | 5 | 3 | 4 |
| Frame4 | 3 | 3 | 3 | 3 | 3 | 3 | 5 | 5 | 5 | |||
| Frame3 | 5 | 5 | 5 | 5 | 5 | 5 | 1 | 1 | 1 | 1 | ||
| Frame 2 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 4 | |
| Frame1 | 0 | 0 | 0 | 0 | 0 | 0 | 4 | 4 | 4 | 4 | 3 | 3 |
| Miss/Hit | Miss | Miss | Miss | Miss | Hit | Hit | Miss | Miss | Miss | Miss | Miss | Miss |
页面错误数= 10
因此, 在该示例中, 页面错误的数量通过增加帧的数量而增加, 因此这遭受了Belady’sAnomaly的困扰。
评论前必须登录！
注册