X-1 虚拟存储访问全过程（页表 → TLB → Cache → 主存 → 缺页）

这一部分为什么存在？

程序员希望看到的内存是“又大又快又便宜”的，但真实硬件三者不可兼得：SRAM 快而贵、DRAM 容量适中而慢于 CPU、磁盘容量大而极慢。虚拟存储系统就是对这对矛盾的总回答：

• 容量矛盾：程序地址空间（如 $2^{32}$ B）远大于物理内存 → 用磁盘当“后备仓库”，只把正在用的页面放内存（虚拟内存）。
• 速度矛盾：虚拟化引入了地址转换开销（每次访存都要查页表），如果照字面执行，每条访存指令至少变成两次访存 → 用 TLB 缓存地址转换结果；取到物理地址后主存仍慢于 CPU → 用 Cache 缓存数据本身。
• 没有这套机制会怎样：要么程序大小被物理内存锁死，要么每条指令的访存开销翻倍甚至（在缺页时）放大百万倍，多道程序无法实用。

一句话：页表负责“映射是否正确”，TLB 负责“映射是否够快”，Cache 负责“数据是否够快”，缺页机制负责“容量不够时怎么办”。 四者是同一条访存链上的四个检查站。

---

flowchart TD
    A["虚拟地址<br/>= 虚页号 | 页内偏移"] --> B{"TLB 命中？"}
    B -- "命中" --> C["得页框号"]
    B -- "未命中" --> D["查内存中的页表<br/>（多级页表则逐级查）"]
    D --> E{"有效位 = 1？"}
    E -- "否（页不在内存）" --> F["缺页异常<br/>→ OS 缺页处理：磁盘 I/O 调入<br/>→ 重新执行该指令"]
    E -- "是" --> C
    C --> G["物理地址<br/>= 页框号 | 页内偏移"]
    G --> H{"Cache 命中？"}
    H -- "命中" --> I["直接读/写 Cache"]
    H -- "未命中" --> J["访问主存，调入 Cache 块"]

必须掌握的概念及其关系：

关键派生概念：

• 有效位（存在位）：页表项中标记该页是否在内存。TLB 中的项必然来自有效位为 1 的页表项 → “TLB 命中但缺页”不可能发生（2010 年 17 题，答案 D）。
• 多级页表：页表本身太大且必须连续存放的问题 → 把页表再分页。32 位系统典型为 10+10+12 结构：页目录号 | 页表索引 | 页内偏移。
• 页表基址寄存器（PTBR）：存放当前进程一级页表（页目录）的起始物理地址（2021 年 29 题），进程切换时由 OS 更新，并导致 TLB 全局失效（与 X-5 连接）。
• 访问位 A / 修改位 M：为置换算法服务，改进型 Clock 按 (A, M) 四类淘汰（2016 年 26 题）。
• 驻留集 vs 工作集：分配给进程的页框集合 vs 进程实际正在用的页面集合；工作集 > 驻留集 → 抖动（2016 年 29 题、2011 年 29 题）。

来源：复习资料 P2 第 4 节（三级访问链）、P3 第 7 节（内存管理）；王道 2027 操作系统 内存管理章；王道 2027 计组 存储系统章。

---

1. 地址转换的基本动作

设页大小 $L = 2^k$ 字节，逻辑地址 $A$：

$\text{页号 } P = A \gg k,\qquad \text{页内偏移 } d = A \mathbin{\&} (L-1)$

查页表/TLB 得页框号 $f$ 后：

$\text{物理地址} = f \times L + d = (f \ll k) \mathbin{|} d$

注意页内偏移在虚实地址中完全相同，转换只发生在高位（页号 → 页框号）。

来源：复习资料 P3 §7.1。

2. 一次访存的完整流程（六步模板）

1. 拆分虚拟地址为（虚页号，页内偏移）；
2. 查 TLB：命中 → 直接得页框号，跳到第 5 步；
3. TLB 未命中 → 查内存页表（$n$ 级页表则查 $n$ 次内存）；
4. 页表项有效位 = 0 → 缺页异常：陷入内核，OS 从磁盘调入页面（可能先淘汰一页），修改页表并更新 TLB，返回重新执行该指令（不是下一条——2019 年 14 题 D 选项即错在“下一条”）；
5. 拼接物理地址；
6. 用物理地址查 Cache：命中 → 完成；未命中 → 访主存取块填入 Cache。

3. 访存次数核算（大题核心得分点）

两个高频陷阱：

• TLB 和 Cache 的访问时间不计入“访存次数”（题目若问“访问主存次数”，只有查内存页表和读主存数据才算）。
• 取指令、取数据、写回可能各触发一次完整链条，按指令语义逐次数（如 2015 年 16 题 add xaddr, 3：取指 1 次 + 取 x 1 次 + 写回因 Cache 直写再 1 次，TLB 命中时共 3 次）。

4. 有效（平均）访存时间 EAT

设 TLB 命中率 $\alpha$、TLB 访问时间 $t$、内存访问时间 $m$、缺页率 $p$、缺页处理时间 $D$（含磁盘）：

$\text{EAT} = (1-p)\times\big[\alpha(t+m) + (1-\alpha)(t+2m)\big] + p \times D$

影响 EAT 的因素：缺页率、磁盘读写时间、内存访问时间、缺页处理程序的 CPU 时间——四项全部相关（2020 年 28 题）。

5. 缺页后的置换决策

页面不在内存且驻留集已满 → 必须淘汰一页。置换算法是“用过去/未来信息猜哪页最不再用”：

为什么会出现 Belady 异常（补充理解）：FIFO 只看“进内存早晚”，而该信息与未来使用无关；页框增多时被保留的“老页”可能恰是高频页，新页框反而加速了其后续页面的循环淘汰。LRU/OPT 属栈类算法，小驻留集的页面集合是大驻留集的子集，故数学上不可能出现异常。

来源：复习资料 P3 §7.3–7.4；王道 2027 操作系统 虚拟内存节。

---

TLB vs Cache（最容易被混着考的一对）

易混原因：都是“小而快的 SRAM 缓存，靠局部性工作”。本质区别：一个在地址转换阶段（数据还没找到），一个在数据访问阶段（地址已经确定）；判别线索——题目出现“虚页号/页框号/地址转换”即 TLB，出现“块/行/主存数据”即 Cache。

一级页表 vs 多级页表

分页 vs 分段（本链条的两种“切蛋糕”方式，简述）

分页等长切分、对用户透明、无外部碎片但有页内内部碎片；分段按逻辑单位切分、便于共享保护、有外部碎片。段页式先分段再分页。详细展开见后续 OS-5 模块。

---

本专题在真题中的三种固定形态：

形态一：综合大题——给完整系统参数，走一遍链条

• 2011 年 44 题：虚存 16MB、主存 1MB、页 4KB、直接映射 Cache 8 行 + 四路组相联 TLB，问地址字段划分、物理地址计算、TLB 判定页面是否在内存。
• 2016 年 45 题：虚地址 32 位/物理 24 位、页 8KB、TLB 全相联、Cache 64KB 两路组相联，给出“存储访问过程示意图”问 A~G 各字段位数、TLB 标记存什么、Cache 缺失与缺页谁开销大（缺页大：要磁盘 I/O）。
• 2012 年 43 题：Cache 命中率 + 缺页率 + DMA 周期挪用 + 交叉存储带宽，把整条链延伸到了磁盘（与 X-3 连接）。
• 2024 年 46 题（数组访问缺页次数、页故障地址、取指令是否缺页）：链条在代码级访问序列上的应用。

形态二：地址转换计算（选择/填空式大题小问）

• 2013 年 16 题：全相联 TLB，虚地址 03FFF180H → 物理地址 0153180H（页框 0153H | 偏移 180H）。
• 2009 年 46 题：TLB 初空 + LRU + 驻留集 2，逐地址算访问时间与物理地址（含一次 $10^8$ ns 缺页）。
• 2013/2015/2017/2020 年 46 题系列：10+10+12 二级页表，求页目录号/页表索引表达式、页表项物理地址、“两个虚拟地址共访问几个二级页表”（页目录号相同 → 1 个，2015 年 46 题）。

形态三：概念辨析选择题

• 2010 年 17 题：TLB 命中 + Page 未命中的组合不可能存在。
• 2018 年 44 题：TLB 用 SRAM 实现；改进型 Clock 需要页表项设访问位和修改位。
• 2019 年 14 题：缺页处理完返回发生缺页的指令重新执行。
• 2020 年 15 题：TLB 与 Cache 都由 SRAM 组成（“都由 DRAM 组成”为错误项）。
• 2021 年 29 题：页表基址寄存器存一级页表起始物理地址。

做题触发词：看到“页表 + TLB + Cache 同时出现”立即进入本链条；看到“至少/最多访存几次”先列表格核算；看到“有效位/驻留集/LRU”走缺页分支；看到“页目录号相同”立刻意识到只访问一个二级页表。

来源：真题markdown/2009-2024统考真题.md 对应年份题号；复习资料 P2 §4、§7，P3 §7。

---

• 向前依赖：CO-1 数据表示（地址位数与切分）、CO-3 Cache 三种映射（组相联 TLB 的字段划分与 Cache 同构）、OS-5 分页/分段基本概念、CO-4/OS-0 中断异常机制（缺页是内中断/异常）。
• 向后引出：
  • 缺页要读磁盘 → 文件在磁盘上的位置由文件系统决定（OS-7），磁盘读写用 DMA（CO-7 / X-3）；
  • 置换算法失控 → 抖动 → 工作集模型（OS-6）；
  • 进程切换 → PTBR 更换 → TLB 失效 → 性能问题（X-5）；
  • 写操作经 Cache → 写直达/写回的一致性问题（CO-3，2015 年 16 题已涉及直写）。

---

顺着以下问题自问自答，能完整走通即说明本模块已串联：

1. 为什么程序可以用比物理内存大的地址空间？（虚拟内存 + 磁盘后备）
2. 虚拟地址怎么变成物理地址？（页号查页表得页框号，偏移不变）
3. 页表放在哪里？每次访存都查它有什么后果？（放内存；一次访存变两次）
4. 怎么把地址转换加速回来？（TLB：页表的 Cache）
5. TLB 命中了，数据就一定在内存吗？TLB 未命中呢？（命中必在；未命中要查页表才知道）
6. 拿到物理地址后为什么还要 Cache？（主存仍慢于 CPU，缓存数据本身）
7. 一次访存最少/最多访问主存几次？（0 次；$n$ 级页表未命中 + Cache 未命中 = $n+1$ 次）
8. 页表项有效位为 0 会发生什么？（缺页异常 → 陷入内核）
9. 缺页处理做哪些事？处理后从哪里继续执行？（找页框/必要时淘汰/磁盘读入/改页表和 TLB；重新执行缺页指令）
10. 驻留集满了淘汰哪一页？各算法思想与缺页次数怎么比？（OPT/FIFO/LRU/Clock）
11. 为什么 FIFO 会出现 Belady 异常而 LRU 不会？（栈类算法驻留集包含关系）
12. 缺页太频繁会怎样？系统怎么救？（抖动；撤销部分进程、增大驻留集）
13. 页表太大放不下怎么办？代价是什么？（多级页表；转换多查 $n-1$ 次内存，靠 TLB 补偿）
14. 进程切换对这个链条有什么影响？（换 PTBR、TLB 失效）