某虚拟页式存储管理系统中有一个程序占8个页面，运行时访问页面的顺序是1,2,3,4,5,3,4,1,6,7,8,7,8,5。假设刚开始内存没有预装入任何页面。
某虚拟页式存储管理系统中有一个程序占8个页面，运行时访问页面的顺序是1,2,3,4,5,3,4,1,6,7,8,7,8,5。假设刚开始内存没有预装入任何页面。
- (1) 如果采用LRU调度算法，该程序在得到4块内存空间时，会产生多少次缺页中断？请给出详细计算步骤。
- (2) 如果采用OPT调度算法，该程序在得到4块内存空间时，会产生多少次缺页中断？请给出详细计算步骤。
- (3) 列出两种影响缺页率的因素
虚拟页式存储管理问题解析
(1) LRU (Least Recently Used) 最近最少使用算法。 算法缺页中断计算（4内存块）
核心原理
淘汰 最长时间未被访问 的页面
实现特点
- 时间局部性：基于程序访问的时空局部性原理
- 动态维护：每次访问更新页面时间戳
- 常见实现：
- 计数器法：为每个页维护访问时间戳
- 栈结构法：维护页面访问顺序栈
详细步骤分析
| 访问序列 | 内存状态（LRU顺序） | 缺页 | 缺页计数 |
|---|---|---|---|
| 1 | [1] | ✔️ | 1 |
| 2 | [2,1] | ✔️ | 2 |
| 3 | [3,2,1] | ✔️ | 3 |
| 4 | [4,3,2,1] | ✔️ | 4 |
| 5 | [5,4,3,2] | ✔️ | 5 |
| 3 | [3,5,4,2] | ✖️ | 5 |
| 4 | [4,3,5,2] | ✖️ | 5 |
| 1 | [1,4,3,5] | ✔️ | 6 |
| 6 | [6,1,4,3] | ✔️ | 7 |
| 7 | [7,6,1,4] | ✔️ | 8 |
| 8 | [8,7,6,1] | ✔️ | 9 |
| 7 | [7,8,6,1] | ✖️ | 9 |
| 8 | [8,7,6,1] | ✖️ | 9 |
| 5 | [5,8,7,6] | ✔️ | 10 |
结论：共发生 10次缺页中断
(2) OPT (Optimal Page Replacement) 最佳置换算法。算法缺页中断计算（4内存块）
核心原理
淘汰 未来最长时间不会被访问 的页面
算法特性
- 理论最优：产生最少缺页次数（作为性能评估基准）
- 不可实现：需要预知未来页面访问序列
- 应用场景：仅用于算法性能理论研究
关键置换决策分析
| 访问序列 | 内存状态 | 置换选择依据 | 缺页计数 |
|---|---|---|---|
| 1 | [1] | 初始载入 | 1 |
| 2 | [1,2] | 初始载入 | 2 |
| 3 | [1,2,3] | 初始载入 | 3 |
| 4 | [1,2,3,4] | 初始载入 | 4 |
| 5 | [1,3,4,5] | 置换未来不再访问的2号页 | 5 |
| 3 | [1,3,4,5] | 命中 | 5 |
| 4 | [1,3,4,5] | 命中 | 5 |
| 1 | [1,3,4,5] | 命中 | 5 |
| 6 | [3,4,5,6] | 置换未来不再访问的1号页 | 6 |
| 7 | [4,5,6,7] | 置换未来不再访问的3号页 | 7 |
| 8 | [5,6,7,8] | 置换未来不再访问的4号页 | 8 |
| 7 | [5,6,7,8] | 命中 | 8 |
| 8 | [5,6,7,8] | 命中 | 8 |
| 5 | [5,6,7,8] | 命中 | 8 |
结论：共发生 8次缺页中断
(3) 影响缺页率的两大因素
影响缺页率的因素有:分配给程序的物理页面数;页面的大小;程序编制的方法;页面调度算法。