基本分页存储管理：从页表到地址变换机构

---

引言

上篇文章留给我们的难题是：连续分配中，外部碎片无解——除非我们不再要求"连续"。分页（Paging）就是那个打破"连续分配"前提的方案。它把物理内存切成等大的"页框"（Frame），把进程的逻辑地址空间切成同样大小的"页"（Page），然后允许任意一页装入任意一个空闲的页框。这块拼图不需要是相邻的——物理上可以散落在内存各处，逻辑上页表帮你把它们连起来。

这个设计方案精巧到什么程度？从 1960 年代被提出以来，它至今仍然是所有主流操作系统的内存管理基础——Linux、Windows、macOS、FreeBSD，无一例外。

📌 核心要点

• 分页的核心优势是零外部碎片：任何空闲页框都能被任何进程的任何页使用，不存在"够不够大"的问题。
• 基本地址变换需要两次访存（第一次取页表项、第二次取数据），这是分页最根本的性能代价。
• TLB（快表）利用程序访问的局部性将地址变换速度提升一个数量级，命中率通常在 99% 以上。
• EAT = 命中率 × (TLB时间 + 访存时间) + 未命中率 × (TLB时间 + 2×访存时间 + 页表更新开销)。记住：未命中时多了额外一次访存。

---

分页的基本思想——把内存切成等大的方块

三个核心概念

页（Page）：进程的逻辑地址空间被划分为若干大小相等的块，每块称为一页。页的大小由硬件（CPU）决定，常见的页大小是 4KB（如 x86-64 的小页）。页号（Page Number）从 0 开始连续编号。

页框（Frame / Page Frame）：物理内存被划分为与页大小相同的块，每块称为一个页框或帧。页框也从 0 开始编号。

页表（Page Table）：存储在内存中的一个数据结构，用于记录每个逻辑页被映射到哪个物理页框。页表的索引是页号，页表项的内容是对应的页框号。

为什么页大小是 2 的整数次幂？

这不是巧合，而是一个精心设计的约定。假设逻辑地址空间为 32 位，页大小为 4KB = 2^12 字节。那么：

• 逻辑地址的低 12 位就是页内偏移量（Page Offset）
• 逻辑地址的高 20 位就是页号

关键在于：页内偏移量的位数 = log₂(页大小)。因为页大小是 2 的幂，所以逻辑地址的二进制拆分不需要做除法——直接按位截断即可。这是硬件实现上的巨大优势：地址转换可以在一个时钟周期内完成拆分。

如果页大小不是 2 的幂（比如 3KB），那么硬件就必须做一次真正的整数除法来拆分页号和偏移量——这会拖慢每一次内存访问。分页之所以能成为工业标准，和这个"按位截断"的硬件友好特性密不可分。

逻辑地址的拆分

对于一个 32 位的逻辑地址，4KB 页：

|←————— 20 位 —————→|←—— 12 位 ——→|
      页号 P              偏移量 W

• 页号 P = 逻辑地址 / 页大小（右移 12 位）
• 偏移量 W = 逻辑地址 % 页大小（取低 12 位）

物理地址 = 页框号 × 页大小 + 偏移量 W。注意：页内偏移量在转换过程中完全不变，只是把"底"从页号换成了页框号。

---

页表——操作系统的核心数据结构

页表项里有什么

每个页表项（Page Table Entry, PTE）至少包含：

• 页框号（Frame Number）：这是页表项的精华——这个逻辑页对应哪个物理页框。对于 32 位系统、4KB 页、4GB 物理内存，页框号需要 20 位（1M 个页框）。
• 有效位（Present / Valid bit）：P = 1 表示该页已在物理内存中；P = 0 表示该页不在（可能是未分配、或在磁盘交换区）。访问 P = 0 的页会触发缺页中断（Page Fault）。

在请求分页系统中，页表项还会扩展更多控制位（访问位、修改位等），但基本分页阶段，掌握页框号和有效位就足够。

页表的内存开销

页表本身存放在内存中。对于 32 位系统、4KB 页、每进程 4GB 逻辑地址空间，页表共有 4GB / 4KB = 1M 个页表项。若每个页表项占 4 字节，则每进程的页表开销为 4MB。如果有 100 个进程，就是 400MB——这显然是不可接受的。这个问题的解决方案是两级页表（下一篇讲解），基本分页阶段先知道有这个开销问题即可。

页表寄存器（Page Table Register, PTR）

CPU 中有一个专门的寄存器——页表基址寄存器（PTBR），存储当前进程的页表在内存中的起始物理地址。进程切换时，操作系统只需要更新 PTR，指向新进程的页表即可。这个切换开销相对较小，但访问页表本身需要访存——每个地址变换都要先访问一次 PTR 指向的页表，再访问实际数据。

---

基本地址变换机构——两次访存的完整流程

基本分页的地址变换步骤如下：

1. 从逻辑地址中拆分出页号 P 和页内偏移量 W。
2. 检查 P 是否超过页表长度（越界保护）。若越界，触发越界中断。
3. 将页表基址（来自 PTR）+ 页号 P × 页表项大小，得到该页的页表项在内存中的地址。
4. 第一次访存：从内存中读取页表项，获得页框号 F。
5. 物理地址 = F × 页大小 + W。
6. 第二次访存：从物理地址读取实际的数据或指令。

每访问一次数据，需要访问两次内存——这就是分页最根本的性能代价。一条访存指令（如 mov eax, [ebx]）在执行时需要两次物理内存访问，等效于访存速度减半。

⚠️ 注意事项：考研题目中常考"某系统采用基本分页，访问一次内存需要 t ns，求有效访存时间"。基本分页的有效访存时间 = 2t（因为没有 TLB）。这是最基础的题型，也是引入 TLB 动机的直接体现。

考题类型：给定页表，求物理地址

假设系统页大小为 4KB，某进程的页表如下：

页号	页框号
0	2
1	5
2	7

逻辑地址 A = 0x00001A2C（十进制 6700）。求物理地址。

解：页大小 4KB = 4096，页号 = 6700 / 4096 = 1，偏移量 = 6700 % 4096 = 2604。页号 1 对应页框号 5，物理地址 = 5 × 4096 + 2604 = 20480 + 2604 = 23084 = 0x00005A2C。

---

TLB——快表如何拯救分页的性能

两次访存的代价实在太大了。解决思路来自一个深刻的观察：程序访问内存时并非随机跳跃，而是表现出很强的局部性。

局部性原理

时间局部性（Temporal Locality）：如果程序访问了某个内存位置，那么它在不久的将来很可能再次访问同一个位置。典型场景：循环中的变量、频繁调用的函数。

空间局部性（Spatial Locality）：如果程序访问了某个内存位置，那么它附近的地址在不久的将来也很有可能被访问。典型场景：数组遍历、顺序执行的指令流。

这两个局部性的存在意味着：绝大多数地址转换请求都集中在少数的几个页上。所以，如果我们能把最近使用的页表项缓存起来——不是缓存在慢速的内存中，而是缓存在 CPU 内部的高速硬件中——就能避免绝大多数"第一次访存去查页表"的开销。

这个高速硬件缓存就是 TLB（Translation Lookaside Buffer），中文叫快表或地址转换后援缓冲器。

TLB 的工作原理

TLB 是一种专用的高速联想存储器（Associative Memory），它不像普通内存那样按地址索引，而是按内容并行比较。给定一个页号，TLB 在同一时刻把它和所有 TLB 表项中的页号进行比较，找到匹配的那一项，直接输出对应的页框号。整个过程通常在一个 CPU 时钟周期内完成。

引入 TLB 后的地址变换流程：

1. 从逻辑地址拆分出页号 P。
2. 查 TLB——用页号 P 并行比较所有 TLB 表项。
3. 若 TLB 命中（Hit）：直接从 TLB 获得页框号 F，跳过页表访问。物理地址 = F × 页大小 + 偏移量 W。一次访存即可获取数据。
4. 若 TLB 未命中（Miss）：走基本地址变换流程——第一次访存查页表获得页框号 F，第二次访存读取数据。同时将 (P, F) 更新到 TLB 中，供后续使用。

现代 CPU 的 TLB 命中率通常在 99%~99.9%。这意味着 99% 以上的地址变换只需要一次访存——效果接近没有分页的时候。

Effective Access Time（EAT）——必考公式

假设：

• TLB 查找时间 = ε（通常 1 个时钟周期，远小于访存时间）
• 一次内存访问时间 = t
• TLB 命中率 = α

EAT = α × (ε + t) + (1-α) × (ε + 2t)

解释：命中时 = TLB 查找 + 一次访存取数据；未命中时 = TLB 查找 + 一次访存查页表 + 一次访存取数据。

当 α 接近 1 时，EAT ≈ ε + t ≈ t——几乎等于没有分页的访存速度。

408 典型考题：t = 50ns，ε = 10ns，α = 98%。求 EAT。

EAT = 0.98 × (10 + 50) + 0.02 × (10 + 100) = 0.98 × 60 + 0.02 × 110 = 58.8 + 2.2 = 61ns。比不加 TLB 的 100ns（两次 50ns 访存）快了约 40%。

---

分页的工程视角

页大小的选择

页大小是一个工程权衡：

• 小页（如 4KB）：内部碎片少（每页最多浪费半页），但页表大、TLB 覆盖范围小。
• 大页（如 2MB 或 1GB）：页表小、TLB 覆盖范围大、TLB 命中率更高，但内部碎片多、交换开销大。

现代 CPU（x86-64、ARM）普遍支持多级页大小：4KB 小页 + 2MB 大页 + 1GB 巨页。Linux 的透明大页（Transparent Huge Pages, THP）可以自动将连续的 4KB 页面合并为 2MB 大页，对应用透明。

地址翻译的现代实现

现代 CPU 的 TLB 不是单层的——典型结构是 L1 TLB（分离指令 TLB 和数据 TLB，速度最快但容量小）和 L2 TLB（统一、容量较大）。地址翻译的完整链路上可能先查 L1 TLB → 未命中查 L2 TLB → 仍未命中才查页表（Page Walk）→ 最终触发缺页中断。考研阶段只需要掌握一层 TLB + 页表的模型，但工程现实中这个层次是更丰富的。

---

FAQ：常见问题速查

Q: TLB 的命中率为什么可以达到 99% 以上？

因为程序访问具有空间局部性——同一页内部的连续地址共享同一个页号。TLB 通常有 64~1024 个表项，以 4KB 页为例，64 个 TLB 表项覆盖 256KB——这已经足够容纳绝大多数程序的"当前工作区域"了。再加上循环和函数调用的时间局部性，TLB 命中率自然极高。

Q: 如果 TLB 未命中但页表项存在（P = 1），总共需要几次访存？

需要两次访存：第一次查页表（获得页框号 + 更新 TLB），第二次访问实际数据。总共两次——比命中多一次。但如果页表是多级的（如两级页表），查页表本身就可能需要多次访存，这也是为什么两级页表会引入更多性能代价。

Q: 页内偏移量为什么不需要存储在任何映射表中？

因为分页的核心约束是：页与页框大小严格相等。所以页内偏移量在地址转换时原封不动地从逻辑地址"搬"到物理地址，只是前面拼接的页号换成了页框号。这是一个巧妙的设计——通过保证页大小等于页框大小，避免了偏移量的重新计算。

Q: 如何快速判断一个系统是否使用分页？

看地址结构。如果逻辑地址中包含"页号"和"页内偏移量"两个字段，且页大小是 2 的整数次幂，那么一定是分页系统。物理地址 = 页框号 × 页大小 + 偏移量。注意：分页系统中没有"段"的概念，逻辑地址是一维的——只有一个编号（不像分段有段号和段内偏移两个维度）。

---

总结

分页是一次优雅的概念飞跃：允许物理内存以不连续的方式分配给进程。页表作为逻辑页到物理页框的映射枢纽，承担了地址转换的核心角色。TLB 利用局部性原理，将 99% 以上的地址转换加速到单时钟周期级别，使得分页在实际运行中的性能代价几乎可以忽略。

但单级页表的内存开销——每进程 4MB 的页表——还没有解决。而且分页本身也缺乏"按逻辑含义划分"的能力。这些问题将在下一篇中讨论：两级页表、分段和段页式存储管理。

[INTERNAL-LINK: 两级页表、分段与段页式——三种非连续分配方案的对比 → 第三章第 3 篇]

---

📚 延伸阅读

• Operating System Concepts, 10th Edition, Chapter 9.4~9.5: Paging and Structure of the Page Table
• Intel 64 and IA-32 Architectures Software Developer’s Manual, Vol 3A, Chapter 4: Paging
• What Every Programmer Should Know About Memory, Ulrich Drepper, Section 3: Virtual Memory and TLB

---