（7 分）设一个没有设置快表的虚拟页式存储系统，页面大小为 100 字节。一个仅有 460 个字节的程序有下述内存访问序列（下标从 0 开始）： 10、11、104、170、73、309、185、245、246、434、458、364。 为该程序分配有 2 个可用页帧（Page frame）。试问：
（1）试叙述缺页中断与一般中断的主要区别？ （2）若分别采用 FIFO 和 LRU 算法，试计算访问过程中发生多少次缺页中断？ （3）若一次访存的时间是 10ms，平均缺页中断处理时间为 25ms，为使该虚拟存储系统的平均有效访问时间不大于 22ms，则可接受的最大缺页中断率是多少？
[tag_link]
**【解析】** 本题考查缺页中断和页面置换算法。
（1）缺页中断是一种特殊的中断，它与一般中断的区别是： ① 在指令执行期间产生和处理中断信号。CPU 通常在一条指令执行完后检查是否有中断请求，而缺页中断是在指令执行时间，发现所要访问的指令或数据不在内存时产生和处理的； ② 一条指令在执行期间可能产生多次缺页中断。如一条读取数据的多字节指令，指令本身跨越两个页面，若指令后一部分所在页面和数据所在页面均不在内存，则该指令的执行至少产生两次缺页中断。
（2）每个页面大小为 100 字节，则页面的访问顺序如下：
| 10 | 11 | 104 | 170 | 73 | 309 | 185 | 245 | 246 | 434 | 458 | 364 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 0 | 3 | 1 | 2 | 2 | 4 | 4 | 3 |
采用 FIFO 算法的页面置换情况如下表，共产生缺页中断 6 次。
| 走向 | 0 | 0 | 1 | 1 | 0 | 3 | 1 | 2 | 2 | 4 | 4 | 3 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 块号 1 | 0 | 0 | 1 | 1 | 1 | 3 | 3 | 2 | 2 | 4 | 4 | 3 |
| 块号 2 | 0 | 0 | 0 | 1 | 1 | 3 | 3 | 2 | 2 | 4 | ||
| 淘汰 | 0 | 1 | 3 | 2 | ||||||||
| 缺页 | √ | √ | √ | √ | √ | √ |
采用 LRU 算法的页面置换情况如下表，共产生缺页中断 7 次。
| 走向 | 0 | 0 | 1 | 1 | 0 | 3 | 1 | 2 | 2 | 4 | 4 | 3 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 块号 1 | 0 | 0 | 1 | 1 | 0 | 3 | 1 | 2 | 2 | 4 | 4 | 3 |
| 块号 2 | 0 | 0 | 1 | 0 | 3 | 1 | 1 | 2 | 2 | 4 | ||
| 淘汰 | 1 | 0 | 3 | 1 | 1 | 2 | ||||||
| 缺页 | √ | √ | √ | √ | √ | √ | √ |
（3）设可接受的最大缺页中断率为 。若要访问页面在内存中，一次访问的时间是 10ms（访问内存页表）+ 10ms（访问内存）= 20ms。如果不在内存，所花时间为 10ms（访问内存页表）+ 25ms（中断处理）+ 10ms（访问内存页表）+ 10ms（访问内存）= 55ms。
平均有效访问时间：
解得可接受的最大缺页中断率 为 5.7%。