（9 分）一个进程分配给 4 个页帧（下面的所有数字均为十进制数，每一项都是从 0 开始计数的）。最后一次把一页装入到一个页帧的时间、最后一次访问页帧中的页的时间、每个页帧中的虚页号以及每个页帧的访问位（R）和修改位（M）如下表所示（时间均为从进程开始到该事件之前的时钟值，而不是从事件发生到当前的时钟值）。

当虚页 4 发生缺页时，使用下列存储器管理策略，哪一个页帧将用于置换？解释每种情况的原因。

（1）FIFO（先进先出）算法。

（2）LRU（最近最少使用）算法。

（3）改进的 Clock 算法。

（4）在缺页之前给定上述的存储器状态，考虑下面的虚页访问串：

4, 0, 0, 0, 2, 4, 2, 1, 0, 3, 2

如果使用 LRU 页面置换算法，分给 4 个页帧，会发生多少缺页？

协议数据单元

[tag_link]

**【答案】** （1）页帧3 （2）页帧1 （3）页帧1 （4）3次缺页

**【解析】** （1）FIFO算法基于页面加载时间，选择加载时间最早的页面置换。表中加载时间分别为：页帧0（60）、页帧1（130）、页帧2（26）、页帧3（20）。页帧3的加载时间最早（20），因此用于置换。

（2）LRU算法基于最近访问时间，选择访问时间最早的页面置换。表中访问时间分别为：页帧0（161）、页帧1（160）、页帧2（162）、页帧3（163）。页帧1的访问时间最早（160），因此用于置换。

（3）改进的Clock算法优先选择R=0且M=0的页面。表中页帧状态：页帧0（R=0, M=1）、页帧1（R=0, M=0）、页帧2（R=1, M=0）、页帧3（R=1, M=1）。页帧1满足R=0且M=0，因此用于置换。算法扫描时（假设从页帧0开始），遇到页帧1即选中，无需进一步扫描。

（4）使用LRU算法模拟虚页访问串。初始内存中有虚页0、1、2、3，最后访问时间如表所示（虚页1最早，虚页3最晚）。模拟过程：

• 访问虚页4：缺页，置换LRU页面虚页1（页帧1），装入虚页4。
• 访问虚页0：命中，更新访问时间。
• 访问虚页0：命中，更新访问时间。
• 访问虚页0：命中，更新访问时间。
• 访问虚页2：命中，更新访问时间。
• 访问虚页4：命中，更新访问时间。
• 访问虚页2：命中，更新访问时间。
• 访问虚页1：缺页，置换LRU页面虚页3（页帧3），装入虚页1。
• 访问虚页0：命中，更新访问时间。
• 访问虚页3：缺页，置换LRU页面虚页4（页帧1），装入虚页3。
• 访问虚页2：命中，更新访问时间。 缺页发生在访问4、1、3时，共3次缺页。