在一个采用页式虚拟存储管理的系统中，某进程依次要访问的字地址序列是：115，228，128，88，446，102，321，432，260，167，若作业的第0页已经装入主存，现分配给该作业的主存共300字，页的大小为100字，回答下列问题：

问答题按FIFO调度算法将产生多少次缺页中断，依次淘汰的页号是什么?

【正确答案】如表1所示，FIFO算法产生5次缺页中断，淘汰的页号依次是0，1，2。表1 FIFO算法

【答案解析】

问答题按LRU调度算法将产生多少次缺页中断，依次淘汰的页号是什么?

【正确答案】如表2所示，LRU算法产生6次缺页中断，淘汰的页号依次是2，0，1，3。表2 LRU算法先将地址序列转换成访问串，因为每页有100字，所以访问串就是地址除100取整后得到的数字；又，题目给了300字，说明该作业在主存获得3个驻留集。下面给出两种算法的淘汰过程，其中第0页已在主存，符号“×”代表产生页故障(以下各题相同)。

【答案解析】该类题目在有的试卷上是以综合题的形式出现，不管分值大小，只要牢记每种页面替换策略的方法即可。

问答题假定占有M块内在(初始为空)的进程有一个页访问串，这个页访问串的长度为P，其中涉及Q个不同的页号。对于任何页面替换算法，计算出：
(1)缺页中断次数的下界是多少?
(2)缺页中断次数的上界是多少?

【正确答案】对于任何页面替换算法，缺页中断次数的下界是Q，缺页中断次数的上界是P。发生缺页中断的原因是当前访问的页不在内存中，需进行页面调度，将该页面调入主存，此时不管内存中是否已满(若满则选择调出一页，若不满则可直接调入)，都要发生一次缺页中断，故无论怎样安排，Q个不同页号在初次进入主存时都要发生一次缺页中断，总共发生Q次。再讨论上限为什么是P。在进行页面调度时，进入内存的页面不可能永久占有内存，会在某个时刻被调出，最坏的情况是每当访问一个页面，该页都不在主存，都要产生一次缺页中断；所以会发生P次中断，举例如下：下限：M=2，P=12，Q=4，有如下访问串： 1 1 1 2 2 3 3 3 4 4 4 4 缺页中断数为4；上限：M=2，P=12，Q=4，有如下访问串： 1 2 3 4 1 2 3 4 1 2 3 4 缺页中断数为12。

【答案解析】本题考的是对页面替换整体概念的理解。对于任何一个算法而言，衡量其优劣的标准并不是页故障的多少，因为页故障数是随着访问串的内容变化而发生变化的，本题就是要说明这一点。

问答题页面调度算法中有LRU、FIFO和Clock算法。针对以下条件，计算上述3个算法下的页面调度过程和缺页中断率，并分析为什么在3种算法中Clock算法应用得比较广泛：
●页面访问序列：2，3，2，1，5，2，4，5，3，2，5，2
●分配内存块：3块

【正确答案】LRU算法(见表1)：表1 LRU算法中断率：7/12 FIFO算法(见表2)：表2 FIFO算法中断率：9/12 Clock算法(见表3)：表3 Clock算法中断率：8/12 在页面调度算法中，OPT算法理论最优但无法实现，LRU算法性能几乎和OPT一样，但是实现相当困难，系统开销非常大，此外，虽然FIFO算法简单易行，但是性能较差。相比之述算法，Clock算法是LRU算法的变种，通过为每一块附加一个附加位记录该内存块的使用情况，比较小的开销接近了LRU的性能，故Clock算法相对而言应用比较广泛。

【答案解析】

问答题某程序访问下列页而：0，9，0，1，8，1，8，7，8，7，1，2，8，2，7，8，2，3，8，3，如果程序有3个页帧可用且使刚下列算法，将会产生多少次缺页：
(1)FWO替换算法。
(2)LRU替换算法。
(3)OPT替换算法。

【正确答案】如下表所示。 (1)FIFO替换算法产生8个缺页。 (2)LRU替换算法产生9个缺页。 (3)OPT替换算法产生7个缺页。

【答案解析】