跳转至

408 高频考点精讲:地址翻译

模块归属:操作系统 · 内存管理
考点层级:微观细分考点(近十年考查 >= 3 次)
适用对象:408 计算机考研备考学生


一、 考情档案

  • 近十年考查频次:7 次(2016 年第 28 题、2017 年第 45 题、2018 年第 45 题、2019 年第 31 题、2019 年第 46 题、2020 年第 46 题、2021 年第 44 题)
  • 历年总考查频次:12 次(统考自 2009 年设立以来,多次以综合解答题压轴形式出现)
  • 出题形式:单项选择题、综合解答题(近五年高频作为“计算机组成原理 + 操作系统”跨学科大题的核心考查骨架)
  • 命题特点:
  • 位划分与进制转换要求严密:重点考查 32 位系统下的二级分页机制(标准 \(10-10-12\) 划分结构),要求考生在十六进制与二进制之间精准展开切分,提取页目录号、二级页号、页内偏移量。
  • 软硬件协同机制穿透考查:深入考查 MMU 硬件翻译流水线、控制寄存器 PDBR(页目录基址寄存器,存放物理地址)、TLB 快表缓存、主存物理页表之间的联动;重点考查进程切换(刷新 PDBR 与清空 TLB)与线程切换(同一地址空间,PDBR 与 TLB 不变)的底层机制差异。
  • 数据结构实体与物理地址精算:要求熟练推导页目录项(PDE)、二级页表项(PTE)的物理地址生成公式,理解基地址相加与项大小缩放关系。
  • 跨模块系统级联合考查:
    • 结合虚拟存储器的页面置换算法(如改进型 Clock 置换算法所需的访问位与修改位);
    • 结合体系结构 Cache 组相联映射(利用页内偏移低位与物理地址低位严格重合的特性,直接求解 Cache 组号);
    • 结合 TLB 组相联映射机制及 LRU 替换策略;
    • 结合程序局部性分析(二维数组按行遍历与按列遍历对缺页率、TLB/Cache 命中率的深层影响)。

近十年考查年份分布表格(2016~2025)

+------+------------+----------+------------------------------------------------------+
| 年份 | 题号       | 题型     | 核心考查主题                                         |
+------+------------+----------+------------------------------------------------------+
| 2016 | 第 28 题   | 单项选择 | 段式存储管理地址变换机制、段限长越界判断与异常类型   |
| 2017 | 第 45 题   | 综合解答 | 二级分页地址结构、指令跨页判断、页目录与页表表项索引 |
| 2018 | 第 45 题   | 综合解答 | 二级页表地址合成计算、PDBR 物理属性与进程/线程切换、Clock 位设计 |
| 2019 | 第 31 题   | 单项选择 | 二级分页十六进制地址二进制切分、页目录号与页号提取   |
| 2019 | 第 46 题   | 综合解答 | 虚页号跨页判定、虚实地址低位重合性与 Cache 组号映射  |
| 2020 | 第 46 题   | 综合解答 | 数组元素虚拟地址切分、PDE 与 PTE 物理地址精算、空间局部性分析 |
| 2021 | 第 44 题   | 综合解答 | 虚拟地址划分、TLB 组相联映射划分、LRU 替换序列与标记位扩展 |
| 2022 | -          | -        | 未直接考查(涉及虚存全局概念)                       |
| 2023 | -          | -        | 未直接考查(考查文件系统与进程调度)                 |
| 2024 | -          | -        | 未直接考查(考查页面置换算法与磁盘调度)             |
| 2025 | -          | -        | 未直接考查                                           |
+------+------------+----------+------------------------------------------------------+

二、 具体考察内容

1. 核心概念与机制原理

(1) 基本概念与内存管理单元(MMU)

  • 虚拟地址(Virtual Address, VA / Logical Address, LA):用户进程所面对的连续编址空间。在 32 位体系结构中,虚拟地址空间通常为 \(2^{32}\,\text{B} = 4\,\text{GB}\)。
  • 物理地址(Physical Address, PA):物理内存(DRAM)的真实物理引脚编址。
  • 内存管理单元(Memory Management Unit, MMU):CPU 内部专用于将虚拟地址实时翻译为物理地址的硬件部件。它负责 TLB 查找、页表遍历(Page Walk)、越界检查与访问权限校验。
  • 页内偏移量与物理页内偏移量的恒等性:设页面大小为 \(S = 2^p\)$ \text{字节,虚拟地址低} $\(p\)$ \text{位为页内偏移量(Virtual Page Offset, VPO),物理地址低} $\(p\) 位为物理页内偏移量(Physical Page Offset, PPO)。在分页机制中,页面边界与物理页框(Page Frame)严格对齐,故: $\(VPO = PPO = VA[p-1:0] = PA[p-1:0]\)$ 该数学性质是现代计算机实现虚索引实标记(VIPT)Cache 架构的物理基石。

(2) 一级分页与多级分页机制

  • 一级分页机制:虚拟地址划分为虚页号(Virtual Page Number, VPN)与页内偏移量(VPO)。
  • 页表基址寄存器(Page Table Base Register, PTBR)保存进程页表的物理基地址。
  • MMU 通过索引查找物理内存中的页表项(Page Table Entry, PTE),获得物理页框号(Physical Frame Number, PFN),与页内偏移量拼接构成物理地址。
  • 瓶颈:当虚拟地址空间庞大时,一级页表必须连续存放在主存中,占用大量连续物理内存,且其中绝大部分表项指向未分配的虚存空间。
  • 二级分页机制:采用两级树状索引结构,将虚拟地址划分为:页目录号(\(P_1\)$ \text{)、二级页号(} $\(P_2\)$ \text{)和页内偏移量(} $\(D\))。
  • PDBR(Page Directory Base Register,如 x86 的 CR3 寄存器):保存当前运行进程的页目录表(Page Directory)的物理基地址。
  • 按需分配:页目录表必须常驻内存,而二级页表在对应虚存空间未被映射或访问时无需创建;被置换出主存的二级页表可在缺页时按需调入,从而大幅压缩系统常驻开销。
虚拟地址 (VA) 结构 (以 32 位系统、4KB 页面为例):
 31                22 21                12 11                 0
+--------------------+--------------------+--------------------+
|  页目录号 P1 (10位) |   二级页号 P2 (10位)|  页内偏移量 D (12位) |
+--------------------+--------------------+--------------------+
          |                    |                    |
          |                    |                    |
PDBR ---->+                    |                    |
 (物理基址) | (索引)             |                    |
          v                    v                    |
    [ 页目录项 PDE ] --------> [ 二级页表项 PTE ]      |
    (指向二级页表物理基址)       (指向物理页框号 PFN)    |
                                      |             |
                                      v             v
                              物理地址: [ PFN (20位) | D (12位) ]

(3) 段式存储管理机制

  • 虚拟地址由段号(Segment Number, \(S\)$ \text{)与段内偏移量(Segment Offset,} $\(W\))组成。
  • 段表为每个逻辑段维护一个段表项,包含:
  • 段长(Limit):该段的最大有效逻辑长度。
  • 物理始址(Base Address):该段在物理内存中的起始字节地址。
  • 访问权限与状态控制位:只读/读写/执行权限、在存位(Present Bit)。
  • 硬件翻译与越界检查流程:
  • MMU 提取段号 \(S\)$ \text{,与段表长度寄存器中的段表长度比较,若} $\(S \ge \text{段表长度}\),触发越界异常。
  • MMU 提取段内偏移量 \(W\)$ \text{,与该段表项中的段长} $\(\text{Limit}\)$ \text{严格对比:若} $\(W \ge \text{Limit}\),硬件必须立即触发越界异常(Trap/Fault)。
  • 若 \(W < \text{Limit}\),则检查在存状态位;若不在内存中,触发缺段异常;若在内存中,计算物理地址: $\(PA = \text{Base} + W\)$

(4) 虚拟存储器扩展字段与页面置换

请求分页系统中,页表项除存放物理页框号(PFN)外,还包含关键的控制位: 1. 有效位/在存位(Valid / Present Bit):指示该页面是否已装入主存。若为 0,MMU 访问时触发缺页异常(Page Fault),CPU 转入内核态缺页中断服务程序。 2. 访问位/引用位(Access / Reference / Use Bit):用于记录该页是否被读写访问。页面置换算法(如 Clock 算法)定期扫描该位以判断近期活跃度。 3. 修改位/脏位(Dirty / Modified Bit):指示该页在主存中是否被写过。若为 1,淘汰换出时必须写回外存对齐副本;若为 0,直接丢弃该物理页框内容,避免多余磁盘 I/O。 4. 保护位(Protection Bits):记录读/写/执行权限(Read / Write / Execute)。若非法越权写入只读代码段,触发保护违例异常(Segmentation Fault)。


2. 核心定理推导与计算模型

(1) 页面大小与各级索引位宽模型

设按字节编址,系统虚拟地址位宽为 \(V\)$ \text{位,物理地址位宽为} $\(P\)$ \text{位,系统页面大小为} $\(S = 2^p\) 字节: - 页内偏移量位宽 \(p = \log_2 S\)。 - 虚页号(VPN)总位宽为 \(V - p\)。 - 物理页框号(PFN)总位宽为 \(P - p\)。

若系统采用 \(N\)$ \text{级分页机制,虚页号划分为} $\((k_1, k_2, \dots, k_N)\),满足: $\(\sum_{i=1}^N k_i = V - p\)$ 工程设计定理(页表对齐准则):为了避免页表跨页断裂,各级页表自身的大小通常严格限制为一个物理页大小 \(S\)$ \text{。设每个页表项大小为} $\(e = 2^m\) 字节,则单页最多容纳的表项数为: $\(N_{\text{entry}} = \frac{S}{e} = \frac{2^p}{2^m} = 2^{p-m}\)$ 因此,各级索引位宽 \(k_i\) 的设计上限为: $\(k_i \le p - m\)$ 经典 32 位 x86 体系(4KB 页面,4B 表项)推导: - \(p = \log_2(4096) = 12\) - \(e = 4\,\text{B} \implies m = 2\) - \(k_i = 12 - 2 = 10\) 位。 - 故虚页号拆分为两级:\(10 + 10 = 20\)$ \text{位,形成标准} $\(10-10-12\) 地址划分结构。

(2) 页目录项与二级页表项物理地址精算模型

设当前运行进程的 PDBR 值为页目录表起始物理地址 \(Base_{\text{DIR}}\)$ \text{,二级页表项大小与页目录项大小均为} $\(e\)$ \text{字节。给定虚拟地址} $\(VA\),提取字段: $\(P_1 = \text{Ext}(VA, 31, 22), \quad P_2 = \text{Ext}(VA, 21, 12), \quad D = \text{Ext}(VA, 11, 0)\)$

  1. 页目录项(PDE)物理地址计算: $\(PA_{\text{PDE}} = Base_{\text{DIR}} + P_1 \times e\)$
  2. 二级页表物理基地址提取: 从物理地址 \(PA_{\text{PDE}}\)$ \text{处读取 32 位 PDE 内容,提取其高 20 位页框号字段} $\(PFN_{\text{PT}}\)(低 12 位为控制标志位),则二级页表的物理基地址为: $\(Base_{\text{PT}} = PFN_{\text{PT}} \times 2^p = PFN_{\text{PT}} \ll 12\)$
  3. 二级页表项(PTE)物理地址计算: $\(PA_{\text{PTE}} = Base_{\text{PT}} + P_2 \times e\)$
  4. 最终目标物理地址计算: 从物理地址 \(PA_{\text{PTE}}\)$ \text{处读取 32 位 PTE 内容,提取目标物理页框号} $\(PFN_{\text{Target}}\)$ \text{,与页内偏移量} $\(D\) 拼接: $\(PA_{\text{Target}} = (PFN_{\text{Target}} \ll 12) + D\)$

(3) 虚实地址低位重叠与 Cache 组索引映射定理

设物理地址位宽为 \(P\)$ \text{,主存 Cache 容量为} $\(C\)$ \text{字节,Cache 块大小为} $\(B = 2^b\)$ \text{字节,采用} $\(K\)$ \text{路组相联映射方式(组数} $\(N_{\text{set}} = \frac{C}{K \cdot B} = 2^s\)): - 物理地址被划分为三个字段: $$ \text{物理标记 (Tag)} : (P - s - b) \text{ 位} \quad|\quad \text{组索引 (Set Index)} : s \text{ 位} \quad|\quad \text{块内偏移 (Block Offset)} : b \text{ 位} $$ - 虚拟地址低 \(p\)$ \text{位(页内偏移)与物理地址低} $\(p\) 位(页框内偏移)满足: $\(PA[p-1:0] \equiv VA[p-1:0]\)$ - 定理:当系统满足条件 \(s + b \le p\)$ \text{时,物理地址的组索引与块内偏移完全被包含在物理地址的低} $\(p\) 位中。此时有: $$ \text{Cache 组索引} = PA[s+b-1 : b] = VA[s+b-1 : b] $$ 推论:CPU 在发起取指或访存时,无需等待 MMU 完成虚拟页号向物理页框号的漫长地址翻译,即可直接利用虚拟地址的第 \(b\)$ \text{到第} $\(s+b-1\) 位索引 Cache 组,实现与 MMU 翻译并行的 Cache 组寻址(VIPT 架构)。

(4) TLB 组相联映射划分模型

TLB 作为页表的高速硬件缓存,直接缓存 \((VPN \to PFN)\) 的映射对。 - 在组相联 TLB 中,虚页号(VPN)被细分为两部分: $$ \text{VPN} = [\,\text{TLB Tag} \,|\, \text{TLB 组号 (TLB Set Index)}\,] $$ - 设 TLB 共有 \(M = 2^m\)$ \text{组,则虚页号的低} $\(m\) 位直接充当 TLB 组索引,剩余的高位为 TLB Tag。 - 虚页号 \(VPN\) 映射到的 TLB 组号为: $$ \text{TLB 组号} = VPN \bmod M = VPN[m-1:0] $$ - 若虚拟地址位宽扩展 \(\Delta k\)$ \text{位,而页面大小不变,则虚页号位宽增加} $\(\Delta k\)$ \text{位。在 TLB 组数不变的情况下,增加的} $\(\Delta k\)$ \text{位全部归入 TLB Tag 字段,导致每个 TLB 表项的位宽精确增加} $\(\Delta k\) 位。


3. 核心机制对比辨析

(1) 基本内存分配管理方式全维度对比

对比维度 分页存储管理 分段存储管理 段页式存储管理
基本单位性质 物理实体(由硬件统一划分,大小固定) 逻辑单位(由用户程序结构决定,长度动态可变) 逻辑分段,段内物理分页
地址维度 一维(给出虚拟地址,硬件自动切分) 二维(逻辑上显式给出段名与段内偏移) 二维(显式给出段号与段内偏移,段内自动切分)
内存碎片 无外部碎片,存在内部碎片(平均每进程半页) 无内部碎片,存在大量外部碎片(需内存紧凑) 无外部碎片,仅在最后一个页内产生内部碎片
越界判断时机 仅检查虚页号是否超过页表长度 严格执行双重检查:检查段号,且检查段内偏移 \(W \ge \text{Limit}\) 检查段号、段内页号、页内偏移
共享与保护 以固定大小页面为单位,代码共享较繁琐 以独立逻辑段(代码段、数据段)为单位,共享与保护天然友好 以段为单位共享与保护,实现灵活
访存开销(无TLB) 查页表 1 次 + 访主存 1 次 = 2 次访存 查段表 1 次 + 访主存 1 次 = 2 次访存 查段表 1 次 + 查页表 1 次 + 访主存 1 次 = 3 次访存

(2) TLB、Page Table 与 Cache 硬件协同层级对比

对比维度 TLB(转换旁置旁路缓冲区) Page Table(页表) Cache(主存高速缓冲存储器)
物理本质 CPU 内部的高速 SRAM 联想存储器 物理内存(DRAM)中的操作系统数据结构 CPU 内部或芯片上的高速 SRAM
缓存内容 虚页号到物理页框号的映射(\(VPN \to PFN\)) 虚页号到物理页框号的全部映射关系实体 物理主存或虚拟主存中的真实指令/数据块
索引输入 虚页号(VPN) 虚页号(VPN)或多级索引(\(P_1, P_2\)) 物理地址(PIPT)或虚拟地址(VIVT/VIPT)
硬件/软件属性 纯硬件控制查找,缺失可由硬件或软件处理 操作系统软件维护结构,MMU 硬件读取遍历 纯硬件透明管理(映射、替换、写回)
进程切换影响 必须失效清空(除非支持 ASID/PCID 标签) 切换基地址寄存器 PDBR 指向新进程页目录 物理 Cache 无需清空,虚拟 Cache 需刷新

(3) 进程切换与线程切换在地址翻译层面的本质区别

对比维度 进程切换(Process Switch) 线程切换(Thread Switch,同一进程内)
地址空间所有权 从一个独立的虚拟地址空间切换到另一个空间 在同一个共享的虚拟地址空间内部切换执行流
PDBR (CR3) 寄存器 必须改变。重新装入新进程页目录的物理基地址 保持不变。所有线程共享同一套页目录与页表
TLB 快表有效性 发生上下文切换,旧进程的映射失效,TLB 必须刷新/清空 虚实映射关系未变,TLB 缓存条目全部保持有效
性能切换代价 极高(涉及页表基址切换与冷启动 TLB Miss 风暴) 极低(仅保存与恢复少量私有寄存器和栈指针)

三、 近十年真题精讲(2016~2025)

【真题 1】2016 年 408 第 28 题 · 段式内存管理地址转换与越界异常判定

题目:
某进程的段表内容如下所示:

段号 段长 内存起始地址 权限 状态
0 100 6000 只读 在内存
1 200 · · · 读写 不在内存
2 300 4000 读写 在内存

当访问段号为 2、段内地址为 400 的逻辑地址时,进行地址转换的结果是( )。
A. 段缺失异常
B. 得到内存地址 4400
C. 越权异常
D. 越界异常

【解析】

  1. 知识定位:段式存储管理的硬件地址变换机制与异常检测判定逻辑。
  2. 核心判断流程:
  3. 给定逻辑地址包含:段号 \(S = 2\)$ \text{,段内地址(偏移量)} $\(W = 400\)。
  4. 检索段表中段号为 2 的表项,读取其对应属性:段长 \(\text{Limit} = 300\)$ \text{,内存物理起始地址} $\(\text{Base} = 4000\),状态为“在内存”。
  5. 硬件越界检查规则:段式管理要求逻辑偏移量严格小于段长,即必须满足 \(W < \text{Limit}\)$ \text{。若} $\(W \ge \text{Limit}\),硬件 MMU 判定该偏移量超出该段合法分配空间,直接触发越界异常(Protection Fault / Bounds Check Fault)。
  6. 在本题中,段内地址 \(W = 400\)$ \text{,段长} $\(\text{Limit} = 300\)$ \text{。由于} $\(400 \ge 300\),硬件立即判定地址越界,产生越界异常。
  7. 干扰项辨析:
  8. 选项 A 错误:只有在段内地址未越界(\(W < \text{Limit}\))且段表项的“状态”字段指示“不在内存”时,才会触发段缺失异常(类似缺页异常)。段号 2 状态为“在内存”,且越界检查在状态检查之前发生。
  9. 选项 B 错误:物理地址的相加计算(\(4000 + 400 = 4400\))只有在越界检查合法通过后才会执行。硬件绝不允许越界计算生效。
  10. 选项 C 错误:越权异常发生在非法权限访问(例如对只读段执行写指令)时,本题段号 2 权限为读写,且越界检查先于权限检查报错。

正确答案:D


【真题 2】2017 年 408 第 45 题 · 二级分页地址划分、指令代码跨页判断与表项索引

题目背景:
(本题依托 2017 年第 43 题与第 44 题上下文)已知在按字节编址的 32 位计算机 M 上,函数 f1 的机器级代码如下(部分展示):

1   0040 1020   55                  push  ebp
... ...         ...                 ...
20  0040 105E   39 4D F4            cmp   dword ptr [ebp-0Ch], ecx
... ...         ...                 ...
35  0040 107F   C3                  ret
计算机 M 采用二级分页虚拟存储管理方式,虚拟地址格式如下:
+--------------------+--------------------+--------------------+
|  页目录号 (10 位)  |  页表索引 (10 位)  | 页内偏移量 (12 位) |
+--------------------+--------------------+--------------------+
请回答下列问题: (1) 函数 f1 的机器指令代码占多少页?
(2) 取第 1 条指令(push ebp)时,若在进行地址变换的过程中需要访问内存中的页目录和页表,则会分别访问它们各自的第几个表项(编号从 0 开始)?
(3) M 的 I/O 采用中断控制方式。若进程 P 在调用 f1 之前通过 scanf() 获取 \(n\) 的值,则在执行 scanf() 的过程中,进程 P 的状态会如何变化?CPU 是否会进入内核态?

【解析】

  1. 第 (1) 问解析:
  2. 由虚拟地址格式可知,页内偏移量占 12 位,因此页面大小为 \(2^{12}\,\text{B} = 4096\,\text{B} = 4\,\text{KB}\)。
  3. 高 \(10 + 10 = 20\) 位构成虚页号(VPN),对应十六进制的前 5 个十六进制半字节(Hex Digits)。
  4. 查看代码段地址分布:第 1 条指令虚拟地址为 0040 1020H,最后一条指令(第 35 条 ret,机器码 C3 占 1 字节)地址范围为 0040 107FH。
  5. 提取起止指令的高 20 位虚页号:
    • 起始地址 0040 1020H 的高 20 位为 00401H;
    • 终止地址 0040 107FH 的高 20 位同样为 00401H。
  6. 由于函数 f1 的全部指令的虚页号完全一致,且该段代码总长度仅为 \(0040107\text{FH} - 00401020\text{H} + 1 = 60\text{H} + 1 = 96\) 字节,未发生跨页,因此函数 f1 的机器指令代码仅占用 1 页。

  7. 第 (2) 问解析:

  8. 第 1 条指令的虚拟地址为 0040 1020H。
  9. 将其精确展开为 32 位二进制比特序列: $$ \text{0040 1020H} = \underbrace{0000\,0000\,01}{\text{高 10 位:页目录号}} \underbrace{00\,0000\,0001} $$}} \underbrace{0000\,0010\,0000}_{\text{低 12 位:页内偏移}
  10. 提取对应索引:
    • 高 10 位(页目录号):\(0000000001_2 = 1\);
    • 中间 10 位(页表索引):\(0000000001_2 = 1\)。
  11. 表项编号从 0 开始计数,因此访问页目录的第 1 个表项,在二级页表中访问第 1 个表项。

  12. 第 (3) 问解析:

  13. 进程状态变化流:
    • 进程 P 在用户态调用 scanf(),底层触发系统调用(软中断),CPU 转入内核态;
    • 由于终端输入尚未就绪,进程 P 调用睡眠阻塞原语,从运行态(Running)变为阻塞态(Blocked / Waiting),并引发进程调度程序执行;
    • 当键盘输入完成产生硬件中断后,中断服务程序唤醒进程 P,进程 P 从阻塞态转为就绪态(Ready);
    • 调度程序再次选中进程 P 时,进程 P 从就绪态转为运行态。
  14. 特权级变化:
    • 系统调用引发陷阱(Trap),以及后续的 I/O 硬件中断处理,均会导致 CPU 进入内核态(管态)。

【标准答案】

(1) 占 1 页。
(2) 页目录的第 1 个表项;页表的第 1 个表项。
(3) 进程 P 状态变化为:运行态 \(\to\)$ \text{阻塞态} $\(\to\)$ \text{就绪态} $\(\to\) 运行态。CPU 会进入内核态。


【真题 3】2018 年 408 第 45 题 · 二级页表地址合成、PDBR物理属性与Clock位设计

题目背景:
(本题依托 2018 年第 44 题给出的 32 位二级分页虚拟存储管理图示)虚拟地址格式如下:高 10 位为页目录号,中间 10 位为页号,低 12 位为页内偏移量。请回答下列问题:
(1) 某虚拟地址对应的页目录号为 6,在相应的页表中对应的页号为 6,页内偏移量为 8,该虚拟地址的十六进制表示是什么?
(2) 寄存器 PDBR 用于保存当前进程的页目录起始地址,该地址是物理地址还是虚拟地址?进程切换时,PDBR 的内容是否会变化?说明理由。同一进程的线程切换时,PDBR 的内容是否会变化?说明理由。
(3) 为了支持改进型 CLOCK 置换算法,需要在页表项中设置哪些字段?

【解析】

  1. 第 (1) 问解析:
  2. 提取字段的十进制值并转换为二进制比特段:
    • 页目录号(高 10 位):\(6 = 00\,0000\,0110_2\)
    • 二级页号(中间 10 位):\(6 = 00\,0000\,0110_2\)
    • 页内偏移量(低 12 位):\(8 = 0000\,0000\,1000_2\)
  3. 沿高位到低位严格拼接 32 位二进制序列: $\(\underbrace{0000\,0001}_{\text{01H}} \ \underbrace{1000\,0000}_{\text{80H}} \ \underbrace{0110\,0000}_{\text{60H}} \ \underbrace{0000\,1000}_{\text{08H}}\)$
  4. 将二进制序列按 4 位一组转换为十六进制:01806008H(或 0x01806008)。

  5. 第 (2) 问解析:

  6. PDBR 的物理属性:PDBR(页目录基址寄存器,即 x86 的 CR3)用于 MMU 在地址翻译流程最前端定位根页目录。若 PDBR 存储的是虚拟地址,MMU 访问页目录前又需要对 PDBR 本身进行地址翻译,产生死锁循环递归。因此,PDBR 保存的必须是物理地址。
  7. 进程切换判定:会变化。每个进程拥有独立的虚拟地址空间与独立的页目录映射表。发生进程上下文切换时,必须将当前进程的页目录物理基址刷新到 PDBR 中,以激活新进程的地址映射空间。
  8. 线程切换判定:不会变化。同一进程中的所有线程共享该进程的全部虚拟地址空间、代码段、数据段和页表结构。因此,同一进程内部的线程发生切换时,页目录基地址不变,PDBR 内容无需改变。

  9. 第 (3) 问解析:

  10. 改进型 Clock 置换算法依据页面近期是否被访问以及是否被修改两个特征,结合元组 $$ \text{(\text{访问位 } A, \text{修改位 } M)} $$ 实施四轮扫描淘汰。
  11. 因此,为了支持该算法,页表项中必须显式设置:访问字段(访问位/使用位/引用位)与修改字段(修改位/脏位)。

【标准答案】

(1) 虚拟地址的十六进制表示为:01806008H。
(2) 该地址是物理地址。
进程切换时,PDBR 的内容会变化。理由:每个进程拥有独立的虚拟地址空间与独立的页目录表,进程切换时必须加载新进程页目录的物理起始地址以切换地址空间。
同一进程的线程切换时,PDBR 的内容不会变化。理由:同一进程的所有线程共享该进程的虚拟地址空间,其页目录物理起始地址相同。
(3) 需要在页表项中设置:访问位(使用位)和修改位(脏位)。


【真题 4】2019 年 408 第 31 题 · 二级分页十六进制地址二进制切分与索引提取

题目:
某计算机主存按字节编址,采用二级分页存储管理,地址结构如下所示:

+--------------------+--------------------+--------------------+
|  页目录号 (10 位)  |    页号 (10 位)    |  页内偏移 (12 位)  |
+--------------------+--------------------+--------------------+
虚拟地址 20501225H 对应的页目录号、页号分别是( )。
A. 081H、101H
B. 081H、401H
C. 201H、101H
D. 201H、401H

【解析】

  1. 知识定位:二级分页存储管理的虚拟地址切分模型。
  2. 二进制展开: 将十六进制虚拟地址 20501225H 严格按每个十六进制字符展开为 4 位二进制:
    2    0    5    0    1    2    2    5
    0010 0000 0101 0000 0001 0010 0010 0101
    
  3. 字段精确截取: 根据地址结构(高 10 位为页目录号,中间 10 位为页号,低 12 位为页内偏移量):
  4. 页目录号(高 10 位): 提取高 10 位:00 1000 0001 补齐高位前导零转为 12 位十六进制:0000 1000 0001B = 081H。
  5. 页号(中间 10 位): 提取接下来第 11 位到第 20 位: 原序列:0010 0000 01 [已取走] \(\to\) 紧接着是 01 0000 0001 补齐高位前导零转为 12 位十六进制:0001 0000 0001B = 101H。
  6. 页内偏移(低 12 位): 剩余低 12 位为:0010 0010 0101B = 225H。
  7. 结论匹配:页目录号为 081H,页号为 101H,选项 A 正确。

正确答案:A


【真题 5】2019 年 408 第 46 题 · 虚页号跨页判断、虚实地址低位重叠与Cache组映射

题目背景:
(本题依托 2019 年第 45 题上下文)已知计算机 M 的主存按字节编址,主存地址为 32 位,采用分页存储管理方式,页大小为 4KB。函数 f1 的机器级代码中: - 第 1 行指令(push ebp)的虚拟地址为 0040 1000H; - 第 16 行指令(call f1)的虚拟地址为 0040 1025H; - 第 30 行指令(ret)的虚拟地址为 0040 105AH。

请回答下列问题:
(1) 第 1 行的 push 指令和第 30 行的 ret 指令是否在同一页中?说明理由。
(2) 若指令 Cache 有 64 行,采用 4 路组相联映射方式,主存块大小为 64B,则 32 位主存地址中,哪几位表示块内地址?哪几位表示 Cache 组号?哪几位表示标记(Tag)信息?
(3) 读取第 16 行的 call 指令时,只可能在指令 Cache 的哪一组中命中?说明理由。

【解析】

  1. 第 (1) 问解析:
  2. 页面大小为 \(4\,\text{KB} = 2^{12}\,\text{B}\)$ \text{,因此虚拟地址的低 12 位表示页内偏移量,高} $\(32 - 12 = 20\) 位表示虚页号(VPN)。
  3. 检查两条指令的虚拟地址:
    • 第 1 行 push 指令虚拟地址为 0040 1000H,高 20 位(前 5 个十六进制位)为 00401H;
    • 第 30 行 ret 指令虚拟地址为 0040 105AH,高 20 位同样为 00401H。
  4. 结论:由于两者的虚页号完全相同,故它们在同一页中。

  5. 第 (2) 问解析:

  6. 块内地址位宽:主存块大小为 \(64\,\text{B} = 2^6\,\text{B}\),因此块内地址占低 6 位(即第 0 位至第 5 位)。
  7. Cache 组号位宽:Cache 共有 64 行,采用 4 路组相联映射,故组数: $\(N_{\text{set}} = \frac{64}{4} = 16 = 2^4\)$ 因此 Cache 组号占 4 位(即第 6 位至第 9 位)。
  8. 标记(Tag)位宽:主存地址总位宽为 32 位,去除块内偏移和组号后: $$ \text{Tag 位宽} = 32 - 4 - 6 = 22 \text{ 位} $$ 因此高 22 位(即第 10 位至第 31 位)表示 Tag 标记。

  9. 第 (3) 问解析:

  10. 读取第 16 行 call 指令,其虚拟地址为 0040 1025H。
  11. 虚实地址低位重叠原理:由于页面大小为 \(4\,\text{KB} = 2^{12}\,\text{B}\),分页管理机制保证了物理地址的低 12 位与虚拟地址的低 12 位完全相同。
  12. 虚拟地址 0040 1025H 的低 12 位为 025H,展开为二进制比特: $$ \text{025\text{H} = \underbrace{00}{\text{bit 11~10}} \underbrace{0000} $$}} \underbrace{100101}_{\text{bit 5~0: 块内地址}}
  13. Cache 组号由物理地址的第 6 位到第 9 位决定,而在低 12 位重合区间内: $\(\text{bit } 9 \sim 6 = 0000_2 = 0\)$
  14. 因此,无论该虚拟页面最终被映射到物理内存的哪一个物理页框中,其对应的物理地址的第 6 至第 9 位必然恒为 0,故该指令只可能在指令 Cache 的第 0 组中命中。

【标准答案】

(1) 在同一页中。理由:页面大小为 4KB,虚拟地址的高 20 位为虚页号,两者的虚拟地址高 20 位均为 00401H,因此在同一页。
(2) 低 6 位(bit 0~5)表示块内地址;中间 4 位(bit 6~9)表示 Cache 组号;高 22 位(bit 10~31)表示标记(Tag)信息。
(3) 只可能在 第 0 组 中命中。理由:虚拟地址与物理地址的低 12 位完全相同,call 指令虚拟地址的低 12 位为 025H,其对应的第 6~9 位(Cache 组号)为二进制 0000B,对应组号 0。


【真题 6】2020 年 408 第 46 题 · 二级分页数组元素虚拟地址计算与PDE/PTE物理地址求解

题目:
某 32 位系统采用基于二级页表的请求分页存储管理方式,按字节编址,页目录项和页表项长度均为 4 字节,虚拟地址结构如下所示:

+--------------------+--------------------+--------------------+
| 页目录号 (10 位)  |    页号 (10 位)    | 页内偏移量 (12 位) |
+--------------------+--------------------+--------------------+
某 C 程序中数组 a[1024][1024] 的起始虚拟地址为 1080 0000H,数组元素占 4 字节,该程序运行时,其进程的页目录起始物理地址为 0020 1000H。请回答下列问题:
(1) 数组元素 a[1][2] 的虚拟地址是什么?对应的页目录号和页号分别是什么?对应的页目录项的物理地址是什么?若该目录项中存放的页框号为 00301H,则 a[1][2] 所在页对应的页表项的物理地址是什么?
(2) 数组 a 在虚拟地址空间中所占区域是否必须连续?在物理地址空间中所占区域是否必须连续?
(3) 已知数组 a 按行优先方式存放,若对数组 a 分别按行遍历和按列遍历,则哪一种遍历方式的局部性更好?

【解析】

  1. 第 (1) 问解析:
  2. 虚拟地址计算:
    • C 语言中二维数组 a[1024][1024] 按行优先存储,每个元素占 4 字节。
    • 元素 a[1][2] 之前包含整整一行(a[0] 共 1024 个元素)以及第一行的前 2 个元素(a[1][0], a[1][1]),总元素偏移量为: $\(\Delta N = 1 \times 1024 + 2 = 1026\)$
    • 字节偏移量: $\(\Delta \text{Bytes} = 1026 \times 4\,\text{B} = 4104\,\text{B} = 4096\,\text{B} + 8\,\text{B} = 1008\text{H}\)$
    • 虚拟地址: $\(VA = 1080\,0000\text{H} + 1008\text{H} = 1080\,1008\text{H}\)$
  3. 页目录号与页号提取:
    • 将 1080 1008H 展开为二进制: $$ \text{\underbrace{00\,0100\,0010}{\text{高 10 位:页目录号}} \underbrace{00\,0000\,0001} $$}} \underbrace{0000\,0000\,1000}_{\text{低 12 位:页内偏移}}
    • 页目录号:\(0001000010_2 = 42\text{H}\)(即十六进制 042H,十进制 66)。
    • 页号:\(0000000001_2 = 1\text{H}\)(即十六进制 001H,十进制 1)。
  4. 页目录项(PDE)物理地址计算:
    • 进程页目录起始物理地址为 0020 1000H,每个页目录项占 4 字节。
    • 该元素对应的页目录号为 \(42\text{H}\),因此对应 PDE 的物理地址为: $\(PA_{\text{PDE}} = 0020\,1000\text{H} + 42\text{H} \times 4 = 0020\,1000\text{H} + 108\text{H} = 0020\,1108\text{H}\)$
  5. 二级页表项(PTE)物理地址计算:

    • 该目录项中存放的二级页表所在的物理页框号为 00301H。
    • 页面大小为 4KB(12 位),因此二级页表的物理基地址为: $\(Base_{\text{PT}} = 00301\text{H} \ll 12 = 0030\,1000\text{H}\)$
    • 对应的二级页号为 \(1\text{H}\),每个页表项占 4 字节。
    • 对应的二级页表项物理地址为: $\(PA_{\text{PTE}} = Base_{\text{PT}} + 1\text{H} \times 4 = 0030\,1000\text{H} + 004\text{H} = 0030\,1004\text{H}\)$
  6. 第 (2) 问解析:

  7. 虚拟地址空间:必须连续。在高级语言(C 语言)及操作系统内存管理规范中,数组通过基地址加首尾索引乘下标步长进行随机寻址访存(即 \(a[i][j] = \&a[0][0] + (i \times N + j) \times \text{sizeof}\)),编译器和链接器为其分配连续的线性虚拟地址空间。
  8. 物理地址空间:不必须连续(可以离散)。分页机制的核心设计目的正是解除虚拟地址连续性与物理地址连续性的耦合。各虚拟页可以被操作系统离散分配到物理内存的任意可用页框中。

  9. 第 (3) 问解析:

  10. 按行遍历的局部性更好。
  11. 深入分析:由于一行元素占 \(1024 \times 4\,\text{B} = 4096\,\text{B} = 4\,\text{KB}\),恰好等于一个页面的容量。
  12. 若按行遍历,访问完当前页面内的全部 1024 个元素后才会跨入下一页,空间局部性极好,页表与 TLB 命中率高,缺页率低;
  13. 若按列遍历,每次访问相邻元素(如从 \(a[0][0]\)$ \text{到} $\(a[1][0]\))跨度均为 4KB,直接跳入下一个不同的虚拟页面,引发连续的 TLB Miss 和剧烈的缺页中断抖动,空间局部性极差。

【标准答案】

(1) - 虚拟地址:10801008H - 页目录号:042H(或 \(42\text{H}\),十进制 66) - 页号:001H(或 \(1\text{H}\),十进制 1) - 页目录项物理地址:00201108H - 二级页表项物理地址:00301004H
(2) 数组 a 在虚拟地址空间中所占区域必须连续;在物理地址空间中所占区域不必须连续。
(3) 按行遍历的局部性更好。


【真题 7】2021 年 408 第 44 题 · 虚拟地址划分、TLB组相联映射与LRU替换序列

题目:
假设计算机 M 的主存地址为 24 位,按字节编址;采用分页存储管理方式,虚拟地址为 30 位,页大小为 4KB;TLB 采用 2 路组相联方式和 LRU 替换策略,共 8 组。请回答下列问题:
(1) 虚拟地址中哪几位表示虚页号?哪几位表示页内地址?
(2) 已知访问 TLB 时虚页号高位部分用作 TLB 标记,低位部分用作 TLB 组号,M 的虚拟地址中哪几位是 TLB 标记?哪几位是 TLB 组号?
(3) 假设 TLB 初始时为空,访问的虚页号依次为 10、12、16、7、26、4、12 和 20,在此过程中,哪一个虚页号对应的 TLB 表项被替换?说明理由。
(4) 若将 M 中的虚拟地址位数增加到 32 位,则 TLB 表项的位数增加几位?

【解析】

  1. 第 (1) 问解析:
  2. 页面大小为 \(4\,\text{KB} = 2^{12}\,\text{B}\),按字节编址,因此页内地址占低 12 位(第 0 位至第 11 位)。
  3. 虚拟地址位宽总共为 30 位,因此虚页号(VPN)占高 \(30 - 12 =\) 18 位(第 12 位至第 29 位)。

  4. 第 (2) 问解析:

  5. TLB 共 8 组,\(8 = 2^3\),因此 TLB 组号占 3 位。
  6. 题目指明虚页号低位用作 TLB 组号,高位用作 TLB 标记:

    • TLB 组号位于虚拟地址中紧跟页内地址之上的 3 位,即虚拟地址的第 12 位至第 14 位。
    • TLB 标记位于虚页号的高位,占 \(18 - 3 = 15\) 位,即虚拟地址的第 15 位至第 29 位。
  7. 第 (3) 问解析:

  8. 组映射函数:虚页号映射到 TLB 的组号公式为: $$ \text{组号} = VPN \bmod 8 $$
  9. 计算给定的虚页号序列对应的映射组号:
    • 虚页号 10: \(10 \bmod 8 = 2 \implies\) 映射到第 2 组
    • 虚页号 12: \(12 \bmod 8 = 4 \implies\) 映射到第 4 组
    • 虚页号 16: \(16 \bmod 8 = 0 \implies\) 映射到第 0 组
    • 虚页号 7: \(7 \bmod 8 = 7 \implies\) 映射到第 7 组
    • 虚页号 26: \(26 \bmod 8 = 2 \implies\) 映射到第 2 组
    • 虚页号 4: \(4 \bmod 8 = 4 \implies\) 映射到第 4 组
    • 虚页号 12: \(12 \bmod 8 = 4 \implies\) 映射到第 4 组
    • 虚页号 20: \(20 \bmod 8 = 4 \implies\) 映射到第 4 组
  10. 容量与冲突分析:

    • TLB 为 2 路组相联,意味着每个组最多只能容纳 2 个表项。
    • 只有第 4 组的访问次数超过了路数容量(2 次以上):
    • 访问 12:第 4 组装入 [12](组内表项数 1);
    • 访问 4:第 4 组装入 [12, 4](组内表项数 2,已满);
    • 再次访问 12:命中!根据 LRU 策略,表项 12 的访问活跃时间被更新为最新,此时最近最少使用的表项变为 4;
    • 访问 20:第 4 组缺失且已满,触发 LRU 淘汰。此时组内表项为活跃的 12 与最久未使用的 4,因此表项 4 被淘汰替换出来,第 4 组变为 [12, 20]。
  11. 第 (4) 问解析:

  12. 虚拟地址从 30 位扩展到 32 位,增加了 \(32 - 30 = 2\) 位。
  13. 页面大小保持 4KB 不变(页内偏移仍为 12 位),TLB 组数保持 8 组不变(组索引仍为 3 位)。
  14. 增加的 2 位全部归入虚页号,且全部增加到虚页号的高位,即 TLB 标记(Tag)字段增加了 2 位。
  15. TLB 表项保存的内容包括:有效位、Tag 标记、物理页框号、访问位、修改位等。由于其他字段长度不变,Tag 字段增加 2 位直接使得每个 TLB 表项的位宽增加 2 位。

【标准答案】

(1) 高 18 位(第 12~29 位)表示虚页号,低 12 位(第 0~11 位)表示页内地址。
(2) 虚拟地址的第 15~29 位为 TLB 标记,第 12~14 位为 TLB 组号。
(3) 虚页号 4 对应的 TLB 表项被替换。理由:各虚页号映射到的 TLB 组号依次为 2, 4, 0, 7, 2, 4, 4, 4。仅有映射到第 4 组的虚页号数量超过 2 个。访问序列为 12(装入)、4(装入)、12(命中并刷新活跃度)、20(引发替换)。根据 LRU 策略,访问 20 时,4 为最近最少使用的表项,故虚页号 4 被替换。
(4) TLB 表项的位数增加 2 位。


四、 综合考法拓展

在近年 408 统考命题中,“地址翻译”已成为贯穿计算机组成原理(流水线/Cache/TLB/主存)与操作系统(进程/虚存/中断/系统调用)交叉命题的核心枢纽。掌握以下综合大题破题框架至关重要。

1. 跨学科联合访存全链路时序模型

当 CPU 执行一条访存指令(如 mov eax, [0x10801008])时,软硬件体系的真实协同判定流程如下:

[ 虚拟地址 (VA) ]
       |
       v
+--------------+        Hit        +--------------------+
|   TLB 检索   | ----------------> |  直接获取物理页框号   |
+--------------+                   +--------------------+
       | Miss                                 |
       v                                      |
+--------------+        有效位=0               |
|  页表查询遍历  | ----------------> [ 触发缺页异常中断 ]
+--------------+                   (转入内核态调页更新)
       | 有效位=1                             |
       v                                      |
+--------------+                              |
| 获得物理页框号 | <----------------------------+
+--------------+
       |
       +--> 物理地址 (PA) = PFN || PPO (其中 PPO = VPO)
       |
       v
+--------------+        Hit        +--------------------+
|  Cache 检索  | ----------------> | CPU 极速取得数据/指令|
+--------------+                   +--------------------+
       | Miss
       v
+--------------+
| 主存 DRAM 访问| (若发生脏块替换则写回主存)
+--------------+

2. 综合题通用解题模板(万能三步法)

无论题目形式如何变化,求解地址翻译大题均应严格遵循以下三步:

  • 第一步:建立标尺,量化比特宽度
  • 页内偏移位宽:\(p = \log_2(\text{Page Size})\)
  • 虚页号总位宽:$$ \text{VPN = \text{虚拟地址位宽} - p} $$
  • 多级索引划分:若为 \(N\)$ \text{级页表,根据题意列出} $\([P_1 \mid P_2 \mid \dots \mid P_N \mid D]\) 的每一段比特范围。
  • Cache / TLB 字段划分:按 \([Tag \mid SetIndex \mid Offset]\) 划定边界。
  • 第二步:十六进制严密转二进制,坚决避免口算误差
  • 将十六进制地址按 4 位一组完整写出,切忌只展开部分位;
  • 按照第一步标尺的位宽边界,从高位到低位画分割竖线;
  • 提取出各个字段的二进制值,并在高位补 0 规范转化为十六进制或十进制。
  • 第三步:基地址与表项偏移精算(物理地址生成)
  • 谨记:页目录基址寄存器(PDBR)存放的是物理地址!
  • 页目录项物理地址:\(PA_{\text{PDE}} = Base_{\text{DIR}} + P_1 \times \text{Size}_{\text{PDE}}\)
  • 二级页表物理基址:从 PDE 中读取的虚页框号必须左移 \(p\)$ \text{位(} $\(Base_{\text{PT}} = PFN_{\text{PT}} \ll p\)),切勿将整个 PDE 原始内容直接充当基址!
  • 二级页表项物理地址:\(PA_{\text{PTE}} = Base_{\text{PT}} + P_2 \times \text{Size}_{\text{PTE}}\)

3. 得分要点与踩分陷阱防范

  1. PDE 物理页框号提取陷阱: 综合题中 PDE 往往包含属性标志位(低 12 位)。例如 PDE 内容为 00301007H,其中 007H 是读写/存在控制位,真正的物理页框号为高 20 位 00301H,对应的二级页表物理基址应为 00301000H,绝不可带入低位控制标志进行基址加法!
  2. 段式与页式越界判断边界陷阱:
  3. 分段管理中,段长为 \(\text{Limit}\)$ \text{,合法地址偏移量必须在} $\([0, \text{Limit}-1]\)$ \text{范围内。当} $\(W = \text{Limit}\) 时即为越界(2016 年真题核心考点)。
  4. 分页管理中,页内偏移量自动利用二进制模运算限制在 \([0, 2^p - 1]\) 之间,硬件物理上不会产生页内偏移越界,仅存在虚页号超出进程页表长度寄存器的越界。

五、 考点速记清单

1. 核心要点速记表

  • PDBR 属性:保存页目录表物理基地址,属于硬件 MMU 上下文;进程切换时刷新,线程切换时保持不变。
  • 虚实低位重合:\(VA\)$ \text{低 12 位与} $\(PA\) 低 12 位恒等(以 4KB 页面为例)。Cache 组索引若落在低 12 位内,可直接用虚拟地址查 Cache(VIPT)。
  • 缺页与异常:缺页中断属于内部异常(故障 Fault),处理完毕后返回发生缺页的那条指令重新执行;越界异常属于故障,直接终止进程。
  • 改进型 Clock 算法位设置:必须具备访问位(使用位)与修改位(脏位)。
  • TLB 组相联与 LRU:虚页号低位充当 TLB 组号,高位充当 TLB Tag。扩展虚拟地址位数只增加 Tag 位宽。

2. 常用计算公式汇总

  1. 页面偏移位数:\(p = \log_2(\text{Page Size})\)
  2. 单页最多容纳页表项数:\(N_{\text{entry}} = \frac{\text{Page Size}}{\text{PTE Size}} = 2^{p - m}\)
  3. 虚页号与物理页号: $\(\text{VPN} = \lfloor VA / 2^p \rfloor = VA \gg p, \quad VPO = VA \bmod 2^p\)$ $\(PA = (PFN \ll p) \mid VPO\)$
  4. 二级页表地址计算: $\(PA_{\text{PDE}} = Base_{\text{DIR}} + P_1 \times \text{Size}_{\text{PDE}}\)$ $\(PA_{\text{PTE}} = (PFN_{\text{PT}} \ll p) + P_2 \times \text{Size}_{\text{PTE}}\)$
  5. Cache 组号:\(SetIndex = (PA \gg b) \bmod N_{\text{set}}\)

3. 解题避坑口诀

展开二进制,切勿凭空算;
标尺画清楚,高位向低排。
段式比段长,大于等于亡;
页内同虚实,组号低位藏。
进程换目录,线程切不忙;
PDBR 记物理,表项乘长加基址。