极客笔记操作系统 贝拉迪异常
在LRU和最佳页面替换算法中，如果增加页面帧的数量，可以减少页面错误的数量。然而，贝拉迪发现，在FIFO页面替换算法中，页面错误的数量会随着页面帧数量的增加而增加。
这是FIFO算法在某些情况下显示出的奇怪行为。这被称为贝拉迪异常。
让我们来看一个例子：
给定的参考字符串是0 1 5 3 0 1 4 0 1 5 3 4。让我们分析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 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Frame 4 | 3 | 3 | 3 | 3 | 3 | 3 | 5 | 5 | 5 | |||
| Frame 3 | 5 | 5 | 5 | 5 | 5 | 5 | 1 | 1 | 1 | 1 | ||
| Frame 2 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 4 | |
| Frame 1 | 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’s Anomaly的影响。