跳转至

408 高频考点精讲:虚拟页式管理

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


一、 考情档案

1. 历年考查频次与题号清单

  • 近十年考查频次:14 次(2016~2025 年)
  • 近十年真题清单:
  • 2016 年:第 45 题(综合解答题,14 分)
  • 2018 年:第 44 题(综合解答题,13 分)
  • 2020 年:第 46 题(综合解答题,15 分)
  • 2023 年:第 28 题(单项选择题,2 分)、第 30 题(单项选择题,2 分)、第 43 题(综合解答题,15 分)
  • 2024 年:第 16 题(单项选择题,2 分)、第 18 题(单项选择题,2 分)、第 25 题(单项选择题,2 分)、第 44 题(综合解答题,5 分)、第 45 题(综合解答题,7 分)
  • 2025 年:第 23 题(单项选择题,2 分)、第 27 题(单项选择题,2 分)、第 43 题(综合解答题,15 分)
  • 历年总考查频次:20 次(2009~2025 年)
  • 出题形式:单项选择题与综合解答题并重。近五年呈现出“高频选择题 + 跨学科(计算机组成原理/操作系统)超大分值综合解答题”的深度考查趋势。

2. 命题特点分析

  1. 多层次软硬件协同贯通:统考命题极度偏好将操作系统中的虚拟页式管理与计算机组成原理中的 Cache 映射、TLB(快表)、MMU 硬件地址翻译、指令寻址及流水线异常处理进行一体化考查(如 2016#45、2018#44、2023#43、2024#44、2025#43)。
  2. 地址翻译计算精度要求极高:深入考查虚拟地址二进制切分、多级页表索引、页表项物理定位、页表自映射、跨页边界判定等定量计算(如 2020#46、2024#45、2025#43)。
  3. 程序执行局部性与性能量化:结合二维数组行优先/列优先遍历、循环嵌套展开,考查缺页率、Cache 缺失率以及平均访存时间的精确推导。
  4. 底层运行机制辨析深入:针对进程上下文切换(CR3/PTBR 更新)、TLB 缺失 vs 缺页异常 vs Cache 缺失的处理主体与时序、硬件寻址方式对最少页框数的约束等原理进行深度设问。

3. 近十年考查年份分布表格

+------+------------+-------------------------------------------------------+----------+
| 年份 | 题号       | 考查主题 / 核心考点                                   | 题型     |
+------+------------+-------------------------------------------------------+----------+
| 2016 | 第 45 题   | 页式虚拟存储与 Cache/TLB 联合映射、写策略及缺失开销   | 综合解答 |
| 2018 | 第 44 题   | 二级页表、TLB 与 2 路组相联 Cache 协同翻译与容量计算   | 综合解答 |
| 2020 | 第 46 题   | 二级页表地址转换、页表项物理寻址与数组遍历局部性      | 综合解答 |
| 2023 | 第 28 题   | 进程虚拟地址空间特征与容量决定因素                    | 单项选择 |
| 2023 | 第 30 题   | 进程间共享数据的页号与页框号对应关系                  | 单项选择 |
| 2023 | 第 43 题   | 请求分页缺页分析、Cache 组映射与循环遍历命中率计算    | 综合解答 |
| 2024 | 第 16 题   | 存储层次结构对比(Cache-主存 vs 主存-外存)           | 单项选择 |
| 2024 | 第 18 题   | MMU 硬件地址转换过程中的异常检测范围                  | 单项选择 |
| 2024 | 第 25 题   | 页式存储管理进程上下文切换需更新的寄存器集合          | 单项选择 |
| 2024 | 第 44 题   | 汇编指令寻址、小端存储与页式虚拟内存跨页定位          | 综合解答 |
| 2024 | 第 45 题   | 4MB 大页管理、缺页异常处理与页表自映射物理定位        | 综合解答 |
| 2025 | 第 23 题   | 进程上下文切换中的内核寄存器状态保持与更新判定        | 单项选择 |
| 2025 | 第 27 题   | 进程运行所需最少页框数的硬件约束条件(寻址方式)      | 单项选择 |
| 2025 | 第 43 题   | 虚拟分页与 Cache 联合访问性能评估、访存周期与缺页计算 | 综合解答 |
+------+------------+-------------------------------------------------------+----------+

二、 具体考察内容

1. 核心概念与机制原理

(1) 虚拟存储器与局部性原理

  • 虚拟存储器定义:基于局部性原理,在具有调页功能和页面置换功能的支持下,将离散分配的物理主存与辅存(如磁盘交换区)结合,为进程提供一个容量远大于实际物理主存的逻辑存储空间。
  • 局部性原理:
  • 时间局部性:最近被访问的指令或数据在不久的将来很可能再次被访问(典型场景:循环结构、临时变量)。
  • 空间局部性:一旦某个存储单元被访问,其相邻的存储单元在不久的将来也很可能被访问(典型场景:数组顺序遍历、顺序执行指令流)。

(2) 页式虚拟存储系统数据结构

虚拟页式管理依赖页表(Page Table)实现虚拟页号(VPN, Virtual Page Number)到物理页框号(PFN, Physical Frame Number)的映射。请求分页系统中,页表项(PTE, Page Table Entry)包含以下核心控制字段:

+----------+---------------+--------+--------+--------+--------+
| 物理页框号 | 有效位/存在位 | 访问位 | 修改位 | 保护位 | 外存块号 |
+----------+---------------+--------+--------+--------+--------+
  • 物理页框号(PFN):该虚拟页驻留主存时的物理基址高位部分。
  • 有效位 / 存在位(Valid / Present Bit):指示该页面是否已调入物理主存(\(1\)$ \text{表示在主存中;} $\(0\) 表示未调入,引发缺页异常)。
  • 访问位 / 引用位(Access / Reference Bit):记录该页最近是否被访问过,供页面置换算法(如 CLOCK、LRU 近似算法)决策使用。
  • 修改位 / 脏位(Dirty / Modified Bit):指示该页面调入主存后内容是否被修改。若页面被置换淘汰且修改位为 \(1\)$ \text{,必须写回辅存;若为} $\(0\),可直接丢弃,无需写回。
  • 保护位(Protection Bits):定义该页面的访问权限(只读、读写、可执行等)。

(3) 地址映射与多级页表

  • 单级页表机制:页表必须在物理内存中连续存放。虚拟地址划分为虚拟页号 \(VPN\)$ \text{与页内偏移量} $\(Offset\)$ \text{。若虚拟地址空间过大(如 32 位系统且页大小为 4KB,虚拟页数多达} $\(2^{20}\)$ \text{),连续存放页表将消耗} $\(2^{20} \times 4\text{B} = 4\text{MB}\) 连续主存空间,违背离散分配初衷。
  • 多级页表机制:将单级页表离散分配,建立页目录与二级/多级页表结构。
  • 各级页表项中记录的是下一级页表的起始物理地址。
  • 关键特性:只有根页表(顶级页目录)必须常驻内存,且进程的页表基址寄存器(PTBR / CR3)存放根页目录的物理基地址;下级页表可以按需动态创建或调入,大幅降低常驻内存开销。

(4) 快表(TLB, Translation Lookaside Buffer)机制

  • 概念:设在 MMU 内部的高速缓存(通常采用相联存储器 CAM 或静态 RAM 构建),用于存放近期频繁访问的高频页表项副本。
  • 查找时序:CPU 发出虚拟地址后,MMU 首先根据虚页号并行检索 TLB:
  • TLB 命中:直接获取物理页框号,无须访问主存页表,将物理页框号与页内偏移拼接即得物理地址。
  • TLB 缺失:MMU 或操作系统异常处理程序访问主存中的多级页表,若页表项有效,则将该项装入 TLB 并完成地址转换;若页表项指示不在主存,则触发缺页异常。

(5) 缺页异常处理全流程

缺页异常(Page Fault)属于 CPU 内部异常中的故障(Fault)。其标准处理流程如下: 1. 硬件检测与陷入:MMU 检索页表项发现有效位为 \(0\),硬件产生缺页中断向量,保护断点现场(保存发生异常的指令 PC 及 CPU 状态),陷入内核态。 2. 缺页中断处理程序执行: - 检查虚拟地址合法性(是否越界、是否越权)。若非法,则向进程发送 SIGSEGV 信号终止进程。 - 检查物理主存是否有空闲页框。若无,调用页面置换算法(如 LRU、CLOCK)选出牺牲页。若牺牲页被修改(脏位为 \(1\)),必须调用设备驱动将其写回外存交换区。 - 启动磁盘 I/O,将所需页面自外存交换区读入空闲页框,进程转入阻塞态。 - 页面载入完成后,磁盘中断唤醒该进程,操作系统更新相应页表项(有效位置 \(1\),填入 PFN,清除修改位),并将该进程置为就绪态。 3. 恢复执行:调度器重新调度该进程,恢复 CPU 现场,重新执行发生缺页的那一条指令。


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

(1) 地址空间划分与多级页表计算模型

设系统按字节编址,虚拟地址位宽为 \(V\)$ \text{位,物理地址位宽为} $\(M\)$ \text{位,页面大小为} $\(P = 2^p\) 字节,则: - 页内偏移量位数:\(p\) 位。 - 虚拟页号(VPN)位数:\(k = V - p\)$ \text{位,虚拟地址空间最大包含} $\(2^{V - p}\) 个逻辑页面。 - 物理页框号(PFN)位数:\(m = M - p\)$ \text{位,物理内存最大包含} $\(2^{M - p}\) 个物理页框。 - 页表项大小设计约束:页表项至少需容纳 \(m\)$ \text{位物理页框号及若干状态控制位(有效位、脏位、引用位、保护位等)。设页表项大小为} $\(e\)$ \text{字节,通常向上对齐为} $\(2\) 的幂次(如 4 字节或 8 字节)。 - 多级页表级数推导:为保证每个页表块恰好占用一个物理页面(便于离散分配),每个页面可容纳的页表项数为 \(N = P / e = 2^p / 2^s = 2^{p - s}\)$ \text{个。此时每级页表索引占} $\(p - s\)$ \text{位。多级页表的级数} $\(L\) 满足: $\(L = \left\lceil \frac{V - p}{p - s} \right\rceil\)$

(2) 有效访存时间(EAT, Effective Access Time)推导

设主存单次访问时间为 \(t_m\)$ \text{,TLB 查找时间为} $\(t_{tlb}\)$ \text{,TLB 命中率为} $\(\alpha\): - 含 TLB 的单级页表系统: $\(EAT = t_{tlb} + \alpha \cdot t_m + (1 - \alpha) \cdot (t_m + t_m) = t_{tlb} + t_m + (1 - \alpha) \cdot t_m\)$ (注:缺失时访问一次主存页表获取物理地址,再访问一次主存获取数据) - 含 TLB 的 \(n\) 级页表系统: $\(EAT = t_{tlb} + \alpha \cdot t_m + (1 - \alpha) \cdot (n \cdot t_m + t_m)\)$ - 考虑缺页异常开销的完整模型:设缺页率为 \(f\)$ \text{,缺页中断处理与磁盘 I/O 平均开销为} $\(t_{fault}\): $\(EAT = (1 - f) \cdot EAT_{hit} + f \cdot t_{fault}\)$

(3) 经典页面置换算法模型

  • 最佳置换算法(OPT):淘汰未来最长时间内不再被访问的页面。理想算法,无法实际实现,作为性能评价基准。
  • 先进先出算法(FIFO):淘汰最早进入主存的页面。存在 Belady 异常(分配的物理页框数增加,缺页次数反而增加)。
  • 最近最久未使用算法(LRU):淘汰自上次被访问以来经历时间最长的页面。性能优异,需硬件堆栈或计数器支持。
  • 简单时钟算法(CLOCK / NRU):为每页设置 1 位访问位 \(A\)$ \text{。指针循环扫描,遇} $\(A=1\)$ \text{置} $\(0\)$ \text{,遇} $\(A=0\) 淘汰。
  • 改进型时钟算法:结合访问位 \(A\)$ \text{和修改位} $\(M\),按优先级分四轮扫描(首选无访问且无修改的页):
  • 第一轮:寻找 \((A=0, M=0)\),不修改任何位。
  • 第二轮:若失败,寻找 \((A=0, M=1)\)$ \text{,将所经过的所有页的} $\(A\)$ \text{置为} $\(0\)。
  • 第三轮:若仍失败,指针重新循环寻找 \((A=0, M=0)\),不修改任何位。
  • 第四轮:寻找 \((A=0, M=1)\)。

(4) 工作集与颠簸(抖动)模型

  • 工作集 \(W(t, \Delta)\)$ \text{:某进程在时间段} $\([t - \Delta, t]\)$ \text{内实际访问的逻辑页面集合,} $\(\Delta\) 称为工作集窗口大小。
  • 驻留集(Resident Set):操作系统当前实际分配给该进程的物理页框集合。
  • 颠簸(Thrashing)发生的充要条件:系统中所有活跃进程的工作集大小之和超过了系统可用的实际物理页框总数,导致进程频繁缺页、CPU 极度闲置、磁盘 I/O 队列极度饱和。

(5) 硬件指令集对最少物理页框数的约束模型

进程运行所需的最少页框数与进程大小、虚拟地址空间无关,完全由计算机硬件指令系统架构与寻址方式决定。 - 若指令系统支持双操作数指令,且操作数支持跨页访问与多级间接寻址: - 指令自身跨页:最多占用 \(2\) 个页框。 - 源操作数间接寻址及数据跨页:指针可能跨页(\(2\)$ \text{个页框),最终操作数跨页(} $\(2\) 个页框)。 - 目的操作数间接寻址及数据跨页:同理可能占用多个页框。 - 结论:若系统必须保证一条指令执行中不发生由于页框不足导致的前后页面反复颠簸置换,硬件必须为该进程提供至少满足单条指令最大可能并发引用页面数的物理页框。


3. 核心对比辨析

(1) 异常与缺失机制三维度对比

比较维度 TLB 缺失 (TLB Miss) 缺页异常 (Page Fault) Cache 缺失 (Cache Miss)
发生阶段 MMU 进行虚拟地址翻译阶段 虚拟地址转换查询页表阶段 得到物理地址后访问主存数据阶段
检测主体 MMU 硬件逻辑 MMU 硬件检测到有效位为 0 Cache 控制器硬件匹配 Tag
处理主体 硬件自动遍历页表或软中断填充 操作系统缺页异常处理程序(软件) Cache 控制器硬件自动调度总线
处理开销 极小(几纳秒至几十纳秒,访问主存) 极大(数毫秒至数十毫秒,磁盘 I/O) 很小(几十纳秒,访问主存)
是否引发中断 软硬件相关(x86为硬件,MIPS为异常) 必然触发 CPU 内部异常(Fault) 不触发中断,CPU 流水线暂停等待
现场恢复 重新进行 TLB 检索 重新执行触发缺页的指令 恢复流水线继续执行

(2) 存储体系两级层次结构对比

对比维度 Cache - 主存层次 主存 - 外存层次(虚拟页式存储)
设置目标 解决 CPU 与主存之间的速度失配问题 解决主存容量不足及离散保护问题
数据交换单位 主存块(Cache Line,通常 32B ~ 128B) 页面(Page,通常 4KB ~ 4MB)
映射方式 直接映射、全相联映射或组相联映射 全相联映射(任意逻辑页可放入任意物理页框)
替换控制实现 完全由专用硬件高速实现 操作系统软件配合硬件标志位实现
写策略 直写策略(Write-Through)或回写策略(Write-Back) 仅采用回写策略(磁盘写入开销巨大,严禁直写)
未命中损失 几十到上百个 CPU 时钟周期 数十万到数百万个 CPU 时钟周期

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

【真题 1】2016 年 408 第 45 题 · 虚拟分页系统与 Cache/TLB 联合访存综合分析

题目: 某计算机采用页式虚拟存储管理方式,按字节编址,虚拟地址为 32 位,物理地址为 24 位,页大小为 8KB;TLB 采用全相联映射;Cache 数据区大小为 64KB,按 2 路组相联方式组织,主存块大小为 64B。存储访问过程的示意图如下。

虚拟地址:  [  A  位 (虚页号)  ] [  D  位 (页内地址)  ]
TLB 项:    [ B 标记 ][ 页框号 ][ 存在位 ]
物理地址:  [  C  位 (页框号)  ] [  D  位 (页内地址)  ]
Cache 寻址:[ E 标记 ][ F 组号 ][ G 块内地址 ]
           Cache 比较器输入: E 标记 与 H 字段

请回答下列问题。 (1) 图中字段 A~G 的位数各是多少?TLB 标记字段 B 中存放的是什么信息? (2) 将块号为 4099 的主存块装入到 Cache 中时,所映射的 Cache 组号是多少?对应的 H 字段内容是什么? (3) Cache 缺失处理的时间开销大还是缺页处理的时间开销大?为什么? (4) 为什么 Cache 可以采用直写(Write Through)策略,而修改页面内容时总是采用回写(Write Back)策略?

【解析】

  1. 字段 A~G 位数推导及 B 字段含义:
  2. 页大小为 \(8\text{KB} = 2^{13}\text{B}\)$ \text{,因此页内偏移量位数} $\(D = 13\) 位。
  3. 虚拟地址总长 32 位,故虚页号字段 \(A = 32 - 13 = 19\) 位。
  4. TLB 采用全相联映射,存放虚拟页号到页框号的映射,故 TLB 标记字段 \(B\)$ \text{对应虚页号,} $\(B = A = 19\) 位,存放的内容是虚页号。
  5. 物理地址总长 24 位,页内偏移 \(D = 13\)$ \text{位,故物理页框号字段} $\(C = 24 - 13 = 11\) 位。
  6. 主存块大小为 \(64\text{B} = 2^6\text{B}\)$ \text{,故 Cache 块内地址字段} $\(G = 6\) 位。
  7. Cache 数据区容量为 64KB,按 2 路组相联组织,每组容量为 \(2 \times 64\text{B} = 128\text{B}\)。
  8. Cache 组数 \(= 64\text{KB} / 128\text{B} = 512 = 2^9\)$ \text{组,故组号字段} $\(F = 9\) 位。

  9. 物理地址总长 24 位,Cache 标记字段 $E = 24

  10. F

  11. G = 24

  12. 9

  13. 6 = 9$ 位。

  14. 块号 4099 映射组号与 H 字段计算:
  15. 物理地址划分为:Tag(9 位)+ 组号(9 位)+ 块内地址(6 位)。
  16. 主存块号由 Tag 与组号拼接而成,共 \(9 + 9 = 18\) 位。主存块号为 4099,转换为 18 位二进制数: $\(4099 = 4096 + 3 = 000001000000000011_2\)$
  17. 低 9 位为 Cache 组号:\(000000011_2 = 3\)。
  18. 高 9 位为 Tag(即 H 字段内容):\(000001000_2\)$ \text{(十六进制为} $\(008\text{H}\)$ \text{或二进制} $\(000001000_2\))。
  19. Cache 缺失与缺页处理时间开销对比:
  20. 缺页处理开销远大于 Cache 缺失开销。
  21. 原因:Cache 缺失只需访问物理主存(纳秒级开销),且完全由硬件逻辑自动控制;而缺页处理需要通过软中断陷入操作系统内核,涉及磁盘 I/O 操作将页面自外存交换区调入内存(毫秒级开销),二者相差数十万倍。
  22. 写策略差异原因:
  23. 直写策略需要在更新当前存储层时同时同步写入下一级慢速存储层。
  24. 在 Cache-主存层级,主存为半导体存储器,写入速度快,采用直写策略开销在可容忍范围内,且硬件实现简单;
  25. 在主存-外存层级,外存为机械硬盘或低速闪存,写磁盘的时间开销极其高昂。若每次修改内存页面都同步直写磁盘,系统性能将急剧恶化崩溃。因此修改页面时必须采用回写(Write Back)策略,仅当页面被换出且脏位为 1 时才执行磁盘写入。

正确答案: (1) \(A = 19\),\(B = 19\),\(C = 11\),\(D = 13\),\(E = 9\),\(F = 9\),\(G = 6\)。TLB 标记字段 B 中存放的是虚拟页号(虚页号)。
(2) 映射的 Cache 组号为 3;对应的 H 字段内容为 \(000001000_2\)$ \text{(或} $\(008\text{H}\))。
(3) 缺页处理的时间开销大。因为缺页处理涉及磁盘 I/O 且需要操作系统软件干预,而 Cache 缺失只需访问主存且由硬件自动完成。
(4) 因为直写策略需要同时写下一层存储器,写磁盘的速度远慢于写主存的速度。为避免极高的时间开销,主存-外存层级必须采用回写策略。


【真题 2】2018 年 408 第 44 题 · 二级页表、TLB 与组相联 Cache 协同翻译与容量计算

题目: 某计算机采用页式虚拟存储管理方式,按字节编址。CPU 进行存储访问的过程如题图所示。

CPU 给出虚拟地址: [ 虚页号: 20 位 (页目录号 10 位, 页表号 10 位) ] [ 页内地址: 12 位 ]
TLB: 全相联映射, Tag 匹配有效则直接输出 16 位实页号.
二级页表查找: PDBR -> 页目录项 (10位) -> 二级页表项 (10位) -> 16 位实页号.
物理地址拼接: [ 16 位实页号 ] [ 12 位页内地址 ] = 28 位物理地址.
Cache 寻址: 物理地址划分为 [ Tag: 20 位 ] [ 组号: 3 位 ] [ 块内地址: 5 位 ]
Cache 结构: 8 个组, 每组 2 行 (2 路组相联), 采用 LRU 与回写 (Write Back) 策略.

根据题图回答下列问题。 (1) 主存物理地址占多少位? (2) TLB 采用什么映射方式?TLB 用 SRAM 还是 DRAM 实现? (3) Cache 采用什么映射方式?若 Cache 采用 LRU 替换算法和回写(Write Back)策略,则 Cache 每行中除数据(Data)、Tag 和有效位外,还应有哪些附加位?Cache 总容量是多少?Cache 中有效位的作用是什么? (4) 若 CPU 给出的虚拟地址为 0008C040H,则对应的物理地址是多少?是否在 Cache 中命中?说明理由。若 CPU 给出的虚拟地址为 0007C260H,则该地址所在主存块映射到的 Cache 组号是多少?

【解析】

  1. 物理地址位数:
  2. 由图可知,TLB 或二级页表输出的实页号(物理页框号)占 16 位,虚拟地址中的页内地址占 12 位。
  3. 物理地址由实页号与页内地址直接拼接而成,故物理地址位数 \(= 16 + 12 = 28\) 位。
  4. 验证:Cache 寻址划分为 Tag(20 位)+ 组号(3 位)+ 块内地址(5 位),\(20 + 3 + 5 = 28\) 位,完全吻合。
  5. TLB 映射方式与实现介质:
  6. 映射方式:TLB 能够将任意虚页项装入任意项中,检索时各表项同时与虚页号通过比较器并行比对,为全相联映射。
  7. 物理介质:TLB 要求极高访问速度(需匹配 CPU 流水线时钟),故采用静态随机存取存储器(SRAM)实现。
  8. Cache 组织、附加位与总容量计算:
  9. 映射方式:图中每组包含 2 个 Cache 行,采用 2 路组相联映射。
  10. 附加位:
    • 采用回写(Write Back)策略,每行需设 1 位修改位(脏位 Dirty Bit);
    • 采用 LRU 替换算法,2 路组相联每组包含 2 行,表示先后次序仅需 1 位 LRU 替换位(每行 1 位或每组 1 位)。
  11. 容量计算:
    • Cache 组索引占 3 位,共 \(2^3 = 8\)$ \text{组;每组 2 行,共} $\(8 \times 2 = 16\) 行。
    • 块内地址占 5 位,每行数据区容量 \(= 2^5 = 32\text{B} = 256\) 位。
    • 每行总位数 $$ \text{= \text{Data}(256\text{位}) + \text{Tag}(20\text{位}) + \text{有效位}(1\text{位}) + \text{脏位}(1\text{位}) + \text{LRU位}(1\text{位}) = 279} $$ 位。
    • Cache 总容量 $$ \text{= 16 \times 279\text{位} = 4464\text{位} = 558\text{字节}} $$。
  12. 有效位作用:用于标识当前 Cache 行中的数据是否有效(1 有效,0 无效)。
  13. 地址转换与 Cache 命中判断:
  14. 虚拟地址 0008C040H:虚页号为高 20 位 0008CH,页内地址为低 12 位 040H。
  15. 查 TLB:虚页号 0008CH 存在于 TLB 项中,有效位为 1,对应的实页号为 0040H。
  16. 物理地址拼接:实页号 0040H(16 位)拼接页内地址 040H(12 位),得物理地址为 0040040H。
  17. 检验 Cache 命中:
    • 物理地址 0040040H 的二进制形式展开为 28 位: $\(0000\ 0000\ 0100\ 0000\ 0000\ 0010\ 0000_2\)$
    • 低 5 位块内地址:00000;
    • 中间 3 位组号:010(组号为 2);
    • 高 20 位 Tag:0000 0000 0100 0000 0000(十六进制 00400H)。
    • 查看 Cache 组 2:组 2 中的两行,一行 Tag 为 00400H 但其有效位为 0;另一行有效位虽为 1 但 Tag 不匹配。因此未命中 Cache。
  18. 虚拟地址 0007C260H 映射 Cache 组号:
    • 物理地址低 12 位与虚拟地址低 12 位完全相同,即 260H = 0010 0110 0000_2。
    • 物理地址低 5 位为块内地址(00000_2),次低 3 位即为 Cache 组号:011_2 = 3。
    • 故该主存块映射到的 Cache 组号为 3。

正确答案: (1) 主存物理地址占 28 位。
(2) TLB 采用全相联映射;TLB 用 SRAM 实现。
(3) Cache 采用 2 路组相联映射;除 Data、Tag 和有效位外,还应有脏位(修改位)和 LRU 替换位;Cache 总容量为 4464 位(或 558 字节);有效位用于指出所在 Cache 行中的信息是否有效。
(4) 对应的物理地址是 0040040H。不在 Cache 中命中,理由是:物理地址对应的 Cache 组号为 2,该组中虽然有一行的 Tag 与物理地址的高 20 位匹配,但该行的有效位为 0,故不命中。虚拟地址 0007C260H 映射到的 Cache 组号是 3。


【真题 3】2020 年 408 第 46 题 · 二级页表地址转换、页表项物理定位与二维数组访存局部性

题目: 某 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. 虚拟地址与物理页表项地址定量计算:
  2. 页面大小 \(= 2^{12}\text{B} = 4\text{KB}\)。
  3. 数组元素占 4B,每行有 1024 个元素,每行占用空间 \(= 1024 \times 4\text{B} = 4096\text{B} = 4\text{KB}\),恰好等于一个页面大小。
  4. 起始虚拟地址为 1080 0000H,对应第 0 行 a[0]。
  5. a[1][2] 前面有完整的 1 行(4096B)加上本行的 2 个元素(\(2 \times 4\text{B} = 8\text{B}\)$ \text{),字节偏移量} $\(= 4096 + 8 = 4104\text{B} = 1008\text{H}\)。
  6. a[1][2] 的虚拟地址 \(= 1080\ 0000\text{H} + 1008\text{H} = \mathbf{1080\ 1008H}\)。
  7. 将 1080 1008H 展开为 32 位二进制: $\(0001\ 0000\ 1000\ 0000\ 0001\ 0000\ 0000\ 1000_2\)$
    • 高 10 位(页目录号):\(0001\ 0000\ 10_2 = \mathbf{042H}\)(十进制 66)。
    • 中间 10 位(页表号):\(00\ 0000\ 0001_2 = \mathbf{001H}\)(十进制 1)。
    • 低 12 位(页内偏移):\(0000\ 0000\ 1008_2 = 008\text{H}\)。
  8. 页目录项物理地址:
    • 页目录起始物理地址为 0020 1000H,每个页目录项占 4B。
    • 物理地址 \(= 0020\ 1000\text{H} + 042\text{H} \times 4 = 0020\ 1000\text{H} + 108\text{H} = \mathbf{0020\ 1108H}\)。
  9. 页表项物理地址:
    • 该页目录项指向的二级页表起始页框号为 00301H,二级页表的起始物理地址为 0030 1000H。
    • 页表项序号为页表号 001H,每个页表项占 4B。
    • 物理地址 \(= 0030\ 1000\text{H} + 001\text{H} \times 4 = \mathbf{0030\ 1004H}\)。
  10. 虚拟与物理连续性判定:
  11. 虚拟地址空间:必须连续。根据高级语言数组的语义以及指针运算规范,数组必须占用连续的虚拟地址空间以支持随机下标寻址。
  12. 物理地址空间:无需连续。分页存储管理的核心优势就是将进程的逻辑地址空间离散地映射到任意分散的物理页框中。
  13. 局部性分析:
  14. 数组按行优先连续存放,每行正好跨越一个页面。
  15. 按行遍历:依次访问当前页面内的各个连续元素,充分利用空间局部性,每访问 1024 个元素仅可能发生一次缺页/Cache 缺失。
  16. 按列遍历:每次访问都跨越整整一行(4KB,跳跃至下一个页面),导致相邻两次访问均跨越不同页面,严重破坏空间局部性,缺页与 Cache 缺失开销极其巨大。因此按行遍历的局部性更好。

正确答案: (1) a[1][2] 的虚拟地址为 1080 1008H;对应的页目录号是 042H,页号是 001H;页目录项的物理地址是 0020 1108H;对应页表项的物理地址是 0030 1004H。
(2) 数组 a 在虚拟地址空间中所占区域必须连续;在物理地址空间中所占区域不必须连续。
(3) 按行遍历的局部性更好。


【真题 4】2023 年 408 第 28 题 · 进程虚拟地址空间特征与容量决定因素

题目: 对于采用虚拟内存管理方式的系统,下列关于进程虚拟地址空间的叙述中,错误的是( )。
A. 每个进程都有自己独立的虚拟地址空间
B. C 语言中 malloc() 函数返回的是虚拟地址
C. 进程对数据段和代码段可以有不同的访问权限
D. 虚拟地址的大小由主存和硬盘的大小决定

【解析】

  • 选项 A 正确:虚拟存储管理为每个进程提供私有的、隔离的虚拟地址空间,各进程虚拟空间互不干扰。
  • 选项 B 正确:在现代分时操作系统中,应用程序处于用户态,无法直接接触物理主存地址,malloc() 动态申请堆空间时返回的是进程虚拟地址空间中的逻辑地址。
  • 选项 C 正确:段页式或页式存储机制通过页表项中的保护位实现精细化权限控制。例如代码段通常设置为“只读/可执行”,数据段设置为“可读/可写/不可执行”(NX/DEP 保护)。
  • 选项 D 错误:虚拟地址空间的大小完全由计算机硬件体系结构(CPU 寻址位数/机器字长)和操作系统规范决定(例如 32 位系统虚拟地址空间固定为 \(2^{32}\text{B} = 4\text{GB}\),64 位系统通常使用 48 位虚拟地址提供 256TB 空间),与物理主存和硬盘的实际物理容量无关。主存和辅存大小仅约束虚拟内存的实际可承载并发负载上限。

正确答案:D


【真题 5】2023 年 408 第 30 题 · 进程间内存共享机制与页表映射特性

题目: 进程 R 和 S 共享数据 data,若 data 在 R 和 S 中所在页的页号分别为 p1 和 p2,两个页所对应的页框号分别为 f1 和 f2,则下列叙述中,正确的是( )。
A. p1 和 p2 一定相等,f1 和 f2 一定相等
B. p1 和 p2 一定相等,f1 和 f2 不一定相等
C. p1 和 p2 不一定相等,f1 和 f2 一定相等
D. p1 和 p2 不一定相等,f1 和 f2 不一定相等

【解析】

  • 虚拟页号(p1, p2):进程 R 和 S 具有各自独立的页表和虚拟地址空间。在链接、加载或动态映射(如 mmap)共享内存时,该共享数据段被映射至各进程虚拟空间中的哪个逻辑位置由各自的地址空间分配器独立决定,因此虚页号 p1 和 p2 不一定相等(当然也可以恰好相等)。
  • 物理页框号(f1, f2):由于数据 data 是被两个进程共享的同一份物理实体,在物理主存中只保留一份副本,两个进程的页表项必然指向同一个物理主存页框,即 f1 和 f2 一定相等。

正确答案:C


【真题 6】2023 年 408 第 43 题 · 请求分页系统缺页分析、Cache 组映射与循环遍历命中率

题目: 已知计算机 M 字长为 32 位,按字节编址,采用请求调页策略的虚拟存储管理方式,虚拟地址为 32 位,页面大小为 4KB;数据 Cache 采用 4 路组相联映射,数据区大小为 8KB,主存块大小为 32B。现有 C 语言程序段如下:

for (i = 0; i < 24; i++)
    for (j = 0; j < 64; j++)
        a[i][j] = 10;
已知二维数组 a 按行优先存放,在虚拟地址空间中分配的起始地址为 0042 2000H,sizeof(int) = 4,假定在 M 上执行上述程序段之前数组 a 不在主存,且在该程序段执行过程中不会发生页面置换。请回答下列问题。 (1) 数组 a 分为几个页面存储?对于数组 a 的访问,会发生几次缺页异常?页故障地址各是什么? (2) 不考虑变量 i 和 j,该程序段的数据访问是否具有时间局部性?为什么? (3) 计算机 M 的虚拟地址(A31~A0)中哪几位用作块内地址?哪几位用作 Cache 组号?a[1][0] 的虚拟地址是多少?其所在主存块对应的 Cache 组号是多少? (4) 数组 a 占用多少主存块?假设上述程序段执行过程中数组 a 的访问不会和其他数据发生 Cache 访问冲突,则数组 a 的 Cache 命中率是多少?若将循环中 i 和 j 的次序按如下方式调换:
for (j = 0; j < 64; j++)
    for (i = 0; i < 24; i++)
        a[i][j] = 10;
则数组 a 的 Cache 命中率又是多少?

【解析】

  1. 页面数量、缺页次数及页故障地址:
  2. 数组总大小 \(= 24 \times 64 \times 4\text{B} = 6144\text{B}\)。
  3. 页面大小 \(= 4\text{KB} = 4096\text{B}\)。
  4. 起始虚拟地址为 0042 2000H,由于低 12 位全为 0,数组起始地址恰与页面边界对齐。
  5. 占用页面范围:
    • 第一页:0042 2000H ~ 0042 2FFFH,容纳 4096B 数据;
    • 第二页:0042 3000H ~ 0042 37FFH,容纳剩余 \(6144 - 4096 = 2048\text{B}\) 数据。
  6. 故数组 a 分布在 2 个页面中。
  7. 由于初始时数组不在主存,执行过程中不发生置换,在首次访问两页的首元素时各触发一次缺页异常,共发生 2 次缺页异常。
  8. 产生异常时的页故障地址即为引发缺页的访问地址:0042 2000H 和 0042 3000H。
  9. 时间局部性分析:
  10. 该程序段对数组 a 的每个元素 a[i][j] 仅执行一次赋值写入操作,后续没有任何重复访问。因此该数据流不具有时间局部性。
  11. Cache 寻址字段划分及特定元素映射计算:
  12. 主存块大小 \(= 32\text{B} = 2^5\text{B}\),故块内地址占低 5 位(A4~A0)。
  13. 数据 Cache 容量为 8KB,4 路组相联,每组容量 \(= 4 \times 32\text{B} = 128\text{B}\)。
  14. Cache 组数 \(= 8\text{KB} / 128\text{B} = 64 = 2^6\) 组,故组号占 6 位。
  15. 在支持虚拟存储的系统中,若采用物理索引 Cache,由于页大小为 4KB(页内地址 12 位),虚拟地址低 12 位(A11~A0)与物理地址低 12 位完全相同。
  16. 块内地址占 A4~A0(5 位),紧随其后的 6 位(A10~A5)用于 Cache 组号。
  17. a[1][0] 虚拟地址: $\(\&a[1][0] = 0042\ 2000\text{H} + 1 \times 64 \times 4\text{B} = 0042\ 2000\text{H} + 100\text{H} = \mathbf{0042\ 2100H}\)$
  18. 将 0042 2100H 低 12 位展开为二进制:\(0001\ 0000\ 0000_2\)。
    • A4~A0(块内地址):00000;
    • A10~A5(组号):\(001000_2 = \mathbf{8}\)。
  19. 主存块数与两类遍历顺序下的 Cache 命中率:
  20. 数组占用主存块数 \(= 6144\text{B} / 32\text{B} = \mathbf{192}\) 块。
  21. 顺序 1(行优先遍历):
    • 每个主存块 32B 容纳 \(32\text{B} / 4\text{B} = 8\) 个 int 元素。
    • 顺序访问时,每个主存块中的第一个元素访问发生冷缺失(Cold Miss),调入 Cache 块后,后续 7 个元素的访问均命中 Cache。
    • 命中率 \(= (8 - 1) / 8 = 7 / 8 = \mathbf{87.5\%}\)。
  22. 顺序 2(列优先遍历,调换循环次序):
    • 数组一行有 64 个元素,占 \(64 \times 4\text{B} / 32\text{B} = 8\) 个主存块。
    • 数组共 24 行,连续 8 行的同列元素相隔 \(8 \times 8 = 64\) 个主存块,正好绕 Cache 组索引一圈(Cache 共 64 组)。
    • 数组总共 192 块,平均映射到 64 个组中,每个组只分配 \(192 / 64 = 3\) 个主存块。
    • 而 Cache 采用 4 路组相联,即每个组能容纳 4 个 Cache 行。
    • 由于 \(3 < 4\),即使采用列优先跳步遍历,数组映射到任意 Cache 组中的块数都小于组相联度,不会发生任何冲突替换(Conflict Miss)。所有调入的块在整个程序执行期间常驻 Cache。
    • 因此总缺失次数依然只有 192 次冷缺失,总命中率仍为 \((192 \times 8 - 192) / (192 \times 8) = 7/8 = \mathbf{87.5\%}\)。

正确答案: (1) 数组 a 分为 2 个页面存储;发生 2 次缺页异常;页故障地址分别是 0042 2000H 和 0042 3000H。
(2) 没有时间局部性。因为每个数组元素在循环中只被访问一次,不存在重复访问。
(3) A4~A0 用作块内地址;A10~A5 用作 Cache 组号;a[1][0] 的虚拟地址是 0042 2100H;所在主存块对应的 Cache 组号是 8。
(4) 数组 a 占用 192 个主存块;行优先方式下的 Cache 命中率是 87.5%;调换次序后的 Cache 命中率依然是 87.5%。


【真题 7】2024 年 408 第 16 题 · 存储器层次结构特性对比与映射策略

题目: 对于页式虚拟存储管理系统,下列关于存储器层次结构的叙述中,错误的是( )。
A. Cache-主存层次的交换单位为主存块,主存-外存层次的交换单位为页
B. Cache-主存层次替换算法由硬件实现,主存-外存层次由软件实现
C. Cache-主存层次可采用回写法写策略,主存-外存层次通常采用回写法
D. Cache-主存层次可采用直接映射,主存-外存层次通常采用直接映射

【解析】

  • 选项 A 正确:Cache-主存层级以固定大小的 Cache 行/主存块为传输粒度;主存-外存层级以虚拟页面为传输粒度。
  • 选项 B 正确:Cache 处于微架构层面,追求纳秒级极速,替换逻辑(如 LRU、伪 LRU)完全由硬件状态机实现;主存-外存层级的缺页开销大,允许操作系统执行较为复杂的置换算法(如 CLOCK 算法家族),由内核软件调度完成。
  • 选项 C 正确:Cache-主存可选择直写或回写;而主存-外存由于外存(磁盘/SSD)写延迟极其高昂,若采用直写会导致每次内存写入都阻塞等待磁盘,因此必须采用回写(Write-Back)。
  • 选项 D 错误:Cache-主存为降低硬件开销可采用直接映射;但主存-外存层次如果采用直接映射,冲突缺失率将大幅上升,导致频繁发生缺页异常与磁盘 I/O,系统吞吐量将发生灾难性雪崩。因此主存-外存层次必须采用全相联映射,由页表记录任意虚页到任意物理页框的映射关系。

正确答案:D


【真题 8】2024 年 408 第 18 题 · MMU 硬件地址转换异常检测范围

题目: 下列事件中,不是在 MMU 地址转换过程检测的是( )。
A. 访问越权
B. Cache 缺失
C. 页面缺失
D. TLB 缺失

【解析】

  • MMU 的核心功能:负责将 CPU 发出的虚拟地址(VA)翻译为物理地址(PA),并在转换过程中利用页表/TLB 中的状态控制位实施硬件检查。
  • 选项 A(访问越权):MMU 比对页表项中的读/写/执行权限位与当前 CPU 运行级别(内核态/用户态),不匹配时检测出访问越权并产生保护异常。
  • 选项 C(页面缺失):MMU 检索页表项时,若发现存在位/有效位为 0,则触发缺页异常。
  • 选项 D(TLB 缺失):MMU 查询 TLB 硬件比较器,若未命中则判定为 TLB 缺失,进而转向遍历主存页表或触发软中断。
  • 选项 B(Cache 缺失):Cache 是利用转换后生成的物理地址去匹配 Cache Tag。Cache 缺失发生在主存数据访问通路中,由 Cache 控制器硬件检测,不属于 MMU 虚实地址转换过程。

正确答案:B


【真题 9】2024 年 408 第 25 题 · 页式存储系统上下文切换中的寄存器更新

题目: 在支持页式存储管理的系统中,进程切换时 OS 要执行( )。
I. 更新 PC(程序计数器)值
II. 更新栈基址寄存器值(ebp)
III. 更新页表基址寄存器值
A. 仅 III
B. 仅 I、II
C. 仅 I、III
D. I、II、III

【解析】

进程上下文切换(Context Switch)要求操作系统保存让出 CPU 进程的上下文,并恢复抢占 CPU 进程的上下文: - I 项正确:PC 记录下一条要执行的指令地址,切换进程必须更新 PC 指向新进程上次中断时的断点地址。 - II 项正确:栈基址寄存器(如 x86 的 EBP/RBP)指示当前函数的栈帧基准,各进程拥有独立的用户栈和内核栈,切换时必须恢复新进程的栈指针与栈基址寄存器。 - III 项正确:每个进程拥有独立的虚拟地址空间和独立的页表。操作系统切换进程时,必须将新进程的页目录物理地址装入页表基址寄存器(如 x86 的 CR3 寄存器),以切换到新进程的虚拟内存映射体系。

正确答案:D


【真题 10】2024 年 408 第 44 题 · 汇编指令寻址、小端存储与页式虚拟内存跨页分析

题目: 对于题中的计算机 M,C 语言程序 P 包含的语句 sum += a[i];,在 M 中对应的指令序列 S 如下:

slli r4, r2, 2  // R[r4] <- R[r2] << 2
add  r4, r3, r4  // R[r4] <- R[r3] + R[r4]
lw   r5, 0(r4)   // R[r5] <- M[R[r4] + 0]
add  r1, r1, r5  // R[r1] <- R[r1] + R[r5]
已知变量 i,sum 和数组 a 都为 int 型,通用寄存器 r1~r5 的编号为 01H~05H。请回答下列问题。 (1) 根据指令序列 S 中每条指令的功能,写出存放数组 a 的首地址、变参 i 和 sum 的通用寄存器编号。 (2) 已知 M 为小端方式,计算机采用页式存储管理方式,页大小为 4KB。若执行到指令序列 S 中第 1 条指令时,i = 5 且 r1 和 r3 的内容分别为 0000 1332H 和 0013 DFF0H。从地址 0013 DFF0H 开始存储单元内容如下表所示。
地址       +0 +1 +2 +3 +4 +5 +6 +7
0013DFF0H  FF FF FF 7C 70 FE FF FF
0013DFF8H  00 00 00 00 3C 02 01 FF
0013E000H  F0 F1 00 00 DC EC FF FF
0013E008H  FF FF 01 02 00 00 01 02
则执行 sum += a[i]; 语句后,a[i] 的地址、a[i] 和 sum 的机器数分别是什么(用十六进制表示)?a[i] 所在页的页号是多少?在此次执行中,数组 a 至少存放在几页中? (3) 指令 slli r4, r2, 2 的机器码是什么(用十六进制表示,格式为 RISC-V 移位格式)?若数组 a 改为 short 类型,则指令序列 S 中 slli 指令的汇编形式应是什么?

【解析】

  1. 寄存器对应关系判定:
  2. slli r4, r2, 2:将 r2 左移 2 位(即乘以 4,对应 sizeof(int) = 4),故 r2 存放变量 i(编号 02H)。
  3. add r4, r3, r4:将 r3 与偏移量 r4 相加计算数组元素地址,故 r3 存放数组 a 的首地址(编号 03H)。
  4. lw r5, 0(r4):从地址 r4 加载 a[i] 到 r5。
  5. add r1, r1, r5:将 a[i] 累加到 r1 中,故 r1 存放变量 sum(编号 01H)。
  6. 地址计算、小端读取与跨页分析:
  7. 首地址 &a[0] = 0013 DFF0H,i = 5。
  8. `&a[5] = 0013 DFF0H + 5 \times 4\text{B} = 0013 DFF0H + 20\text{B} (14\text{H}) = \mathbf{0013 E004H}$。
  9. 查内存数据表,地址 0013 E004H 处的连续 4 字节为:DC EC FF FF。
  10. 系统为小端方式(低位字节存放在低地址端):
    • +0 字节(低地址):DCH 为最低字节;
    • +1 字节:ECH;
    • +2 字节:FFH;
    • +3 字节(高地址):FFH 为最高字节。
    • 拼接得到 a[5] 的机器数为 FFFF ECDCH。
  11. 计算 sum 的新值:
    • 原值 0000 1332H,累加 FFFF ECDCH(其补码真值为 \(-4899\text{D}\))。
    • 补码加法: $\(0000\ 1332\text{H} + \text{FFFF\ ECDCH} = (1)\ 0000\ 000E\text{H}\)$
    • 32 位溢出舍弃最高进位,结果机器数为 0000 000EH。
  12. 页号计算与跨页判定:
    • 页大小为 \(4\text{KB} = 2^{12}\text{B}\),低 12 位为页内偏移量,高 20 位为虚拟页号。
    • a[5] 的地址为 0013 E004H,右移 12 位得页号为 0013EH。
    • 数组首地址为 0013 DFF0H,其页号为 0013DH。
    • 0013DH 与 0013EH 为不同页面,故数组 a 至少存放在 2 个页面中。
  13. 指令机器码及汇编调整:
  14. 若数组类型改为 short,sizeof(short) = 2,对应下标左移 1 位,故汇编指令为 slli r4, r2, 1。

正确答案: (1) a 的首地址存放在 r3(03H);i 存放在 r2(02H);sum 存放在 r1(01H)。
(2) a[i] 的地址为 0013 E004H;a[i] 的机器数为 FFFF ECDCH;sum 的机器数为 0000 000EH;a[i] 所在页的页号是 0013EH;在此次执行中,数组 a 至少存放在 2 页中。
(3) 指令机器码为 0021 2213H。汇编形式应为 slli r4, r2, 1。


【真题 11】2024 年 408 第 45 题 · 大页存储机制、缺页异常处理与页表自映射计算

题目: 某计算机按字节编址,采用页式虚拟存储管理方式,虚拟地址和物理地址的长度均为 32 位,页表项的大小为 4 字节,页大小为 4MB,虚拟地址结构如下:

+-----------------------+---------------------------------------+
|     页号(10 位)     |          页内偏移量(22 位)          |
+-----------------------+---------------------------------------+
进程 P 的页表起始虚拟地址为 B8C0 0000H,被装载到从物理地址 6540 0000H 开始的连续主存空间中。请回答下列问题: (1) 若 CPU 在执行进程 P 的过程中,访问虚拟地址 1234 5678H 时发生了缺页异常,经过缺页异常处理和 MMU 地址转换后得到的物理地址是 BAB4 5678H。在此次缺页异常的处理中,需要为新缺页分配页框并更新相应的页表项,则该页表项的虚拟地址和物理地址分别是什么?该页表项中的页框号更新后的值是什么? (2) 进程 P 的页表所在页的页号是什么?该页对应的页表项的虚拟地址是什么?该页表项中的页框号是多少?

【解析】

  1. 缺页处理与页表项定位推导:
  2. 页大小为 \(4\text{MB} = 2^{22}\text{B}\)$ \text{,页内偏移量占 22 位,虚页号占} $\(32 - 22 = 10\) 位。
  3. 虚拟地址 1234 5678H 转换为二进制: $\(0001\ 0010\ 0011\ 0100\ 0101\ 0110\ 0111\ 1000_2\)$
    • 高 10 位虚页号:\(0001\ 0010\ 00_2 = \mathbf{048H}\)(十进制 72)。
    • 低 22 位页内偏移:34 5678H。
  4. 页表项大小为 4B,虚页号 048H 对应的页表项在页表中的偏移量 \(= 048\text{H} \times 4 = 120\text{H}\)。
  5. 页表项的虚拟地址: $$ \text{VA}_{PTE} = \text{页表起始虚拟地址} + \text{偏移} = \text{B8C0 0000H} + 120\text{H} = \mathbf{B8C0 0120H} $$
  6. 页表项的物理地址: $$ \text{PA}_{PTE} = \text{页表起始物理地址} + \text{偏移} = 6540 0000\text{H} + 120\text{H} = \mathbf{6540 0120H} $$
  7. 物理地址为 BAB4 5678H,其高 10 位为物理页框号: $\(1011\ 1010\ 1011\ 0100\ 0101\ 0110\ 0111\ 1000_2\)$ 高 10 位为 \(10\ 1110\ 1010_2 = \mathbf{2EAH}\)。故更新后的页框号为 2EAH。
  8. 页表自映射与所在页分析:
  9. 进程 P 的页表起始虚拟地址为 B8C0 0000H。
  10. 计算页表所在逻辑页的虚页号:
    • 取 B8C0 0000H 的高 10 位: $\(1011\ 1000\ 1100\ 0000\ \dots_2\)$ 高 10 位为 \(10\ 1110\ 0011_2 = \mathbf{2E3H}\)。故页表所在页的页号为 2E3H。
  11. 该页自身对应的页表项虚拟地址:
    • 该页表项的偏移量 \(= 2\text{E3H} \times 4 = \text{B8CH}\)。
    • 虚拟地址 \(= \text{B8C0\ 0000H} + \text{B8CH} = \mathbf{B8C0\ 0B8CH}\)。
  12. 该页表项中的页框号:
    • 页表存放于物理地址 6540 0000H 开始的主存空间中。
    • 取物理地址 6540 0000H 的高 10 位作为其所在页框号: $\(0110\ 0101\ 0100\ 0000\ \dots_2\)$ 高 10 位为 \(01\ 1001\ 0101_2 = \mathbf{195H}\)。

正确答案: (1) 该页表项的虚拟地址是 B8C0 0120H;物理地址是 6540 0120H;该页表项中的页框号更新后的值是 2EAH。
(2) 进程 P 的页表所在页的页号是 2E3H;该页对应的页表项虚拟地址是 B8C0 0B8CH;该页表项中的页框号是 195H。


【真题 12】2025 年 408 第 23 题 · 进程上下文切换中的内核寄存器状态保持

题目: 在采用页式虚拟存储管理方式的系统中,当发生上下文切换时,下列寄存器中操作系统不需要更新的是( )。
A. 通用寄存器
B. 页表基址寄存器
C. 程序计数器
D. 内核中断向量表基址寄存器

【解析】

  • 进程私有上下文:通用寄存器(保存计算中间值)、程序计数器 PC(指向进程恢复执行的断点)、页表基址寄存器 PTBR/CR3(指向进程私有虚拟空间的页表基址),均属于各进程专有的 CPU 现场,发生进程切换时操作系统必须完整保存与更新。
  • 全局内核上下文:中断向量表基址寄存器(如 x86 的 IDTR)指向操作系统的中断描述符表(IDT)。中断描述符表由操作系统内核在系统引导阶段统一初始化并在物理内存中常驻,服务于所有进程的中断与异常派发,属于全系统共享的内核级数据结构。进程切换在不同用户进程之间进行,操作系统的中断向量表基址无需改变,故不需要更新。

正确答案:D


【真题 13】2025 年 408 第 27 题 · 进程运行所需最少页框数的硬件约束条件

题目: 确定进程运行所需的最少页框数时,要考虑的指标是( )。
A. 代码段长
B. 虚拟地址空间大小
C. 物理地址空间大小
D. 指令系统支持的寻址方式

【解析】

  • 最少页框数(Minimum Frames)的定义:为了保证任意一条机器指令在 CPU 上能够不发生由于缺页导致的死循环颠簸而顺利完成执行,系统分配给进程的驻留集物理页框数不能低于单条指令执行过程中可能并发引用的最大页面数。
  • 决定因素:单条指令执行过程中涉及的页面引用包括:指令自身的读取(可能跨页)、源操作数寻址(间接寻址指针跨页、数据自身跨页)、目的操作数寻址(数据跨页)。这一切完全由处理器体系结构(ISA)的指令格式与寻址方式决定。例如,支持多级间接寻址的复杂指令集(CISC)单条指令可能引用多达 4~6 个页面,则最少页框数必须为 4~6 个。代码段长、虚拟空间与物理内存大小只决定进程分配页框的上限或工作集大小,不约束单条指令运行所需物理页框的下限。

正确答案:D


【真题 14】2025 年 408 第 43 题 · 虚拟分页与 Cache 联合访问性能评估及缺页次数推导

题目: 计算机 M 字长为 32 位,按字节编址,数据 Cache 的数据区大小为 32KB,采用 8 路组相联,主存块大小为 64B,Cache 命中时间为 2 个时钟周期,缺失损失为 200 个时钟周期,采用页式虚拟存储,页大小为 4KB。数组 d 的起始地址为 0180 0020H(VA31~VA0)。现有程序段如下:

int x, d[2048], i;
for (i = 0; i < 2048; i++)
    d[i] = d[i] / x;
(1) 主存地址中的 Cache 组号、块内地址分别占几位?VA 中哪些位可以作为 Cache 索引? (2) d[100] 的 VA 是多少?d[100] 所在主存块中对应的 Cache 组号是多少? (3) 设代码已经在 Cache 中,i, x 已装入内存,但不在 Cache,则 d[0] 在其主存块内的偏移量是多少?执行 for 的过程中,访问 d 的 Cache 缺失率和数组元素的平均访问时间分别是多少?(缺失率用百分比表示,保留两位小数) (4) d 分布在几个页中?若代码已在主存,d 不在主存,则执行 for 的过程中,访问 d 所引起的缺页次数是多少?

【解析】

  1. Cache 结构与虚拟地址切分:
  2. 主存块大小为 \(64\text{B} = 2^6\text{B}\),故块内地址占 6 位。
  3. Cache 容量 32KB,8 路组相联,每组容量 \(= 8 \times 64\text{B} = 512\text{B}\)。
  4. Cache 组数 \(= 32\text{KB} / 512\text{B} = 64 = 2^6\) 组,故 Cache 组号占 6 位。
  5. 页面大小为 \(4\text{KB} = 2^{12}\text{B}\),虚拟地址低 12 位(VA11~VA0)为页内偏移量,在页式管理中与物理地址低 12 位(PA11~PA0)完全一致。
  6. 物理地址中块内地址占 PA5~PA0,Cache 组号占 PA11~PA6。由于低 12 位虚实一致,虚拟地址中的 VA11~VA6 可直接用作 Cache 组索引(即虚索引物理标记 VIPT 机制)。
  7. d[100] 的地址与 Cache 组号:
  8. sizeof(int) = 4,d[100] 的虚拟地址: $\(\&d[100] = 0180\ 0020\text{H} + 100 \times 4\text{B} = 0180\ 0020\text{H} + 400\text{D} (0190\text{H}) = \mathbf{0180\ 01B0H}\)$
  9. 取低 12 位展开为二进制:\(0000\ 0001\ 1011\ 0000_2\)。
    • VA5~VA0(块内偏移):\(110000_2 = 48\);
    • VA11~VA6(组号):\(000110_2 = \mathbf{6}\)。
  10. Cache 缺失率与平均访问时间:
  11. &d[0] = 0180 0020H,块大小为 64B,低 6 位为 0020H(32),故 d[0] 块内偏移量为 32。
  12. 数组总大小 \(= 2048 \times 4\text{B} = 8192\text{B}\)。
  13. 每个 Cache 块 64B。首地址 d[0] 在块内偏移 32B 处,因此:
    • 第 1 个 Cache 块容纳 \(d[0] \sim d[7]\)(8 个元素,共 32B);
    • 中间连续 127 个 Cache 块,每个块完整容纳 16 个元素(\(127 \times 16 = 2032\) 个元素);
    • 最后一个 Cache 块(第 129 块)容纳剩余的 \(2048 - 8 - 2032 = 8\) 个元素(32B)。
    • 数组 d 共占用 129 个 Cache 块。
  14. 语句 d[i] = d[i] / x; 对数组元素执行:1 次读操作 + 1 次写操作,整个循环访问 d 的总次数 \(= 2048 \times 2 = 4096\) 次。
  15. 访问每个 Cache 块时,仅在首次读入该块的第一个元素时产生 1 次冷缺失,随后该块内的所有读写操作均命中 Cache。
  16. Cache 缺失次数 \(= 129\) 次。
  17. Cache 缺失率 \(= 129 / 4096 \approx \mathbf{3.15\%}\)。
  18. 平均访问时间(AMAT): $$ \text{AMAT = 2 + 3.15\% \times 200 = 2 + 6.30 = \mathbf{8.30\text{周期}}} $$ (或按总时钟周期精确计算:\(\frac{129 \times (2 + 200) + (4096 - 129) \times 2}{4096} = \frac{129 \times 200 + 4096 \times 2}{4096} = 2 + \frac{25800}{4096} \approx 8.30\) 周期)
  19. 页面分布与缺页次数:
  20. 页面大小为 4KB(4096B)。
  21. 起始虚拟地址 0180 0020H,页内偏移为 020H(32B)。
  22. 数组占用空间范围为 [0180 0020H, 0180 2020H):
    • 第一页(页号 01800H):从 0020H 到 0FFFH,容纳 \(4096 - 32 = 4064\text{B}\);
    • 第二页(页号 01801H):从 1000H 到 1FFFH,完整容纳 4096B;
    • 第三页(页号 01802H):从 2000H 到 201FH,容纳剩余 32B。
  23. 故数组 d 分布在 3 个页面中。
  24. 初始时 d 不在主存,执行过程中按顺序线性访问,每次跨入新页面均产生一次缺页,故触发的缺页次数为 3 次。

正确答案: (1) Cache 组号占 6 位,块内地址占 6 位;VA 中 VA11~VA6 可以作为 Cache 组索引。
(2) d[100] 的 VA 是 0180 01B0H;对应 Cache 组号是 6。
(3) d[0] 在主存块内的偏移量是 32;Cache 缺失率为 3.15%;数组元素的平均访问时间约为 8.30 个时钟周期。
(4) 数组 d 分布在 3 个页中;访问 d 引起的缺页次数是 3 次。


四、 综合考法拓展

1. 跨层次软硬件端到端联动解题模板

408 综合大题中,最核心的考法是将虚拟分页存储与底层 Cache 体系进行串联。解题时需建立清晰的“地址流转拓扑”:

CPU 虚拟地址 (VA)
   │
   ├─► [MMU/TLB 检索]
   │      ├─ 命中 ──► 获取物理页框号 (PFN)
   │      └─ 缺失 ──► 查页表 (一级/二级) ──► 是否缺页?
   │                    ├─ 有效位=1 ──► 调入 TLB ──► 获取 PFN
   │                    └─ 有效位=0 ──► 缺页中断 ──► 磁盘调页 ──► 更新页表/TLB
   ▼
拼接物理地址 (PA) = PFN + 页内偏移量
   │
   └─► [Cache 控制器检索]
          ├─ 按 PA 组号索引 Cache 组
          ├─ 并行比对该组所有 Cache 行的 Tag 与有效位
          ├─ 命中 ──► 读取/写入数据
          └─ 缺失 ──► 访主存调块 ──► 是否替换? (脏位=1写回主存) ──► 写入 Cache
  • 定长不变量原则:页内偏移位数由页大小决定;无论虚拟地址还是物理地址,低 \(p\)$ \text{位(页内偏移)数值完全一致。若 Cache 组号与块内偏移之和不超过} $\(p\) 位,则虚拟地址对应低位可直接用于 Cache 组索引(VIPT 机制,如 2025#43)。

2. 二维数组访存局部性与缺失率综合推导模型

针对类似 a[M][N] 的嵌套循环访问大题,求解步骤标准化如下: 1. 确定单元素尺寸与空间分布:计算每行字节数,判定一行是否跨页、是否跨 Cache 块。 2. 考察遍历顺序与存储顺序的一致性: - 行优先存储 + 行遍历:空间局部性极佳。Cache 缺失主要为冷缺失,缺失率理论值为 $$ \text{1 / (\text{块大小} / \text{元素大小})} $$。 - 行优先存储 + 列遍历:若单行容量超过 Cache 映射总容量,相邻两次访存将导致严重的颠簸性冲突缺失;若每列元素总数未超过组相联度,则可能避免冲突缺失(如 2023#43 变式)。 3. 读写访存次数判定:辨析指令语义,赋值语句 a[i][j] = a[i][j] + c 包含 1 次读 + 1 次写(共 2 次访存),计算缺失率时分母必须按实际访存总次数计算。

3. 页表自映射与逆向物理定位策略

针对 2024#45 题所展现的高级页表考法,掌握页表自映射(Self-referencing Page Table)原理: - 页表本身也是存储在操作系统虚拟内存中的一段数据。 - 若页表首虚拟地址为 \(V_{base}\)$ \text{,则虚页号为} $\(VPN\) 的页表项虚拟地址必为: $\(VA_{PTE} = V_{base} + VPN \times \text{PTE\_Size}\)$ - 若页表在物理主存中连续分配且基址为 \(P_{base}\),则其物理地址必为: $\(PA_{PTE} = P_{base} + VPN \times \text{PTE\_Size}\)$


五、 考点速记清单

1. 核心要点速记

  • 虚拟地址大小由机器寻址字长决定,与主存、外存容量无关。
  • 进程共享数据时,物理页框号一定相同,虚拟页号不一定相同。
  • 进程运行所需的最少页框数由计算机体系结构指令寻址方式决定。
  • 进程上下文切换时,必须更新 PC、通用寄存器、栈基址寄存器(EBP)与页表基址寄存器(CR3/PTBR);内核中断向量表基址(IDTR)不更新。
  • 缺页异常属于故障(Fault),异常处理结束后重新执行发生缺页的原指令。
  • 存储层次中,主存-外存层次必须采用全相联映射和回写(Write-Back)策略。

2. 计算公式汇总

  • 页内偏移位数:$$ \text{p = \log_2(\text{页大小})} $$
  • 虚拟页号位数:$$ \text{k = \text{虚拟地址位数} - p} $$
  • 物理页框号位数:$$ \text{m = \text{物理地址位数} - p} $$
  • 单级页表总大小:$$ \text{2^k \times \text{PTE大小}} $$
  • Cache 组数:$$ \text{Cache容量} / (\text{组相联度} \times \text{块大小}) $$
  • Cache 组号位数:$$ \text{g = \log_2(\text{Cache组数})} $$
  • 有效访存时间(含 TLB):\(EAT = t_{tlb} + \alpha \cdot t_m + (1 - \alpha) \cdot (n \cdot t_m + t_m)\)

3. 命题避坑指南

  • 陷阱 1:混淆 TLB 缺失与缺页异常。TLB 缺失不等于缺页。若页表项在主存中,只需将页表项重新装入 TLB 即可,不产生缺页中断;只有当页表项指示页面不在物理内存(有效位为 0)时,才触发缺页异常。
  • 陷阱 2:读写访存计数漏算。在计算 Cache 缺失率时,注意语句 d[i] = d[i] / x; 实际上对数组元素执行了两次内存访问(一次读取,一次写回)。计算缺失率的分母是总访存次数而非元素个数。
  • 陷阱 3:列优先遍历 Cache 命中率误判。列优先不一定会导致命中率下降。当整个数组所占用的主存块数映射到同一 Cache 组的最大数量不超过组相联路数时,不会发生冲突替换,其命中率与行优先完全一致。
  • 陷阱 4:主存块号与物理地址的高低位对应。主存块号是由物理地址的高位(去掉块内偏移后的剩余位)构成,在计算 Cache 组号时,组号取自主存块号的低位部分,Tag 取自主存块号的高位部分。

4. 解题核心口诀

虚实转换偏移等,高位寻页低寻位;
查表首看有效位,零为缺页故障归;
进程切换换根页,中断向量稳如雷;
换入换出全相联,磁盘低速必回写。