在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 |
情况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 |
【贝拉迪异常(Belady’ s Anomaly)】因此, 在该示例中, 页面错误的数量通过增加帧的数量而增加, 因此这遭受了Belady’ sAnomaly的困扰。
推荐阅读
- 二进制信号量或互斥量
- Win10系统组策略编辑器怎样打开?
- Win10系统网络连接受限怎样处理？
- Win10如何迅速显示桌面？
- Win10笔记本蓝牙怎样打开？
- Win10系统故障的有效果处理办法
- Win10笔记本无线网络禁用后怎样打开?
- Win10系统怎样升级显卡驱动？
- Win10系统怎样关闭445端口？