3.2.11 虚拟内存管理【2009 统考真题】

好的，我们来详细解析这道2009年的虚拟内存管理统考真题。这道题是该领域的集大成者，将 TLB、页表、缺页中断、页面置换算法等核心知识点串联在一起，通过一个完整的访问序列来考察，是理解虚拟内存工作流程的绝佳范例。

第一步：重述题目原文

【2009 统考真题】在请求分页管理系统中，假设某进程的页表内容如下表所示：

系统参数：

页面大小为 4KB。一次内存的访问时间是 100ns。一次快表 (TLB) 的访问时间是 10ns。处理一次缺页的平均时间为 10⁸ns (已含更新 TLB 和页表的时间)。进程的驻留集大小固定为 2。采用最近最少使用 (LRU) 置换算法和局部淘汰策略。

假设：

TLB 初始为空。地址转换时先访问 TLB，若 TLB 未命中，再访问页表 (忽略访问页表后的 TLB 更新时间)。有效位为 0 表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。

问题：
设有虚地址访问序列
2362H,
1565H,
25A5H。

依次访问上述三个虚拟地址，各需多少时间？给出计算过程。基于上述访问序列，虚地址
1565H 的物理地址是多少？请说明理由。

第二步：知识体系是什么？

这道题考察的是现代操作系统核心的 虚拟内存管理机制，它是一个为了在有限的物理内存上运行大型程序而设计的多层体系。

分页与地址转换：这是基础。CPU发出的虚拟地址被分为 页号 和 页内偏移。系统通过 页表 将虚拟页号翻译成物理 页框号，然后与页内偏移拼接成最终的物理地址。

TLB (快表)：页表本身存放在内存中，这意味着每次内存访问都需要两次访存（一次查页表，一次取数据），效率太低。TLB 是设在 CPU 内部的一个高速缓存，专门用于缓存最近用过的页表项。

TLB命中：直接从 TLB 获得页框号，速度极快。TLB未命中：需要老老实实去内存中查页表，并将查到的页表项放入 TLB，以备后续使用。

缺页中断 (Page Fault)：当查询页表发现 有效位为0 时，说明该页面不在物理内存中。CPU会产生一个“缺页中断”异常，将控制权交给操作系统。

页面置换：操作系统响应缺页中断后，需要从磁盘中把缺失的页面调入内存。如果内存已满（如此题中驻留集大小固定为2），就需要选择一个已在内存中的页面将其换出。

LRU (最近最少使用) 算法：是一种经典的页面置换算法。其核心思想是：当需要淘汰一个页面时，选择那个在过去最长时间内未被访问过的页面。

第三步：解题套路是什么？

解决这类问题，关键在于状态追踪。你需要像一个CPU一样，一步一步、严格按照规则来模拟整个地址转换和状态更新的过程。

套路一：预处理

解析地址结构：根据页大小确定页内偏移的位数。
页大小 =
4KB = 2¹² B。所以，页内偏移占 12位。12位二进制等于3位十六进制。因此，对于一个十六进制虚拟地址，后3位是偏移，前面的是页号。
分解地址序列：将所有给定的虚拟地址预先分解好。

2362H -> 页号
2, 偏移
362H
1565H -> 页号
1, 偏移
565H
25A5H -> 页号
2, 偏移
5A5H
建立状态表：在草稿纸上画出需要追踪的状态。
TLB 内容：(页号 -> 页框号)驻留集 (内存中的页)：{页号, …}LRU 访问次序：用一个队列或栈来记录，队头/栈顶是最近访问的。

套路二：按序列逐步模拟

对序列中的每一个地址，严格执行以下流程，并计算时间：

查 TLB：时间 +
10ns。

命中？ -> 成功。总时间 =
10ns (TLB) + 100ns (访存)。转到步骤4。未命中？ -> 失败。继续。

查页表 (需要访问内存)：时间 +
100ns。

有效位为1？(在内存) -> 成功。总时间 =
10ns (TLB miss) + 100ns (查页表) + 100ns (访存)。将该页表项装入TLB。转到步骤4。有效位为0？(缺页) -> 失败。继续。

处理缺页中断：

时间 +
10⁸ns。执行页面置换：根据LRU算法，在驻留集中找到要被淘汰的页，用新页替换它。更新页表。重新执行指令：回到步骤1，对当前地址重新发起访问。

更新状态：

更新LRU次序：将当前访问的页置为“最近使用的”。

第四步：为什么是这样？（深度剖析）

为什么要重新执行指令？ 缺页中断对用户进程是透明的。当操作系统处理完中断后，必须让被中断的指令重新执行，就好像什么都没发生过一样。所以一次缺页的总时间，包含了首次访问失败、中断处理和第二次访问成功的全过程。LRU的精髓：LRU体现了程序的局部性原理。它假设最近被访问的页面，在将来也很有可能被再次访问，所以应该保留在内存中。而很久没被访问的页面，则可以被优先淘汰。

第五步：考试怎么解决？（实战指南）

问1：依次访问的时间计算

初始状态:

TLB:
{} (空)驻留集:
{页0, 页2}LRU次序: (假设页2比页0更新，记为
(MRU -> LRU):
(2, 0))

1. 访问
2362H (页号 2, 偏移 362H)

查TLB: 未命中 (TLB为空)。 耗时: 10ns查页表: 页号2的有效位为1，页框号为
254H。 耗时: 100ns访问内存: 根据页框号
254H和偏移
362H访问数据。 耗时: 100ns总时间:
10ns + 100ns + 100ns = 210ns状态更新:
TLB:
{(2 -> 254H)}LRU次序: 页2被访问，成为最近使用的。
(2, 0)

2. 访问
1565H (页号 1, 偏移 565H)

查TLB: 未命中 (TLB中只有页2)。 耗时: 10ns查页表: 页号1的有效位为0。 缺页中断！ 耗时: 100ns处理缺页中断:
执行LRU置换: 当前驻留集为
{0, 2}，LRU次序为
(2, 0)。页0是最近最少使用的，淘汰页0。调入页面: 将页1调入原属于页0的页框
101H。更新页表: 页1的页表项变为(页框
101H, 有效位1)，页0的页表项变为(有效位0)。中断处理总耗时: 10⁸ns
重新执行指令 (访问
1565H):
查TLB: 未命中 (因为是重新执行，TLB中依然没有页1)。 耗时: 10ns查页表: 此时页1的有效位为1，页框号为
101H。 耗时: 100ns访问内存: 耗时: 100ns
总时间:
10(TLB miss) + 100(查页表) + 10⁸(缺页) + 10(重试TLB miss) + 100(重试查页表) + 100(访存) = 100,000,220 ns。状态更新:
TLB:
{(2 -> 254H), (1 -> 101H)}驻留集:
{1, 2}LRU次序: 页1被访问，成为最近使用的。
(1, 2)

3. 访问
25A5H (页号 2, 偏移 5A5H)

查TLB: 命中！ (TLB中有
(2 -> 254H)的映射)。 耗时: 10ns访问内存: 耗时: 100ns总时间:
10ns + 100ns = 110ns状态更新:
LRU次序: 页2被访问，成为最近使用的。
(2, 1)

问2：虚地址
1565H 的物理地址

理由:
在处理对虚地址
1565H (页号1) 的访问时，发生了缺页中断。根据LRU算法，系统需要从驻留集
{0, 2} 中淘汰最近最少使用的页面。在此之前，访问序列是
2362H (访问了页2)，所以页2是最近使用的，页0是最近最少使用的。因此，页0被淘汰。页0原先占用的物理页框是
101H。缺失的 页1 被调入到刚刚被释放的页框
101H 中。
计算:
物理地址由 页框号 和 页内偏移 拼接而成。页1对应的页框号为
101H。虚地址
1565H 的页内偏移为
565H。拼接得到物理地址为
101565H。