Lecture 15: 分页（Paging）
Lecture 15: 分页（Paging）
概述
分页把虚拟与物理地址空间都切成固定大小的页，用页表（page map/page table）映射虚拟页到物理页，彻底消除外部碎片并支持任意稀疏的地址空间。本讲深入 x86-64 的四级页表（PML4→PML3→PML2→PML1）翻译过程，讨论页表共享（2MB/1GB 大页）、TLB（翻译后备缓冲器）以及内部碎片。
核心概念与系统机制图解
分页的基本思想
- 虚拟与物理地址空间都划分成固定大小块：页（page）。常见 4KB（x86，myth 机器）或 16KB（MacBook）。
- 页表（Page Table / Page Map）：把虚拟页号（VPN）映射到物理页号（PPN）的表；每进程一张。
虚拟地址空间 页表(Page Map) 物理内存 VPN 0 ────────────► ┌──────────┐ ────────► PPN 0 VPN 1 ────────────► │ VPN→PPN │ ────────► PPN 1 VPN 2 ────────────► │ 映射条目 │ ────────► PPN 3 ... │ (PTE) │ ... VPN n ────────────► └──────────┘ PPN n 页表条目(PTE)通常含: PPN + Present(存在位) + Writeable(可写位) + 其它标志 虚拟地址 = [VPN][offset] 物理地址 = [PPN][offset]
固定大小的好处
- 物理内存管理：OS 维护空闲物理页链表——分配 = 取一页，释放 = 还一页（无碎片）。
- 虚拟地址空间管理：程序的一段（segment）就是一组页，可从任意页边界开始。
x86-64 四级页表（为什么需要多级？）
- 64 位虚拟地址、4KB 页、8 字节 PTE → 若用单级页表：
2^36 项 × 8B = 512GB/进程 —— 不可行！ - 方案：把页表本身也按页切分（每页 512 个 8B 条目），再加一级索引……逐级嵌套：
64位虚拟地址: [PML4(9位)][PML3(9位)][PML2(9位)][PML1(9位)][offset(12位)] │ │ │ │ │ ▼ ▼ ▼ ▼ ▼ PML4基址寄存器 → PML4表(512项) → PML3表(512项) → PML2表(512项) → PML1表(512项) → 物理页 每级表恰好一页(4KB = 512×8B); 有 Present 位的级可省略(稀疏地址空间只分配用到的表) - 翻译示例（Lecture 15）：
- 访问代码页 0x0：PML4[0x0]→PML3[0x0]→PML2[0x0]→PML1[0x0]→PTE 得到物理页；
- 访问栈页 0xFFFFFFFFF000：四级索引全是 0x1FF（512）——栈页在虚拟空间顶端；
- 访问数据页 0x1000：PML4[0]→PML3[0]→PML2[0]→PML1[1]。
- 这像什么数据结构？ 像一棵 4 层 512 叉树——只有被访问的路径才分配页表页。
内存共享（x86-64）
- 两个进程的 PML1 条目指向同一个物理页 → 共享 4KB；
- 让两个 PML2 指向同一张 PML1 表 → 共享 2MB（512×4KB）；
- 同理可共享 1GB、512GB 对象 → 大页（2MB/1GB）天然支持。
TLB（Translation Lookaside Buffer）
- 问题：一次访问要查 4 级页表 = 4 次内存访问，太慢！
- 方案：在 MMU 里放一个小而快的翻译缓存：VPN→PPN 映射。
- 典型容量 64–2048 条目；全相联；命中率通常 >95%（局部性）。
- 命中：直接用 PPN + 检查保护位；未命中：走页表并填充 TLB。
- OS 相关操作：
- 切换页表（上下文切换）时必须使 TLB 失效（x86 写 PML4 基址自动刷新；有的架构给 TLB 条目加 PID 避免全刷）；
- 修改页表后需用
INVLPG指令使对应 TLB 条目失效。
碎片化的两种形式
- 外部碎片：进程之间的碎片——分页用固定大小页消除了它。
- 内部碎片：页内部未使用的空间——分页引入了它（每段最后一页平均浪费半页）；页越大内部碎片越严重。
代码示例与系统调用解说
示例：mmap 映射文件并访问（分页的用户可见形态）
#include <fcntl.h>
#include <sys/mman.h>
#include <unistd.h>
#include <cstdio>
#include <cstring>
int main() {
int fd = open("data.bin", O_RDWR | O_CREAT, 0644);
if (fd < 0) { perror("open"); return 1; }
ftruncate(fd, 4096); // 保证文件有一页大小
char* p = (char*)mmap(nullptr, 4096, // 映射 4KB (一页)
PROT_READ | PROT_WRITE,
MAP_SHARED, fd, 0);
if (p == MAP_FAILED) { perror("mmap"); return 1; }
strcpy(p, "hello from mmap"); // 写: 触发缺页→分配物理页→读文件内容
printf("read back: %s\n", p);
msync(p, 4096, MS_SYNC); // 把脏页写回文件
munmap(p, 4096); // 解除映射
close(fd);
return 0;
}
【代码做了什么？】 mmap 把文件内容映射进进程虚拟地址空间；访问映射区域如同访问内存；msync 强制写回。
【系统机制透视】
mmap建立”虚拟页 ↔ 文件块”的页表条目（present 位初始为 0）；首次读写触发缺页中断，内核分配物理页、从文件读入数据、置 present 位（Assign5 就是用户态模拟这一流程！）。MAP_SHARED下多个进程映射同一文件 → 共享同一物理页（页表级共享）；MAP_PRIVATE则用写时复制隔离。- 这展示了分页的完整价值：文件可以被当作内存访问、按需加载、跨进程共享——而这一切对用户透明。
关键要点
- 分页 = 固定大小页 + 页表；消除外部碎片，支持稀疏、可共享的地址空间。
- x86-64 用四级页表（PML4→PML1）避免单级页表 512GB 的荒谬开销；只有用到的路径才分配页表页。
- TLB 缓存 VPN→PPN，命中率 >95%；上下文切换需使其失效。
- 共享可通过”页表条目指向同一物理页”实现，天然支持 4KB/2MB/1GB 大页。
- 分页把外部碎片换成内部碎片（每段最后一页最多浪费一页）。
常见陷阱与注意事项
- 把页表大小算成单级：x86-64 必须 4 级，否则内存爆炸。
- 忘记 TLB 失效：修改页表后不刷新 TLB 会用到陈旧映射（安全与正确性双重问题）。
- 混淆内部/外部碎片：分页消除外部、引入内部。
- 页大小选择：页越大页表越小、I/O 越高效，但内部碎片越大。
思考题
- 问题：为什么 x86-64 不用一张巨大的单级页表？
- 答案：64 位地址 + 4KB 页 → 2^52 个潜在页，8B 条目需要 2^55 字节（32PB）；而四级页表只需分配实际使用的路径，一个只用了 3 页的程序只需 4 张页表页（约 16KB）。
- 问题：TLB 命中为什么能大幅加速内存访问？
- 答案：未命中需 4 次页表内存访问；命中只需一次 TLB 查找（几纳秒）。局部性使 TLB 命中率超 95%，平均访问时间接近一次快速查找。
- 问题：两个进程如何共享一个 2MB 的只读库？
- 答案：让两个进程 PML2 表的同一项指向同一张 PML1 页表，从而共享其下全部 512 个 4KB 页（共 2MB）；物理上只有一份库代码。