虚拟存储器

概念

虚拟存储器（virtual memory）是把「主存当 Cache、把磁盘当主存」的那套机制——它让每个程序都以为自己独占一整块连续、巨大的地址空间，而实际的物理主存可能只有它的几十分之一。

上一章 Cache 解决的是「CPU 与主存」之间的速度差距；这一章解决的是容量问题：程序比内存大怎么办。两者的手法惊人地相似（分块、按需调入、地址映射、替换），所以这一章几乎可以看成「Cache 原理在磁盘层级上的重演」。

        CPU                主存（物理）              磁盘
    ┌────────┐          ┌──────────────┐       ┌────────────┐
    │ 虚拟地址│ ──映射──▶│  页框（物理页） │◀──换入/换出──│   页文件   │
    │  32/64 位│          │  几 GB        │       │  几百 GB   │
    └────────┘          └──────────────┘       └────────────┘
         ↑ 这一层由操作系统 + MMU 共同维护

本章主线：一个虚拟地址，怎么变成物理地址？ 沿途会经过 TLB、页表、（可能缺页），最后才落到主存或 Cache——这条链上的每一步都是考点。

原理

一、术语对照：虚存与 Cache 是同构的

Cache 侧	虚存侧	说明
块 / 行（block/line）	页（page）/ 页框（page frame）	传送单位；页是虚拟的，页框是物理的
主存	磁盘（页文件、交换区）	慢速后备存储
Cache 行号	页框号（PPN，physical page number）	映射到的位置
块内地址	页内偏移（offset）	页内定位，映射前后不变
标记（tag）	虚页号（VPN，virtual page number）	用来核对"这是哪一页"
命中 / 缺失	命中 / 缺页（page fault）	缺页代价高 5~6 个数量级

最关键的一条对齐：

$$\text{页内偏移在地址变换中不参与任何计算，原样复制}$$

因为一块（页）整块搬动，内部相对位置永远不会变。只有页号被翻译，偏移是"跟着走"的。

二、页表：虚拟页号到物理页框号的映射表

页表（page table）是一个数组，下标是虚页号，内容是页表项（PTE，page table entry）：

$$\text{PTE}=\underset{\text{映射结果}}{\underbrace{\text{物理页框号 PPN}}}+\underset{\text{在不在内存}}{\underbrace{\text{有效位 V}}}+\underset{\text{要不要写回}}{\underbrace{\text{修改位 D（脏位）}}}+\underset{\text{给替换算法用}}{\underbrace{\text{访问位 A}}}+\underset{\text{读/写/执行}}{\underbrace{\text{保护位}}}$$

• 有效位 = 0 表示该页不在主存（在磁盘上）→ 触发缺页。
• 页表本身也存在主存里，所以「查页表」本身就是一次访存。这就是为什么需要 TLB（见第四节）。

三、单级页表的问题与两级页表的由来

以 32 位虚地址、4 KB 页为例：

$$\text{页内偏移}={\log }_{2}4096=12\text{位},\text{虚页号}=32-12=20\text{位}$$

虚页号 20 位 → 页表有 $2^{20}=1048576$ 个表项。每个表项 4 B：

$$2^{20}\times 4\text{B}=4\text{MB}$$

每个进程都要 4 MB 页表，还必须连续存放——这是不可接受的。两条改革：

1. 多级页表：把页表本身也分页，只给用到的部分分配。20 位虚页号切成 10 + 10，一级页表（页目录）正好 1 页（4 KB），二级页表按需分配。
2. TLB：把最近用到的「虚页号 → 页框号」映射放进一个极小的高速相联存储器，避免每次访存都要查页表。

一级页号(10) 二级页号(10) 页内偏移(12)
└────┬────┘└────┬────┘└───┬───┘
     │          │         └── 不变，直接拼接
     │          └── 查二级页表 -> 得到页框号
     └── 查一级页表（页目录）-> 得到二级页表的基址

四、TLB：快表

TLB（translation lookaside buffer，快表）是一个容量极小、速度极快、全相联的硬件表，缓存最近用过的页表项。

项	值
相联度	全相联（Cam 实现，几路到几百路）
容量	通常 16 ~ 256 项（远小于页表）
索引字段	没有（全相联）
内容	虚页号（标记）+ 物理页框号 + 有效/脏/保护位
命中代价	1 个时钟内完成，与 CPU 同速

TLB 命中的判定：把虚页号与所有表项并行比较，有一项相等且有效位为 1 即命中。这也是"全相联"概念的第二个重要落点（第一个是第 12 篇提到的早期小 Cache）。

TLB 与 Cache 的分工别混：

• TLB 缓存的是"地址映射"（虚页号 → 页框号），不缓存数据。
• Cache 缓存的是"数据"，不负责地址翻译。
• 两者都可能在一次访存中被访问，顺序见第六节。

五、缺页处理

访问一个虚页，TLB 未命中 → 查页表 → 有效位 = 0 → 缺页。处理流程：

① MMU 发现有效位 = 0，产生缺页异常（page fault），转 OS
② OS 查页表项：该页在磁盘的哪个位置
③ 在主存里找空闲页框；没有空闲 -> 用替换算法挑一个牺牲页
④ 若牺牲页脏位 = 1 -> 先写回磁盘（这是虚存必须用写回法的原因）
⑤ 从磁盘把目标页读入该页框（这一阶段 CPU 可以调度去跑别的进程）
⑥ 改写页表项：页框号 = 新位置，有效位 = 1；若刚写过则脏位置 1
⑦ 返回并重新执行那条引起缺页的指令

注意第 ⑦ 步：缺页是故障（fault）而非中断——处理完后重新执行那条指令，而不是执行下一条。这一分类在第 33 篇异常机制里会正式讲。

六、一次访存的完整链路

虚拟地址
  │
  ├─▶ TLB 查（全相联，1 个时钟）
  │      ├─ 命中 ──▶ 得到物理页框号 ──┐
  │      └─ 未命中 ─▶ 查页表（访存！）─┤
  │                    ├─ 有效 ──▶ 得到页框号，并填入 TLB
  │                    └─ 无效 ──▶ 缺页，OS 介入，处理后再来
  │                                    │
  └────────────────────────────────────┴──▶ 物理地址 = 页框号 ‖ 页内偏移
                                              │
                                              └─▶ 再查 Cache（第 12 篇）──▶ 数据

访存次数统计（重要）：

情形	查映射	取数据	合计访存
TLB 命中	0	1	1
TLB 未命中 + 单级页表	1	1	2
TLB 未命中 + 两级页表	2	1	3
缺页	2 + 磁盘 I/O	1	3 + 盘

再叠一层 Cache：若物理地址查 Cache 命中，则上表的「取数据 1 次」也被 Cache 挡掉（变成 1 次 Cache 访问 + 0 次主存）。

七、写策略必须选写回

层级	写策略	理由
Cache	写回或写直达都有	主存与 Cache 都在内存里，写直达只是慢
虚存	只能写回	磁盘比主存慢 5~6 个数量级，每次写都打磁盘不可想象

写位（脏位 / 修改位）在虚存里是必需品，不是可选项。替换一个干净页可以直接丢弃，替换脏页必须先写回。

八、虚存与 Cache 的配合（考点延伸）

物理地址查 Cache 时，Cache 的标记用物理页框号还是虚页号？三种设计：

方案	全称	做法	优缺点
PIPT	physically indexed, physically tagged	先翻译地址，再查 Cache	正确性好，但翻译在关键路径上，慢
VIPT	virtually indexed, physically tagged	用虚地址低位取索引，同时用物理页框号比对标记	现代主流：翻译与 Cache 索引并行
VIVT	virtually indexed, virtually tagged	整个虚地址查 Cache	最快，但进程切换要清 Cache（同一虚地址不同进程含义不同）

VIPT 能成立的前提：页内偏移位数 ≥ Cache 索引位数。此时索引只用到虚地址的低位，而低位在地址变换中不变，所以可以提前开始索引。

示例

例 1：页与页表的规模

32 位虚地址、页大小 4 KB、页表项 4 B、物理地址 30 位。求：页内偏移位数、虚页号位数、物理页框号位数、单级页表项数与总大小。

完整计算过程：

第一步，页内偏移（由页大小决定）：

$${\log }_2(4\times 1024)={\log }_{2}4096=12\text{位}$$

第二步，虚页号位数：

$$32-12=20\text{位}$$

第三步，物理页框号位数：

$$30-12=18\text{位}$$

第四步，单级页表项数（一项对应一个虚页）：

$$2^{20}=1048576\text{项}$$

第五步，单级页表总大小：

$$1048576\times 4\text{B}=4194304\text{B}=4096\text{KB}=4\text{MB}$$

结论：每个进程需要 4 MB 连续页表，而且其中绝大多数表项根本没被用到（一个程序的活动页只有几百页）。这就是必须引入多级页表的直接原因。

例 2：两级页表的地址划分与容量

仍用例 1 的参数，改为两级页表。求地址划分与各级页表容量。

完整计算过程：

第一步，切分虚页号（20 位）：取 10 + 10，正好让一级页表占一整页：

$$\text{一级页号}=10\text{位},\text{二级页号}=10\text{位}$$

第二步，一级页表（页目录）容量：

$$2^{10}\times 4\text{B}=4096\text{B}=4\text{KB}$$

正好一页——这是「10 + 10」这个切法的意义所在：页目录本身可以被当成一页来换入换出。

第三步，单张二级页表容量：

$$2^{10}\times 4\text{B}=4096\text{B}=4\text{KB}$$

第四步，二级页表最多有多少张：

$$2^{10}=1024\text{张}$$

第五步，"全部分配"时的总容量（用于对比上限）：

$$1024\times 4\text{KB}=4096\text{KB}=4\text{MB}$$

结论对照表：

方案	表项数	总容量	是否连续	按需分配后实际占用
单级页表	$2^{20}$	4 MB	必须连续	还是 4 MB
两级页表	1 + $2^{10}$ 张	最多 4 MB + 4 KB	一级必须连续，二级各 4 KB	只给用到的那几张

关键体会：两级页表并没有减少表项总数（上限还是 4 MB+4KB），它减少的是必须常驻的部分——只有 4 KB 的一级页表必须常驻，1024 张二级页表里只需要存在被访问过的那几张。用「多一层间接」换「按需分配」。

例 3：TLB + 页表的平均访问时间

参数：TLB 访问时间 1 ns；主存访问时间 100 ns；TLB 命中率 $a=98\mathrm{\%}$；缺页率 $c={10}^{-5}$；缺页处理时间 ${10}^6$ ns（1 ms）。采用两级页表。求平均访问时间 EAT。

完整计算过程：

第一步，确定"TLB 命中"时的一次访存总代价：

$$T_{\text{TLB命中}}=\underset{\text{查 TLB}}{\underbrace{1}}+\underset{\text{取数据}}{\underbrace{100}}=101\text{ns}$$

第二步，TLB 未命中时，多付出的代价是"两次额外的访存"（查一级页表、查二级页表，各 100 ns）：

$${\mathrm{\Delta }}_{\text{未命中}}=2\times 100=200\text{ns}$$

第三步，缺页时额外付出的代价（只算一次，因为两级页表已经查过）：

$$T_{\text{缺页}}={10}^6\text{ns}$$

第四步，三项加权相加（标准 EAT 公式）：

$$\text{EAT}=\underset{T_{\text{TLB命中}}}{\underbrace{101}}+\underset{\text{TLB 未命中损失}}{\underbrace{(1-a)\times 200}}+\underset{\text{缺页损失}}{\underbrace{c\times {10}^6}}$$

第五步，代入 $a=0.98$、$c={10}^{-5}$：

$$\text{EAT}=101+0.02\times 200+{10}^{-5}\times {10}^6=101+4+10=115\text{ns}$$

对照表（换不同参数）：

$a$	$c$	TLB 层	未命中损失	缺页损失	EAT
98%	${10}^{-5}$	101	4	10	115 ns
90%	${10}^{-5}$	101	20	10	131 ns
95%	${10}^{-5}$	101	10	10	121 ns
98%	${10}^{-6}$	101	4	1	106 ns
98%	0	101	4	0	105 ns

结论与解读：

• 缺页率从 ${10}^{-5}$ 降到 ${10}^{-6}$，EAT 从 115 降到 106 ns。缺页率每降一个数量级，EAT 明显改善——但注意此时它只占 10 ns / 115 ns ≈ 8.7%，不像很多人想象的那样"缺页一定主导一切"。缺页主导一切是在 $c$ 达到 ${10}^{-3}$ 量级时（那时缺页项 = 1000 ns，比 TLB 层本身还大 10 倍）。
• TLB 命中率的作用相对温和：从 90% 提到 98%，EAT 只从 131 降到 115。因为未命中的代价只有 200 ns，而缺页是 ${10}^6$ ns，差 5000 倍。
• 这与第 12 篇 Cache 的结论完全同构：平均时间被最慢的那一项主导，而最慢的那一项出现的概率最低。解题时三项都要写出来，只算一项必错。

⚠️ 口径提示：本题把"TLB 未命中的额外代价"记为 $2\times 100$（两级页表各一次访存）。若题目说"页表项在主存中，TLB 未命中需要访问主存中的页表一次"，那就改成 $1\times 100$，答案变成 $101+0.02\times 100+10=113$ ns。看清题目给的是单级还是两级页表。

例 4：一次地址变换的逐步演示

仍用例 1/例 2 的配置。虚拟地址 0x00403ABC 需要变换。其一级页号 = 1、二级页号 = 3、页内偏移 = 0xABC。假设：一级页表第 1 项指向的二级页表基址为 0x00002000；该二级页表第 3 项的内容为 0x0000C007（高 20 位是标志，低 12 位是页框号，此处页框号 = 0xC）。求物理地址。

完整计算过程：

第一步，拆虚拟地址 0x00403ABC：

0x00403ABC = 0000 0000 0100 0000 0011 1010 1011 1100
             └── 一级 ──┘└── 二级 ──┘└─── 偏移 ───┘
              10 位        10 位         12 位

一级页号 = 0x00403ABC >> 22 = 1
二级页号 = (0x00403ABC >> 12) & 0x3FF = 3
页内偏移 = 0x00403ABC & 0xFFF = 0xABC

第二步，查一级页表第 1 项 → 得到二级页表基址 0x00002000。

第三步，二级页表的表项地址 = 基址 + 二级页号 × 4：

$$0\text{x}00002000+3\times 4=0\text{x}00002000+0\text{x}0\text{C}=0\text{x}0000200\text{C}$$

第四步，读该地址，得到页表项 0x0000C007。拆开：

$$\text{低 12 位}=0\text{x}007\Rightarrow \text{标志位（有效=1、脏=1、访问=1）},\text{页框号}=0\text{xC}$$

第五步，拼物理地址（页内偏移原样复制）：

$$\text{物理地址}=\text{页框号}\ll 12\mid \text{页内偏移}=0\text{xC}000\mid 0\text{xABC}=\mathbf{0}\text{x}\mathbf{0}\text{CABC}$$

结论：虚拟地址 0x00403ABC → 物理地址 0x0CABC。

访存次数：本例中 TLB 假设未命中，所以是「查一级页表 1 次 + 查二级页表 1 次 + 取数据 1 次 = 3 次访存」。这就是例 3 里那个 $2\times 100$ 的来源。

注意偏移没变：0xABC 从虚地址原封不动搬到了物理地址末尾——这是"页内偏移不参与变换"的直接体现，也是检查答案对不对的最快方法。

例 5：Python——两级页表 + TLB 的地址变换模拟

def translate(va, page_dir, tables, tlb, log=print):
    """32 位 VA / 4KB 页 / 两级页表(10+10+12)。page_dir: {一级号: 二级表号}"""
    l1 = (va >> 22) & 0x3FF
    l2 = (va >> 12) & 0x3FF
    off = va & 0xFFF
    vpn = va >> 12                       # 完整虚页号 = 一级 ‖ 二级

    if vpn in tlb:                       # ---- TLB 命中：0 次额外访存
        ppn, src, extra = tlb[vpn], 'TLB 命中', 0
    else:                                # ---- 未命中：查一级 + 二级 = 2 次访存
        extra, src, ppn = 2, 'TLB 未命中, 查两级页表', None
        if l1 not in page_dir:
            src = '缺页: 二级页表不存在'
        else:
            tno = page_dir[l1]
            if tno not in tables or l2 not in tables[tno]:
                src = '缺页: 页表项无效'
            elif not (tables[tno][l2] & 1):      # 有效位 = 0
                src = '缺页: 有效位=0'
            else:
                ppn = tables[tno][l2] >> 12
                tlb[vpn] = ppn                   # 填入 TLB

    if ppn is None:                      # ---- 缺页: 没有物理地址
        log('  VA 0x%08X -> L1=%d L2=%d off=0x%03X  [%s]  (需 OS 介入)'
            % (va, l1, l2, off, src))
        return None, src, extra

    pa = (ppn << 12) | off
    log('  VA 0x%08X -> L1=%d L2=%d off=0x%03X  [%s]  -> PA 0x%05X'
        % (va, l1, l2, off, src, pa))
    return pa, src, extra

# ---- 构造例 4 的场景 ----
page_dir = {1: 5}                        # 一级表第 1 项 -> 二级表 #5
tables = {5: {3: (0xC << 12) | 0b111}}   # 二级表 #5 第 3 项 -> 页框 0xC, 有效|脏|访问
tlb = {}
print('第一次访问(必未命中):')
translate(0x00403ABC, page_dir, tables, tlb)
print('第二次访问同一个页内地址(应 TLB 命中):')
translate(0x00403AB0, page_dir, tables, tlb)
print('访问不存在的二级页表项:')
translate(0x00800000, page_dir, tables, tlb)

# ---- 例 1/2 规模核算 ----
import math
VA, PG, PTE = 32, 4096, 4
off = int(math.log2(PG)); vpn = VA - off
print('\n页内 %d 位, 虚页号 %d 位, 单级页表项 %d, 大小 %d MB'
      % (off, vpn, 2 ** vpn, 2 ** vpn * PTE // 1024 // 1024))
l1 = vpn // 2; l2 = vpn - l1
print('两级: 一级 %d 位(表 %d B) 二级 %d 位(单张 %d B, 最多 %d 张)'
      % (l1, 2 ** l1 * PTE, l2, 2 ** l2 * PTE, 2 ** l1))

# ---- 例 3 EAT ----
ttlb, tmem, tpf = 1, 100, 1e6
for a, c in [(0.98, 1e-5), (0.90, 1e-5), (0.98, 1e-6)]:
    print('a=%.2f c=%g -> EAT = %g ns' % (a, c, 101 + (1 - a) * 200 + c * tpf))

python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

输出对照：

第一次访问(必未命中):
  VA 0x00403ABC -> L1=1 L2=3 off=0xABC  [TLB 未命中, 查两级页表]  -> PA 0x0CABC
第二次访问同一个页内地址(应 TLB 命中):
  VA 0x00403AB0 -> L1=1 L2=3 off=0xAB0  [TLB 命中]  -> PA 0x0CAB0
访问不存在的二级页表项:
  VA 0x00800000 -> L1=2 L2=0 off=0x000  [缺页: 二级页表不存在]  (需 OS 介入)

第一次的物理地址 0x0CABC 与例 4 手算一致；第二次访问同页内的 0x00403AB0 显示 TLB 命中（虚页号相同，只有页内偏移不同——这正好说明 TLB 是以"页"为粒度的）；第三次 0x00800000 的一级页号是 2，页目录里没有这一项 → 缺页。规模核算输出 4 MB / 一级 4 KB / 二级 1024 张；EAT 为 115、131、106 ns，与例 3 一致。

考点

考点

1. 必背公式

• 页内偏移位数 $={\log }_2(\text{页大小})$；虚页号位数 $=$ 虚地址位数 $-$ 页内偏移位数
• 单级页表项数 $=2^{\text{虚页号位数}}$；页表大小 $=$ 项数 $\times$ 页表项字节数
• 两级页表：一级位数 $+$ 二级位数 $=$ 虚页号位数；一级页表占满一页是最优切法
• 访存次数：TLB 命中 1 次；未命中 + 单级页表 2 次；未命中 + 两级页表 3 次
• $\text{EAT}=T_{\text{TLB命中}}+(1-a)\times (\text{未命中额外访存}\times T_m)+c\times T_{\text{缺页}}$

2. 高频陷阱

• 页内偏移在变换中不变。任何让你"把偏移也翻译一遍"的解法都是错的，也是最快的自检方法。
• 页表本身也要占主存，查页表是一次访存。TLB 存在的全部理由就是省掉这 1~2 次访存。
• 虚存只能写回，不能用写直达。因为写直达要打磁盘。脏位（修改位）是必需品。
• TLB 是全相联、无索引字段。这是"全相联"概念除小 Cache 外的第二个落点，常以"TLB 用什么映射"来考。
• TLB 是按"页"缓存的：同一页内的不同地址命中情况完全相同。例 5 的第二次访问就演示了这一点。
• TLB 未命中的额外代价取决于页表级数：题目说两级页表就是 2 次额外访存，不是固定值。例 3 给了两种口径。
• 缺页是"故障"不是"中断"：处理完后重新执行出错的那条指令，不是执行下一条。第 33 篇会正式区分。
• "虚拟内存变大"不等于"能装更大的程序"：可寻址空间由地址位数决定（32 位 = 4 GB），而能同时驻留的由物理内存决定，两者是两件事。
• 多级页表不减少表项总数，只减少"必须常驻"的部分。问"两级页表比单级省了多少空间"时，答案是"上限差不多，但实际占用按需分配"。
• 进程切换时 TLB 要处理：TLB 里是"这个进程的"映射，换进程要么清空，要么给 TLB 加 ASID（地址空间标识）。这属于 OS 结合考点。
• Cache 与虚存的映射关系别搞反：Cache 的标记可以是物理页框号（PIPT/VIPT）。VIPT 能成立的前提是页内偏移位数 ≥ Cache 索引位数。

3. 解题模板（"给配置求页表规模"）

① 页内偏移 = log2(页大小)
② 虚页号 = 虚地址位数 - 页内偏移
②' 物理页框号 = 物理地址位数 - 页内偏移
③ 单级页表项数 = 2^虚页号位数 ; 字节数 = 项数 x 每项字节
④ 两级: 一级位 + 二级位 = 虚页号位数, 建议一级表正好占 1 页
⑤ 访存次数: TLB 命中 1 / 单级未命中 2 / 两级未命中 3
⑥ 缺页额外代价 = 查页表次数 + 磁盘 I/O

4. 与本篇相邻考点的接口

• 第 12 篇 Cache 与本篇是"同一套思想的两级重演"：对照表要能默写。高频综合题常把「虚地址 → 物理地址（查 TLB + 页表，可能缺页）→ 物理地址查 Cache（可能缺失）→ 主存」串成一条链，每一段都要算访存次数与时间。
• 第 33 篇 异常与中断：缺页异常的触发、EPC 保存的是出错指令地址、返回后重执行。
• 第 11 篇 主存储器：页框分配与内存管理的物理基础。
• 与操作系统的交叉是必考：页面置换算法（LRU/Clock/OPT）、工作集、抖动都在 OS 篇展开，但地址变换与 TLB 的题一定出自组成原理。

小结

• 虚拟存储器 = 把磁盘当主存、把主存当 Cache；它靠"分页 + 按需调入 + 地址映射 + 替换"解决容量问题。
• 页内偏移在地址变换中永不改变，变的只有页号；这是全篇最重要的一句话。
• 页表把虚页号映射成物理页框号，页表项还要带有效位、脏位、访问位与保护位。
• 单级页表太大（本题 4 MB）且必须连续，于是有了多级页表（按需分配，一级表正好一页）与 TLB（省掉查页表的访存）。
• 访存次数：TLB 命中 1 次、单级页表未命中 2 次、两级页表未命中 3 次。这是最高频的一个小计算题。
• $\text{EAT}=101+(1-a)\times 200+c\times {10}^6$：三项都要写，缺页项常常不是主导项。
• 虚存只能用写回，脏位必需；缺页是故障，返回后要重新执行那条指令。

下一篇：指令格式与寻址方式