—个进程在磁盘上包含8个虚拟页(0号~7号)，在主存中固定分配给3个物理块[1]，发生如下顺序的页访问：4,3,2,1,4,3,5,4,3,2,1,5假设这些物理块最初是空的。如果使用LRU 算法，缺页次数为___(只填数字)___次。如果使用FIFO算法，缺页次数为___(只填数字)___次。如果使用OPT算法，缺页次数为___(只填数字)___次。
—个进程在磁盘上包含8个虚拟页(0号~7号)，在主存中固定分配给3个物理块[1]，发生如下顺序的页访问：
4,3,2,1,4,3,5,4,3,2,1,5
假设这些物理块最初是空的。
如果使用LRU 算法，缺页次数为___(只填数字)___次。
如果使用FIFO算法，缺页次数为___(只填数字)___次。
如果使用OPT算法，缺页次数为___(只填数字)___次。
题目解答
答案
根据给定的页访问序列和初始状态，我们按照上述思路进行计算。
LRU算法：
初始状态：物理块为空
页访问序列：4,3,2,1,4,3,5,4,3,2,1,5
物理块状态：空，空，空
缺页次数：0（初始状态）
4 -> 缺页，物理块状态：4，空，空，缺页次数：1
3 -> 缺页，物理块状态：4，3，空，缺页次数：2
2 -> 缺页，物理块状态：4，3，2，缺页次数：3
1 -> 缺页，物理块状态：1，3，2，缺页次数：4
4 -> 命中，物理块状态不变，缺页次数：4
3 -> 命中，物理块状态不变，缺页次数：4
5 -> 缺页，物理块状态：5，3，2，缺页次数：5
4 -> 命中，物理块状态不变，缺页次数：5
3 -> 命中，物理块状态不变，缺页次数：5
2 -> 命中，物理块状态不变，缺页次数：5
1 -> 缺页，物理块状态：1，3，2，缺页次数：6
5 -> 缺页，物理块状态：1，5，2，缺页次数：7
综上，LRU算法的缺页次数为 7 次。
FIFO算法：
初始状态：物理块为空
页访问序列：4,3,2,1,4,3,5,4,3,2,1,5
物理块状态：空，空，空
缺页次数：0（初始状态）
4 -> 缺页，物理块状态：4，空，空，缺页次数：1
3 -> 缺页，物理块状态：4，3，空，缺页次数：2
2 -> 缺页，物理块状态：4，3，2，缺页次数：3
1 -> 缺页，物理块状态：4，3，1，缺页次数：4
4 -> 命中，物理块状态不变，缺页次数：4
3 -> 命中，物理块状态不变，缺页次数：4
5 -> 缺页，物理块状态：4，3，5，缺页次数：5
4 -> 命中，物理块状态不变，缺页次数：5
3 -> 命中，物理块状态不变，缺页次数：5
2 -> 命中，物理块状态不变，缺页次数：5
1 -> 缺页，物理块状态：4，3，1，缺页次数：6
5 -> 缺页，物理块状态：4，3，5，缺页次数：7
综上，FIFO算法的缺页次数为 7 次。
OPT算法：
初始状态：物理块为空
页访问序列：4,3,2,1,4,3,5,4,3,2,1,5
物理块状态：空，空，空
缺页次数：0（初始状态）
4 -> 缺页，物理块状态：4，空，空，缺页次数：1
3 -> 缺页，物理块状态：4，3，空，缺页次数：2
2 -> 缺页，物理块状态：4，3，2，缺页次数：3
1 -> 缺页，物理块状态：4，3，1，缺页次数：4
4 -> 命中，物理块状态不变，缺页次数：4
3 -> 命中，物理块状态不变，缺页次数：4
5 -> 缺页，物理块状态：5，3，1，缺页次数：5
4 -> 命中，物理块状态不变，缺页次数：5
3 -> 命中，物理块状态不变，缺页次数：5
2 -> 命中，物理块状态不变，缺页次数：5
1 -> 缺页，物理块状态：1，3，2，缺页次数：6
5 -> 缺页，物理块状态：1，5，2，缺页次数：7
综上，OPT算法的缺页次数为 7 次。
通过以上计算，得到LRU算法、FIFO算法和OPT算法的缺页次数均为7次。
解析
考查要点：本题主要考查三种页面置换算法（LRU、FIFO、OPT）的实现逻辑及缺页次数的计算。
解题核心思路：
- LRU算法：替换最近最久未使用的页，需记录各页的访问时间顺序。
- FIFO算法：替换最早进入内存的页，需记录页的进入顺序。
- OPT算法：替换未来最久不会被使用的页，需预知后续访问序列。
破题关键点：
- 模拟每一步的内存状态变化，严格按算法规则判断是否缺页。
- 注意内存容量限制（3个物理块），当内存满时执行置换操作。
LRU算法
- 初始状态：内存为空，缺页次数为0。
- 访问序列处理：
- 4,3,2,1：连续缺页，内存填满为
[4,3,2]，缺页次数达3次。 - 1：内存已满，替换最久未使用的
4，内存变为[3,2,1]，缺页次数4。 - 4：缺页，替换最久未使用的
3，内存变为[4,2,1]，缺页次数5。 - 5：缺页，替换最久未使用的
2，内存变为[4,5,1]，缺页次数6。 - 1：缺页，替换最久未使用的
5，内存变为[1,4,5]，缺页次数7。
- 4,3,2,1：连续缺页，内存填满为
- 最终缺页次数：7次。
FIFO算法
- 初始状态：内存为空，缺页次数为0。
- 访问序列处理：
- 4,3,2,1：连续缺页，内存填满为
[4,3,2]，缺页次数达3次。 - 1：内存已满，替换最早进入的
4，内存变为[3,2,1]，缺页次数4。 - 4：缺页，替换最早进入的
3，内存变为[4,2,1]，缺页次数5。 - 5：缺页，替换最早进入的
2，内存变为[4,5,1]，缺页次数6。 - 1：缺页，替换最早进入的
5，内存变为[1,4,5]，缺页次数7。
- 4,3,2,1：连续缺页，内存填满为
- 最终缺页次数：7次。
OPT算法
- 初始状态：内存为空，缺页次数为0。
- 访问序列处理：
- 4,3,2,1：连续缺页，内存填满为
[4,3,2]，缺页次数达3次。 - 1：内存已满，替换未来最久使用的
4（后续第8次访问），内存变为[3,2,1]，缺页次数4。 - 5：缺页，替换未来最久使用的
2（后续第10次访问），内存变为[3,5,1]，缺页次数5。 - 1：缺页，替换未来最久使用的
5（后续第12次访问），内存变为[1,3,2]，缺页次数6。 - 5：缺页，替换未来最久使用的
2（后续无访问），内存变为[1,5,2]，缺页次数7。
- 4,3,2,1：连续缺页，内存填满为
- 最终缺页次数：7次。