第9章：虚拟内存
假装我们有用不完的物理内存
导读
如果你曾经在一台只有 4GB 物理内存的机器上运行过一个占用 10GB 内存的程序，或者曾经好奇为什么两个进程可以同时"使用"同一个地址 0x400000 却互不干扰，那么本章就是为你准备的。虚拟内存（Virtual Memory，简称 VM）是计算机系统中最优雅、最深刻的抽象之一——它让每个进程都产生一种幻觉：自己独占了整个物理内存。这种幻觉不仅简化了编程模型，还从根本上改变了操作系统管理内存的方式，使得内存保护、进程隔离、共享内存、延迟分配等关键能力成为可能。
从存储器层次结构的角度看，虚拟内存处于一个非常特殊的位置。它既是一个硬件机制（MMU、TLB、页表寄存器），又是一个操作系统特性（页表管理、缺页处理、页面置换），同时也是程序员必须理解的概念（内存映射文件、动态内存分配、对齐与碎片）。理解虚拟内存，意味着你真正打通了从硬件到操作系统到应用程序的整条链路。
本章我们将沿着以下脉络展开：首先理解虚拟地址空间的基本概念和作用；然后深入地址翻译的核心机制——页表；接着探讨多级页表如何解决"页表本身太大"的问题；再来看 TLB 如何加速地址翻译；之后讨论内存映射文件这一强大的 I/O 抽象；最后深入动态内存分配器的内部实现，理解 malloc 和 free 到底在做什么。
核心概念详解
一、虚拟地址与地址空间
1.1 什么是虚拟地址
在现代计算机系统中，CPU 发出的每一个内存地址都是虚拟地址（Virtual Address），而非物理地址。这意味着程序看到的"内存"并不是真实的物理 RAM，而是操作系统为每个进程精心构造的一个假象。虚拟地址经硬件中的内存管理单元（Memory Management Unit，MMU）翻译后，才变成真正的物理地址，送往内存子系统。
这个设计看似多此一举——为什么要绕一个大弯？事实上，虚拟内存机制带来了至少三个核心好处：
第一，地址空间抽象。 每个进程都拥有一个独立的、连续的虚拟地址空间。从 0x0000000000000000 到 0xFFFFFFFFFFFFFFFF（在 64 位系统上），这看起来是一个巨大的空间，但实际上操作系统只映射了其中很小的一部分。程序不需要关心物理内存的实际布局，不需要和其他进程"抢"地址，只需要在自己的虚拟地址空间里自由地使用指针和数组。
第二，内存保护。 虚拟地址空间中的每个页面都可以被标记为不同的权限——可读、可写、可执行。操作系统通过页表项中的权限位，配合 MMU 的硬件检查，确保一个进程不能随意读写其他进程或内核的内存。当你试图访问一个没有权限的地址时，MMU 会触发一个异常（在 x86 上称为 page fault），操作系统接管后通常会向进程发送 SIGSEGV 信号，也就是我们常说的"段错误"（Segmentation Fault）。
第三，共享与复用。 虚拟内存允许不同的进程将各自的虚拟页面映射到同一个物理页面。这就是共享内存的基础。操作系统的代码和数据只需要在物理内存中存在一份，就可以被所有进程共享。类似地，C 标准库的代码也只加载一次，通过共享映射出现在每个进程的地址空间中。
1.2 虚拟地址空间的布局
在一个典型的 Linux 系统中，进程的虚拟地址空间有着精心设计的布局。以 64 位 Linux 为例（虽然实际使用的地址位通常只有 48 位，即 0x0000000000000000 到 0x00007FFFFFFFFFFF 用于用户空间），从低地址到高地址大致如下：
0x000000000000 ┌─────────────────────┐
│ 保留区（不可访问） │
0x004000000000 ├─────────────────────┤
│ 代码段 (.text) │ ← 可执行文件中的机器指令
├─────────────────────┤
│ 只读数据 (.rodata) │ ← 字符串常量等
├─────────────────────┤
│ 已初始化数据 (.data) │ ← 全局变量和静态变量（有初值）
├─────────────────────┤
│ 未初始化数据 (.bss) │ ← 全局变量和静态变量（零初始化）
├─────────────────────┤
│ ↓ │ ← 栈向下增长
│ 栈 (stack) │ ← 局部变量、函数调用帧
│ ↑ │
├─────────────────────┤
│ 内存映射区域 │ ← 共享库、内存映射文件
├─────────────────────┤
│ ↓ │
│ 堆 (heap) │ ← malloc 分配，向上增长
│ ↑ │
├─────────────────────┤
│ 内核虚拟内存 │ ← 所有进程共享，受保护
0xFFFFFFFFFFFF └─────────────────────┘值得注意的是，栈从高地址向低地址增长，而堆从低地址向高地址增长。两者之间的巨大空隙就是内存映射区域，用于加载共享库（如 libc.so）和通过 mmap 创建的文件映射。
1.3 虚拟内存作为缓存
从存储器层次结构的角度来看，虚拟内存本质上是一个位于 DRAM 和磁盘之间的缓存。当物理内存不够时，操作系统会将不活跃的页面"换出"（swap out）到磁盘上的交换空间（swap space）；当这些页面再次被访问时，再"换入"（swap in）回物理内存。这个机制使得系统可以运行总工作集大于物理内存的程序集合，虽然性能会因为磁盘 I/O 的高延迟而下降，但程序的正确性不受影响。
这种设计带来了一个深刻的洞察：虚拟内存不仅是一个地址抽象，它还是存储层次中的一级。 正如 L1 缓存对 L2 缓存透明，L2 对主存透明一样，虚拟内存对程序员也是基本透明的——你不需要知道你的数据此刻是在物理内存中还是在磁盘上，MMU 和操作系统会自动处理这一切。
二、页表与地址翻译
2.1 页的基本概念
虚拟内存以页（Page）为基本管理单位。在大多数系统中，页大小为 4KB（即 $2^{12}$ 字节）。这意味着虚拟地址空间被划分为固定大小的块，每个块称为一个虚拟页（Virtual Page，VP）；相应地，物理内存也被划分为同样大小的块，称为物理页帧（Physical Page Frame，PPF）或物理页。
页大小为什么是 4KB？这是一个历史选择与工程折中的结果。页太小，页表会过于庞大，管理开销过高；页太大，内部碎片严重（一个只用了 1 字节的页仍然占用 4KB 物理内存），而且不利于细粒度的内存保护。4KB 是一个经验上比较平衡的选择，不过现代系统也支持大页（Huge Page），如 2MB 甚至 1GB，用于减少 TLB 未命中带来的性能损失。
2.2 页表的结构
页表（Page Table）是虚拟地址到物理地址的映射表。每个进程都有自己的页表，存储在物理内存中（部分可能被换出到磁盘）。页表本质上是一个数组，每个元素称为页表项（Page Table Entry，PTE），包含以下关键信息：
- 物理页帧号（PPN）：指示该虚拟页当前映射到哪个物理页帧。
- 有效位（Valid bit）：表示该虚拟页当前是否已映射到物理内存。如果有效位为 0，访问该虚拟页会触发缺页异常。
- 保护位（Protection bits）：指示对该页的访问权限，如读/写/执行。
- 脏位（Dirty bit）：表示该页自加载以来是否被修改过。这在页面置换时很重要——如果页面没有被修改过，可以直接丢弃；如果被修改过，必须先写回磁盘。
- 缓存控制位：指示对该页的访问是否应该经过 CPU 缓存。
在 x86-64 架构中，一个页表项为 64 位，其中包含了上述所有信息以及一些架构特定的标志位。
2.3 地址翻译的完整过程
当 CPU 执行一条指令需要访问内存时，地址翻译的过程如下：
CPU 生成一个虚拟地址（由段基址 + 偏移量组成，在分页模式下段基址通常为 0）。
MMU 从虚拟地址中提取虚拟页号（Virtual Page Number，VPN）和页内偏移（Page Offset）。以 4KB 页为例，虚拟地址的低 12 位是页内偏移，高位是 VPN。
MMU 使用 VPN 作为索引，查找页表，获取对应的页表项（PTE）。
MMU 检查 PTE 中的有效位。如果有效位为 1，说明该虚拟页当前在物理内存中：
- MMU 从 PTE 中提取物理页帧号（PPN），与页内偏移拼接，形成物理地址。
- 物理地址被送往内存子系统。
如果有效位为 0，触发缺页异常（Page Fault）：
- CPU 陷入操作系统内核。
- 操作系统检查该访问是否合法（例如，是否访问了未分配的内存区域）。
- 如果不合法，操作系统向进程发送 SIGSEGV，进程终止。
- 如果合法（例如，页面在磁盘的交换空间中，或者是一个尚未分配的惰性分配页面），操作系统执行缺页处理：
a. 在物理内存中找一个空闲页帧（如果没有，则执行页面置换，选一个"牺牲页"换出）。
b. 如果牺牲页被修改过，先将其写回磁盘。
c. 将需要的页面从磁盘读入选定的物理页帧。
d. 更新页表项，将有效位置 1，填入新的 PPN。
e. 重新执行触发缺页的那条指令。
整个过程对程序员几乎完全透明。一条普通的 MOV 指令，背后可能经历了一次甚至多次缺页处理，但指令本身并不需要知道这些。
2.4 一个具体的地址翻译示例
假设系统使用 4KB 页，虚拟地址为 14 位，物理地址为 12 位。虚拟地址中，高 6 位为 VPN，低 8 位为页内偏移（这里为了教学简化，实际中页大小和地址位宽不同）。
虚拟地址: 0x0D2E = 0000 1101 0010 1110
VPN = 000011 = 3
偏移 = 0101110 = 0x2E (实际偏移位数取决于页大小)MMU 用 VPN=3 查找页表，得到 PTE[3]：
PTE[3] = 有效位:1 | PPN:0x0D | 权限:RW物理地址 = PPN << 页偏移位数 | 页内偏移 = 0x0D 拼接偏移部分。
三、多级页表
3.1 问题的提出
前述的简单页表方案有一个严重的问题：页表本身太大了。假设虚拟地址空间为 48 位，页大小为 4KB（12 位偏移），那么 VPN 有 $2^{36}$ 个。每个 PTE 为 8 字节，整个页表需要 $2^{36} \times 8 = 2^{39}$ 字节 = 512GB。即使一个进程的虚拟地址空间中只映射了几个页面，页表本身也需要 512GB 的连续空间来存储——这显然是不现实的。
解决方案就是多级页表（Multi-level Page Table），其核心思想是：既然大部分虚拟地址空间是空的（没有映射），那么只为已映射的部分分配页表存储空间。
3.2 x86-64 的四级页表
x86-64 架构使用四级页表结构，将 48 位 VPN 分为 4 个 9 位的字段，加上 12 位页内偏移：
虚拟地址 (48位):
┌────────┬────────┬────────┬────────┬──────────┐
│ PGD │ PUD │ PMD │ PTE │ Offset │
│ 9 bits │ 9 bits │ 9 bits │ 9 bits │ 12 bits │
└────────┴────────┴────────┴────────┴──────────┘翻译过程需要四次内存访问（假设每次都在缓存中未命中）：
PGD（Page Global Directory）：用 VPN 的最高 9 位索引，指向一个 PUD。
PUD（Page Upper Directory）：用第二组 9 位索引，指向一个 PMD。
PMD（Page Middle Directory）：用第三组 9 位索引，指向一个 PTE 表。
PTE（Page Table Entry）：用第四组 9 位索引，得到最终的物理页帧号。
每一级页表都恰好占一个页面（4KB），可以容纳 512 个条目（$512 \times 8 = 4096$ 字节）。
3.3 多级页表如何节省空间
多级页表的精妙之处在于：如果某一级页表中的所有条目都指向同一个下级页表（或者都为空），那么这一级只需要一个页面。更具体地说：
- 如果一段虚拟地址空间完全没有映射，那么对应的 PGD 条目为空，不需要分配 PUD、PMD 和 PTE 页面。
- 如果一段地址空间是连续映射的，那么可以共享上级的页表条目。
对于一个只使用了几 MB 虚拟内存的典型程序，四级页表实际占用的物理内存可能只有几十 KB，远远小于简单线性页表的 512GB。
当然，多级页表也有代价：每次地址翻译需要多次内存访问（4 次在 x86-64 上）。这就是为什么 TLB 如此重要——它缓存了最近的地址翻译结果，避免了每次都走完整的多级页表查找。
3.4 大页与页表
现代处理器支持大页（Huge Page / Large Page）。在 x86-64 上，可以配置 PTE 或 PMD 条目使用大页模式：
- 2MB 大页：在 PMD 级别直接指向物理页，跳过 PTE 级别。VPN 被分为 PGD(9) + PUD(9) + PMD(9)，偏移为 21 位。
- 1GB 大页：在 PUD 级别直接指向物理页，跳过 PMD 和 PTE 级别。
大页对于需要映射大量连续内存的应用（如数据库、虚拟机监控器）非常有用，因为它减少了 TLB 未命中率，也减少了页表的级数和内存开销。
四、TLB（转译后备缓冲器）
4.1 为什么需要 TLB
如前所述，多级页表的地址翻译需要多次内存访问。在 x86-64 上，最坏情况下需要 4 次内存访问来完成一次地址翻译。考虑到每次内存访问可能需要数百个时钟周期，这个开销是非常可观的。
TLB（Translation Lookaside Buffer，转译后备缓冲器）是一个位于 MMU 中的小型、高速的缓存，用于存储最近的虚拟页到物理页帧的映射。它本质上是一个关联存储器（Associative Memory），可以同时比较所有条目，因此查找速度极快，通常只需要 1-2 个时钟周期。
TLB 的命中率对程序性能影响巨大。一个 TLB 未命中意味着必须走完整的多级页表查找，可能需要 4 次甚至更多次内存访问。如果 TLB 命中率为 99%，那么平均地址翻译成本约为 $0.99 \times 1 + 0.01 \times 400 \approx 5$ 个周期；如果命中率降到 95%，则约为 $0.95 \times 1 + 0.05 \times 400 \approx 21$ 个周期——性能下降了 4 倍。
4.2 TLB 的组织方式
TLB 通常是一个小型的组相联或全相联缓存。典型的 TLB 大小为 32 到 128 个条目，有些处理器还有分离的指令 TLB（ITLB）和数据 TLB（DTLB），类似于分离的 L1 指令缓存和数据缓存。
每个 TLB 条目包含：
- VPN：虚拟页号，作为标签。
- PPN：物理页帧号。
- 保护位：读/写/执行权限。
- ASID（Address Space ID）：进程标识符，用于区分不同进程的映射（避免在进程切换时刷新整个 TLB）。
- 有效位：指示该条目是否有效。
当 CPU 生成一个虚拟地址时，MMU 首先在 TLB 中查找 VPN。如果找到（TLB 命中），直接使用对应的 PPN 构造物理地址。如果未找到（TLB 未命中），则走页表查找路径，找到映射后将新的 VPN→PPN 映射加入 TLB。如果 TLB 已满，需要替换一个旧条目（通常使用 LRU 或伪 LRU 策略）。
4.3 TLB 与上下文切换
当操作系统进行进程切换时，TLB 中缓存的映射属于旧进程，对新进程无效。传统做法是通过修改 CR3 寄存器（在 x86 上）来刷新整个 TLB，这是一个代价高昂的操作。
现代处理器引入了 PCID（Process-Context ID，在 x86 上）或 ASID（在 ARM 上）机制。每个 TLB 条目都附带一个进程标识符，进程切换时只需修改当前 PCID/ASID 的值，而不需要刷新 TLB。只有当不同进程恰好映射了相同的虚拟页时，才可能出现混淆，但 PCID/ASID 机制通过标签匹配避免了这个问题。
4.4 TLB 未命中的性能影响
以下代码展示了一个典型的 TLB 未命中导致性能下降的场景——步幅访问（strided access）：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 1024 * 1024 // 4GB 数组（1M 个 int，每个 4B → 4MB，
// 但为了演示效果，实际可调整大小）
int main() {
int *arr = (int *)malloc(N * sizeof(int));
// 顺序访问：TLB 友好
clock_t start = clock();
for (int i = 0; i < N; i++) {
arr[i] = 0;
}
clock_t end = clock();
printf("顺序访问: %.4f 秒\n",
(double)(end - start) / CLOCKS_PER_SEC);
// 大步幅访问：TLB 不友好
int stride = 1024; // 每次跳 4KB，恰好跨越一个页面
start = clock();
for (int i = 0; i < N; i += stride) {
arr[i] = 0;
}
clock_t end = clock();
printf("步幅访问 (stride=%d): %.4f 秒\n",
stride, (double)(end - start) / CLOCKS_PER_SEC);
free(arr);
return 0;
}当步幅等于页大小时，每次内存访问都访问不同的页面，导致 TLB 频繁未命中。如果数组足够大，TLB 无法缓存所有活跃页面的映射，性能会显著下降。这就是为什么在处理大型数组时，数据局部性（locality）如此重要。
五、内存映射
5.1 内存映射文件
内存映射（Memory Mapping）是将一个文件（或其他对象）直接映射到进程的虚拟地址空间的技术。映射后，对文件内容的读写就等价于对内存的读写，无需调用 read() 和 write() 系统调用。
在 Linux 中，通过 mmap() 系统调用来创建内存映射：
#include <sys/mman.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <stdio.h>
#include <string.h>
int main() {
int fd = open("data.txt", O_RDONLY);
if (fd < 0) {
perror("open");
return 1;
}
struct stat sb;
fstat(fd, &sb);
size_t file_size = sb.st_size;
// 将文件映射到进程地址空间
char *addr = mmap(NULL, file_size, PROT_READ,
MAP_PRIVATE, fd, 0);
if (addr == MAP_FAILED) {
perror("mmap");
close(fd);
return 1;
}
// 现在可以像访问数组一样访问文件内容
for (size_t i = 0; i < file_size && i < 100; i++) {
putchar(addr[i]);
}
munmap(addr, file_size);
close(fd);
return 0;
}内存映射的优势在于：
- 零拷贝：不需要将文件内容从内核缓冲区复制到用户缓冲区，文件直接出现在进程的地址空间中。
- 惰性加载：映射创建时，并不会立即将文件读入内存。只有当进程首次访问某个页面时，才会触发缺页异常，操作系统才将对应的文件数据读入物理内存。
- 共享方便：多个进程可以映射同一个文件，实现进程间共享数据。
5.2 共享映射与私有映射
mmap 支持两种映射类型：
- MAP_SHARED：对映射区域的修改会写回到文件中（最终），并且对其他映射了同一文件的进程可见。多个进程使用
MAP_SHARED映射同一文件，就构成了共享内存。 - MAP_PRIVATE：对映射区域的修改是私有的，不会写回文件，也不影响其他进程。这通过写时复制（Copy-on-Write，CoW）机制实现——首次写入时，操作系统为该页面创建一个私有副本。
5.3 匿名映射
除了文件映射，mmap 还可以创建匿名映射（Anonymous Mapping），即不与任何文件关联的映射。这实际上就是 malloc 在大块分配时底层使用的方式：
void *ptr = mmap(NULL, size, PROT_READ | PROT_WRITE,
MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);匿名映射的页面在首次访问时被初始化为零（由操作系统提供全零的物理页帧）。
六、动态内存分配
6.1 分配器的基本任务
动态内存分配器（如 malloc/free 的实现）负责管理进程的堆区域。它的核心任务是：
- `malloc(size)`：在堆中找到一块足够大的空闲区域，返回指向该区域的指针。
- `free(ptr)`：释放之前分配的内存块，使其可以被后续的
malloc请求重用。
分配器需要维护一个空闲链表（Free List），记录堆中所有空闲块的位置和大小。malloc 在空闲链表中搜索合适的块，free 将释放的块插入空闲链表。
6.2 分配策略
在空闲链表中搜索合适块的策略主要有以下几种：
- 首次适配（First Fit）：从头开始搜索空闲链表，返回第一个足够大的块。优点是简单快速，缺点是可能在链表头部积累大量小的碎片。
- 下一次适配（Next Fit）：与首次适配类似，但从上一次搜索结束的位置开始。有助于更均匀地分布分配。
- 最佳适配（Best Fit）：搜索整个链表，找到最小的但足够大的块。理论上碎片最少，但需要遍历整个链表，速度慢，而且可能产生非常小的无用碎片。
- 分离适配（Segregated Fit）：维护多个空闲链表，每个链表管理特定大小范围的块。分配时根据请求大小选择对应的链表。这是现代分配器（如 glibc 的 ptmalloc）常用的策略。
6.3 块的格式
每个已分配或空闲的块都有一个头部（Header），包含块的大小和一些标志位。典型的块格式如下：
已分配块:
┌──────────┬──────────────────────────────┐
│ 头部 │ 有效载荷（payload） │
│ (size+A) │ │
└──────────┴──────────────────────────────┘
空闲块:
┌──────────┬────────┬────────┬────────────┐
│ 头部 │ 下一空闲│ 上一空闲│ ... │
│ (size+A) │ 指针 │ 指针 │ │
└──────────┴────────┴────────┴────────────┘头部中的 A 位（Allocated bit）表示该块是否已分配。块大小包含头部的大小。为了对齐，通常还有一个填充（Padding）区域。有些实现还在块的尾部放置一个脚部（Footer），记录块的大小，以便在 free 时从有效载荷的起始地址向前找到头部，或者向后找到下一个块。
6.4 放置策略与分割
当 malloc 找到一个足够大的空闲块时，有两种选择：
- 使用整个块：即使请求的大小远小于块的大小。这会产生内部碎片。
- 分割块：将空闲块分为两部分——一部分分配给请求，另一部分作为新的空闲块留在链表中。前提是剩余部分足够大（至少能容纳一个头部加上最小的有效载荷）。
分割策略可以减少浪费，但过于频繁的分割会产生大量无法利用的小碎片。
6.5 合并（Coalescing）
当 free 释放一个块时，如果它与相邻的空闲块连续，应该将它们合并为一个更大的空闲块。合并可以显著减少外部碎片。
合并有几种情况：
- 前后都不是空闲块：无需合并。
- 只有前一个块是空闲的：将前块扩展。
- 只有后一个块是空闲的：将当前块与后块合并。
- 前后都是空闲块：将三个块合并为一个。
合并可以立即进行（在 free 时）或延迟进行（在 malloc 时检测到相邻空闲块再合并）。立即合并简单但可能产生不必要的开销；延迟合并更高效但实现更复杂。
6.6 碎片问题
动态内存分配的最大挑战是碎片（Fragmentation）：
- 内部碎片：已分配块中未被使用的空间（如填充、头部开销）。
- 外部碎片：堆中有足够的总空闲空间来满足请求，但这些空闲空间分散在多个不连续的小块中，无法合并为一个足够大的块。
外部碎片是一个严重的问题。考虑以下场景：堆中有 1000 个 8 字节的空闲块，总空闲空间为 8000 字节。此时如果请求一个 8000 字节的块，即使总空闲空间足够，分配器也无法满足请求，因为没有连续的 8000 字节空闲空间。
缓解外部碎片的策略包括：
- 合并：及时合并相邻空闲块。
- 分离适配：将不同大小的请求分类到不同的空闲链表，减少大小不匹配造成的碎片。
- 放置策略：如最佳适配，但代价是速度。
6.7 一个简单的分配器实现
以下是一个教学用的简单分配器实现，使用隐式空闲链表和首次适配策略：
#include <stdio.h>
#include <string.h>
#include <errno.h>
#include <unistd.h>
// 块头部
typedef size_t block_header_t;
#define WSIZE sizeof(size_t) // 字大小
#define DSIZE (2 * WSIZE) // 双字大小
#define CHUNKSIZE (1 << 12) // 扩展堆的块大小 (4KB)
#define ALLOC_MASK 0x1 // 已分配标志位
#define SIZE_MASK ~0x7 // 大小掩码（低3位用于标志）
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define PACK(size, alloc) ((size) | (alloc))
#define GET_SIZE(ptr) (*(block_header_t *)(ptr) & SIZE_MASK)
#define GET_ALLOC(ptr) (*(block_header_t *)(ptr) & ALLOC_MASK)
#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE((char *)(bp) - DSIZE))
static char *heap_listp = NULL;
static void *extend_heap(size_t words) {
char *bp;
size_t size;
size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
bp = sbrk(size);
if (bp == (void *)-1) return NULL;
*(block_header_t *)HDRP(bp) = PACK(size, 0);
*(block_header_t *)FTRP(bp) = size;
*(block_header_t *)HDRP(NEXT_BLKP(bp)) = PACK(0, 1);
return bp; // 简化版，省略合并
}
void malloc_init(void) {
heap_listp = sbrk(2 * WSIZE);
if (heap_listp == (void *)-1) {
fprintf(stderr, "sbrk failed: %s\n", strerror(errno));
return;
}
*(block_header_t *)(heap_listp) = PACK(DSIZE, 1);
*(block_header_t *)(heap_listp + WSIZE) = PACK(DSIZE, 1);
heap_listp += DSIZE;
extend_heap(CHUNKSIZE / WSIZE);
}
void *malloc(size_t size) {
size_t adjusted_size;
char *bp, *startp;
if (heap_listp == NULL) malloc_init();
if (size == 0) return NULL;
adjusted_size = MAX(DSIZE, DSIZE * ((size + (WSIZE - 1)) / DSIZE));
bp = heap_listp;
while (GET_SIZE(HDRP(bp)) > 0) {
if (!GET_ALLOC(HDRP(bp)) && GET_SIZE(HDRP(bp)) >= adjusted_size) {
// 找到合适的块
size_t block_size = GET_SIZE(HDRP(bp));
if (block_size >= adjusted_size + DSIZE) {
// 分割
*(block_header_t *)HDRP(bp) = PACK(adjusted_size, 1);
char *next_bp = NEXT_BLKP(bp);
*(block_header_t *)HDRP(next_bp) = PACK(block_size - adjusted_size, 0);
*(block_header_t *)FTRP(next_bp) = block_size - adjusted_size;
} else {
*(block_header_t *)HDRP(bp) = PACK(block_size, 1);
}
return bp;
}
bp = NEXT_BLKP(bp);
}
// 没有合适的块，扩展堆
bp = extend_heap(MAX(adjusted_size / WSIZE, CHUNKSIZE / WSIZE));
if (bp == NULL) return NULL;
// 重新搜索（简化处理）
startp = heap_listp;
while (GET_SIZE(HDRP(startp)) > 0) {
if (!GET_ALLOC(HDRP(startp)) && GET_SIZE(HDRP(startp)) >= adjusted_size) {
size_t block_size = GET_SIZE(HDRP(startp));
*(block_header_t *)HDRP(startp) = PACK(adjusted_size, 1);
if (block_size >= adjusted_size + DSIZE) {
char *next_bp = NEXT_BLKP(startp);
*(block_header_t *)HDRP(next_bp) = PACK(block_size - adjusted_size, 0);
*(block_header_t *)FTRP(next_bp) = block_size - adjusted_size;
}
return startp;
}
startp = NEXT_BLKP(startp);
}
return NULL;
}
void free(void *bp) {
if (bp == NULL) return;
size_t size = GET_SIZE(HDRP(bp));
*(block_header_t *)HDRP(bp) = PACK(size, 0);
*(block_header_t *)FTRP(bp) = size;
// 简化版，省略立即合并
}这个实现非常简化，省略了合并逻辑，但它展示了分配器的核心思想：通过 sbrk 系统调用扩展堆，维护块的头部和脚部信息，使用首次适配策略搜索空闲块。
代码示例
示例一：观察虚拟内存布局
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int global_var = 42; // .data 段
int global_uninit; // .bss 段
const char *str_literal = "hello"; // .rodata 段
void dummy_function(void) {
int local_var = 100; // 栈上
printf("局部变量 local_var 地址: %p\n", (void *)&local_var);
}
int main() {
printf("=== 虚拟地址空间布局 ===\n\n");
printf("代码段 (.text): %p (main 函数)\n", (void *)main);
printf("只读数据 (.rodata): %p (字符串常量)\n", (void *)"hello");
printf("已初始化数据 (.data): %p (global_var)\n", (void *)&global_var);
printf("未初始化数据 (.bss): %p (global_uninit)\n", (void *)&global_uninit);
int *heap_ptr = (int *)malloc(sizeof(int));
*heap_ptr = 999;
printf("堆 (heap): %p (malloc 分配)\n", (void *)heap_ptr);
printf("栈 (stack): ");
dummy_function();
free(heap_ptr);
return 0;
}运行后你会看到，代码段地址最低，然后是数据段、BSS 段，接着是堆（向上增长），最后是栈（向下增长）。这个布局印证了前文的理论分析。
示例二：观察缺页异常
#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <signal.h>
#include <unistd.h>
#include <string.h>
void segfault_handler(int sig) {
printf("捕获到信号 %d (SIGSEGV) - 非法内存访问!\n", sig);
exit(1);
}
int main() {
signal(SIGSEGV, segfault_handler);
// 使用 mmap 分配一块内存
size_t size = 4096 * 4; // 4 页
char *addr = mmap(NULL, size, PROT_READ | PROT_WRITE,
MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
printf("mmap 返回地址: %p\n", addr);
printf("映射大小: %zu 字节 (%zu 页)\n", size, size / 4096);
// 逐页访问，观察惰性分配
for (size_t i = 0; i < size; i += 4096) {
printf("访问页面 %zu (偏移 0x%zx)...\n", i / 4096, i);
addr[i] = 'A'; // 触发缺页，分配物理页
}
printf("\n所有页面已访问，尝试访问映射范围之外的地址...\n");
// 访问超出映射范围的地址
addr[size] = 'X'; // 这应该触发 SIGSEGV
munmap(addr, size);
return 0;
}这个程序展示了虚拟内存的惰性分配机制：mmap 只是建立了虚拟地址空间的映射，实际的物理页面在首次访问时才分配。当访问超出映射范围的地址时，MMU 无法在页表中找到有效映射，触发缺页异常，操作系统发现这是一个非法访问，发送 SIGSEGV 信号。
示例三：内存映射文件实现简单的 cp 命令
#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <string.h>
int main(int argc, char *argv[]) {
if (argc != 3) {
fprintf(stderr, "用法: %s <源文件> <目标文件>\n", argv[0]);
return 1;
}
// 打开源文件
int src_fd = open(argv[1], O_RDONLY);
if (src_fd < 0) {
perror("打开源文件失败");
return 1;
}
// 获取源文件大小
struct stat stat_buf;
if (fstat(src_fd, &stat_buf) < 0) {
perror("fstat 失败");
close(src_fd);
return 1;
}
off_t file_size = stat_buf.st_size;
// 创建目标文件并设置大小
int dst_fd = open(argv[2], O_RDWR | O_CREAT | O_TRUNC, 0644);
if (dst_fd < 0) {
perror("创建目标文件失败");
close(src_fd);
return 1;
}
if (ftruncate(dst_fd, file_size) < 0) {
perror("ftruncate 失败");
close(src_fd);
close(dst_fd);
return 1;
}
// 内存映射源文件和目标文件
char *src_addr = mmap(NULL, file_size, PROT_READ,
MAP_PRIVATE, src_fd, 0);
if (src_addr == MAP_FAILED) {
perror("映射源文件失败");
close(src_fd);
close(dst_fd);
return 1;
}
char *dst_addr = mmap(NULL, file_size, PROT_WRITE,
MAP_SHARED, dst_fd, 0);
if (dst_addr == MAP_FAILED) {
perror("映射目标文件失败");
munmap(src_addr, file_size);
close(src_fd);
close(dst_fd);
return 1;
}
// 直接通过内存拷贝完成文件复制
memcpy(dst_addr, src_addr, file_size);
// 确保数据写回磁盘
msync(dst_addr, file_size, MS_SYNC);
printf("文件复制完成: %s -> %s (%ld 字节)\n",
argv[1], argv[2], (long)file_size);
munmap(src_addr, file_size);
munmap(dst_addr, file_size);
close(src_fd);
close(dst_fd);
return 0;
}这个程序展示了内存映射的强大之处：整个文件复制操作只需要一次 memcpy，无需显式的 read/write 循环。操作系统在后台处理所有的页面调入和写回。
实验解读
实验：虚拟内存模拟器
CSAPP 提供了一个经典的虚拟内存实验——实现一个简单的虚拟内存系统。在这个实验中，学生需要：
实现地址翻译逻辑：给定一个虚拟地址，根据页表结构计算出物理地址。这需要理解 VPN、偏移量的提取，以及多级页表的逐级查找。
处理缺页异常：当页表项的有效位为 0 时，模拟缺页处理过程——选择一个牺牲页，将其写回（如果脏），将新页面读入，更新页表。
实现页面置换算法：实验通常要求实现 FIFO、LRU 或 Clock 等页面置换算法，并比较它们的缺页率。
这个实验的核心价值在于让你亲手实现地址翻译的每一个步骤，从而真正理解 MMU 在每条内存访问指令背后做了什么。很多学生在做完这个实验后才真正理解：为什么 TLB 如此重要，为什么多级页表是必要的，以及为什么页面置换算法的选择对性能有巨大影响。
实验：动态内存分配器
另一个经典实验是实现一个动态内存分配器（malloc lab）。学生需要实现 malloc、free、realloc 和 calloc 函数，在正确性和性能之间取得平衡。
这个实验的难点在于：
- 正确性：必须处理好所有的边界情况，如合并相邻空闲块、对齐要求、最小块大小等。
- 性能：需要在吞吐量（每秒分配/释放操作的次数）和利用率（已分配内存占总内存的比例）之间权衡。
- 碎片管理：如何在长时间运行后仍然保持较低的碎片率。
常见的优化策略包括：
- 使用显式空闲链表（在空闲块中存储前驱和后继指针）加速搜索。
- 使用分离适配（segregated free list），为不同大小的块维护独立的空闲链表。
- 使用 LIFO 顺序的隐式空闲链表，配合立即合并，实现简单但性能不错的分配器。
延伸阅读
《操作系统导论》（OSTEP）第 18-22 章：对虚拟内存有更深入的操作系统视角的讨论，包括页面置换算法的详细分析。
《Linux 内核设计与实现》第 15 章：从 Linux 内核的角度讲解虚拟内存管理，包括 vm_area_struct、页表管理、缺页处理的内核实现。
Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 3A, Chapter 4：x86-64 四级页表的官方文档，包括所有页表项的位定义。
ULIX 操作系统项目：一个教学用操作系统，包含完整的虚拟内存实现代码，适合想要深入理解内核级虚拟内存管理的读者。
jemalloc / tcmalloc：现代高性能内存分配器的开源实现。阅读它们的源代码可以了解工业级分配器如何处理碎片、并发分配、线程缓存等复杂问题。
论文 "The Slab Allocator: An Object-Caching Kernel Memory Allocator" (Jeff Bonwick, 1994)：介绍了 Solaris 内核的 Slab 分配器，是理解内核级内存管理的重要参考。