页面置换算法 在请求调页的虚存系统中，对于如下的页面访问序列： 7， 0，1 ，2 ，0， 3 ，0， 4 ， 2 ，3 ，0 ， 3， 2，1，2 ， 0，4，当内存块数量为 3时（开始为空），试问：产生的缺页中断次数是多少（要求画表格进行表述页面置换过程）？页面置换次数是多少？缺页中断率是多少？ 分别使用OPT、FIFO、LRU算法 FIFO算法再设置4个内存块，观察Belady现象

当内存块数量为3时，各算法的缺页中断次数和页面置换次数如下：

1. OPT算法

| 页面号 | 内存块状态 | 缺页中断次数 | 页面置换次数 |
| ------ | ---------- | ------------ | ------------ |
| 7 | 7 | 1 | 0 |
| 0 | 7 0 | 1 | 0 |
| 1 | 7 0 1 | 1 | 0 |
| 2 | 2 0 1 | 2 | 1 |
| 0 | 2 0 1 | 2 | 0 |
| 3 | 2 0 3 | 3 | 1 |
| 0 | 2 0 3 | 3 | 0 |
| 4 | 4 0 3 | 4 | 1 |
| 2 | 4 0 2 | 5 | 1 |
| 3 | 4 3 2 | 6 | 1 |
| 0 | 4 3 0 | 7 | 1 |
| 3 | 4 3 0 | 7 | 0 |
| 2 | 4 3 2 | 8 | 1 |
| 1 | 1 3 2 | 9 | 1 |
| 2 | 1 3 2 | 9 | 0 |
| 0 | 1 3 0 | 10 | 1 |
| 4 | 4 3 0 | 11 | 1 |

缺页中断次数为11，页面置换次数为7，缺页中断率为(11/18)×100%=61.11%。

2. FIFO算法

| 页面号 | 内存块状态 | 缺页中断次数 | 页面置换次数 |
| ------ | ---------- | ------------ | ------------ |
| 7 | 7 | 1 | 0 |
| 0 | 7 0 | 1 | 0 |
| 1 | 7 0 1 | 1 | 0 |
| 2 | 2 0 1 | 2 | 1 |
| 0 | 2 0 1 | 2 | 0 |
| 3 | 3 0 1 | 3 | 1 |
| 0 | 3 0 1 | 3 | 0 |
| 4 | 4 0 1 | 4 | 1 |
| 2 | 4 2 1 | 5 | 1 |
| 3 | 4 2 3 | 6 | 1 |
| 0 | 0 2 3 | 7 | 1 |
| 3 | 0 2 3 | 7 | 0 |
| 2 | 0 2 3 | 7 | 0 |
| 1 | 1 2 3 | 8 | 1 |
| 2 | 1 2 3 | 8 | 0 |
| 0 | 1 0 3 | 9 | 1 |
| 4 | 4 0 3 | 10 | 1 |

缺页中断次数为10，页面置换次数为7，缺页中断率为(10/18)×100%=55.56%。

3. LRU算法

| 页面号 | 内存块状态 | 缺页中断次数 | 页面置换次数 |
| ------ | ---------- | ------------ | ------------ |
| 7 | 7 | 1 | 0 |
| 0 | 7 0 | 1 | 0 |
| 1 | 7 0 1 | 1 | 0 |
| 2 | 2 0 1 | 2 | 1 |
| 0 | 0 2 1 | 3 | 1 |
| 3 | 3 2 1 | 4 | 1 |
| 0 | 3 2 0 | 5 | 1 |
| 4 | 4 2 0 | 6 | 1 |
| 2 | 4 2 2 | 7 | 1 |
| 3 | 4 3 2 | 8 | 1 |
| 0 | 0 3 2 | 9 | 1 |
| 3 | 0 3 2 | 9 | 0 |
| 2 | 0 2 3 | 10 | 1 |
| 1 | 1 2 3 | 11 | 1 |
| 2 | 1 2 3 | 11 | 0 |
| 0 | 0 2 3 | 12 | 1 |
| 4 | 4 2 3 | 13 | 1 |

缺页中断次数为13，页面置换次数为7，缺页中断率为(13/18)×100%=72.22%。

当内存块数量从3增加到4时，FIFO算法产生Belady现象，导致缺页中断次数增加：

| 页面号 | 内存块状态 | 缺页中断次数 |
| ------ | ---------- | ------------ |
| 7 | 7 | 1 |
| 0 | 7 0 | 1 |
| 1 | 7 0 1 | 1 |
| 2 | 2 0 1 | 2 |
| 0 | 2 0 1 | 2 |
| 3 | 3 0 1 | 3 |
| 0 | 3 0 1 | 3 |
| 4 | 4 0 1 | 4 |
| 2 | 4 2 1 | 5 |
| 3 | 4 2 3 | 6 |
| 0 | 0 2 3 | 7 |
| 3 | 0 2 3 | 7 |
| 2 | 0 2 3 | 7 |
| 1 | 1 2 3 | 8 |
| 2 | 1 2 3 | 8 |
| 0 | 0 2 3 0 | 9 |
| 4 | 4 2 3 0 | 10 |

缺页中断次数从10增加到了12，这就是Belady现象。