请求分页算法分析：页面访问时间、地址映射及缺页率控制

请求分页算法分析：页面访问时间、地址映射及缺页率控制

本文将通过一个具体的例子，分析请求分页算法中的页面访问时间、地址映射以及缺页率控制方法。

假设

• 进程的页表如下：

| 页号 | 物理帧号 | 有效位 | |---|---|---| | 0 | - | 0 | | 1 | 9H | 1 | | 2 | 254H | 1 |

• 页面大小为 4K
• 分配的物理帧数固定为 2
• 页面置换算法为 LRU
• 帧分配策略为本地帧分配
• 内存访问时间为 100ns
• TLB 访问时间为 10ns
• 缺页处理时间为 8ms
• TLB 初始化为空
• 有效位为 0 表示页面不在内存中，产生缺页处理
• 虚拟地址访问序列为 20A2H、1512H、104H

计算

1. 依次访问该序列地址对应的各个物理内存所需要的时间：

• 访问地址 20A2H

  • 访问 TLB，未命中，访问页表，产生缺页，将页 0 从磁盘读入物理帧 0 中，更新页表和 TLB，耗时 8ms；
  • 访问页表，命中，将页 1 从物理帧 9H 中读入 TLB 和物理帧表中，耗时 100ns；
  • 访问 TLB，命中，将虚拟地址 20A2H 映射到物理地址 9A2H，耗时 10ns；
  • 总耗时：8ms + 100ns + 10ns = 8.11ms

• 访问地址 1512H

  • 访问 TLB，未命中，访问页表，命中，将页 1 从物理帧 9H 中读入 TLB 和物理帧表中，耗时 100ns；
  • 访问 TLB，命中，将虚拟地址 1512H 映射到物理地址 9512H，耗时 10ns；
  • 总耗时：100ns + 10ns = 110ns

• 访问地址 104H

  • 访问 TLB，未命中，访问页表，产生缺页，将页 2 从磁盘读入物理帧 1 中，更新页表和 TLB，耗时 8ms；
  • 访问页表，命中，将页 2 从物理帧 1 中读入 TLB 和物理帧表中，耗时 100ns；
  • 访问 TLB，命中，将虚拟地址 104H 映射到物理地址 104H，耗时 10ns；
  • 总耗时：8ms + 100ns + 10ns = 8.11ms

2. 基于上述访问序列，虚拟地址 405H 对应的物理地址：

• 访问 TLB，未命中，访问页表，命中，将页 0 从物理帧 0 中读入 TLB 和物理帧表中，耗时 100ns；
• 访问 TLB，命中，将虚拟地址 405H 映射到物理地址 405H，耗时 10ns；

因此，虚拟地址 405H 对应的物理地址为 405H。

3. 若希望请求分页时内存的有效访问时间（EAT）为 120ns，缺页的概率应该控制在多少之内。

• EAT = TLB 访问时间 + 缺页处理时间 * 缺页概率 + 页表访问时间 * (1 - 缺页概率) + 物理内存访问时间
• 物理内存访问时间为 0，因为题目中固定了物理帧数为 2

将 EAT 代入公式，得到：

• 120ns = 10ns + p * 8ms + (1-p) * 100ns

解得：p <= 0.145，即缺页的概率应该控制在 14.5% 以内。

总结

本文通过分析一个具体的请求分页算法例子，展示了页面访问时间、地址映射以及缺页率控制方法。我们可以看到，缺页处理时间是影响内存访问时间的主要因素，因此需要通过优化页面置换算法、合理的帧分配策略以及 TLB 命中率等手段来降低缺页概率，从而提高内存访问效率。