《深入理解计算机系统》读书笔记10: 虚拟存储器

作者: andylin02
学习章节: 第 9 章 虚拟存储器
关键词： 虚拟内存；页表；MMU；地址翻译；TLB；内存映射；mmap；动态内存分配；malloc；隐式空闲链表；显式空闲链表；分离适配；Malloc Lab

引言：虚拟内存——计算机系统的"终极抽象"

“虚拟内存是硬件异常、硬件地址翻译、主存、磁盘文件和内核软件的完美交互。它为每个进程提供了一个大的、一致的和私有的地址空间。”——CSAPP作者

在第 1-8 章中，我们逐步构建了对计算机系统的理解：从数据的二进制表示，到机器指令的执行，再到异常控制流和进程管理。然而，还有一个核心问题我们尚未完全解答：当几十个进程同时运行时，每个进程都以为自己独占整个内存——这个"魔法"是如何实现的？

答案就是虚拟内存。虚拟内存是本章的核心主题，也是计算机系统最重要的抽象之一。它提供了三个关键能力：

本章结构速览：

• 9.1 物理和虚拟寻址：从物理寻址到虚拟寻址的演进
• 9.2 地址空间：理解虚拟地址空间和物理地址空间
• 9.3 虚拟内存作为缓存工具：页表、缺页异常、页面置换
• 9.4 虚拟内存作为内存管理工具：简化链接、加载、共享
• 9.5 虚拟内存作为内存保护工具：权限位与隔离
• 9.6 地址翻译：MMU、页表、TLB 的完整工作流程
• 9.7 案例研究：Core i7 地址翻译
• 9.8 内存映射：mmap 与共享库
• 9.9 动态内存分配：malloc 与 free 的实现
• 9.10 垃圾收集：标记-清扫算法
• 9.11 常见陷阱：内存错误与调试工具
• 9.12 配套实验：Malloc Lab

一、物理寻址 vs 虚拟寻址

1.1 物理寻址

早期计算机系统使用物理寻址（Physical Addressing） ：CPU 直接生成物理地址（Physical Address，PA），发送给主存，主存从该地址取出数据返回 CPU。

┌─────────────────────────────────────────────────────────────────────┐
│ 物理寻址模型 │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ CPU ─────── 物理地址(PA) ──────→ 内存 │
│ │ │ │
│ │←─────── 数据字(Word) ────────┘ │
│ │
│ 💡 问题：每个程序都必须知道自己将放在内存的哪个位置， │
│ 无法实现进程间的内存隔离和共享 │
│ │
└─────────────────────────────────────────────────────────────────────┘

1.2 虚拟寻址

现代系统使用虚拟寻址（Virtual Addressing） ：CPU 生成虚拟地址（Virtual Address，VA） ，通过内存管理单元（MMU，Memory Management Unit） 将虚拟地址转换为物理地址后，再访问内存。

┌─────────────────────────────────────────────────────────────────────┐
│ 虚拟寻址模型 │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ CPU ─────── 虚拟地址(VA) ──────→ MMU ─────── 物理地址(PA) ──────→ 内存
│ │ │ │
│ │←──────── 数据字(Word) ───────┘ │
│ │
│ 💡 MMU 使用存放在主存中的**页表**将虚拟地址翻译为物理地址 │
│ │
└─────────────────────────────────────────────────────────────────────┘

二、地址空间

地址空间（Address Space） 是一个非负整数地址的有序集合。系统中有两种地址空间：

💡 关键特性：虚拟地址空间通常比物理地址空间大得多。对于所有在该系统上运行的进程，虚拟地址空间的结构是相同的，这使得内存管理大大简化。

2.1 为什么需要虚拟内存？

虚拟内存解决了三个核心问题：

┌─────────────────────────────────────────────────────────────────────┐
│ 虚拟内存的三大价值 │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ 1. 作为缓存的工具 │
│ └─ 将主存视为磁盘的缓存，只把活动的虚拟页面缓存在物理内存中 │
│ │
│ 2. 简化内存管理 │
│ └─ 为每个进程提供一致的地址空间，隐藏物理内存和磁盘的细节 │
│ │
│ 3. 提供内存保护 │
│ └─ 隔离不同进程的地址空间，防止进程间相互破坏 │
│ │
└─────────────────────────────────────────────────────────────────────┘

三、虚拟内存作为缓存工具

3.1 虚拟页（VP）与物理页（PP）

从概念上，虚拟内存可以视为存储在磁盘上的字节序列。虚拟内存系统将地址空间划分为固定大小的虚拟页（VP，Virtual Page） ，物理内存划分为相同大小的物理页（PP，Physical Page） 。这些页面通常为 4KB~2MB。

虚拟页的状态分为三种：

3.2 页表（Page Table）

页表是虚拟地址到物理地址翻译的核心数据结构。它存放在主存中，每个进程拥有一个独立的页表。页表本质上是一个映射数组，将虚拟页号（VPN）映射到物理页号（PPN），并包含权限和存在信息。

┌─────────────────────────────────────────────────────────────────────┐
│ 页表结构示意图 │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ VPN (虚拟页号) PPN (物理页号) │
│ ┌─────────┐ ┌─────────┐ │
│ │ VP 0 │──────────→│ PP 0 │ 有效位=1（已缓存） │
│ ├─────────┤ ├─────────┤ │
│ │ VP 1 │──────────→│ PP 4 │ 有效位=1 │
│ ├─────────┤ ├─────────┤ │
│ │ VP 2 │──────────→│ 磁盘 │ 有效位=0（未缓存，在磁盘上） │
│ ├─────────┤ ├─────────┤ │
│ │ VP 3 │──────────→│ PP 2 │ 有效位=1 │
│ ├─────────┤ ├─────────┤ │
│ │ VP 4 │──────────→│ 无 │ 有效位=0（未分配） │
│ └─────────┘ └─────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────┘

💡 页表项（PTE，Page Table Entry） 包含物理页号（PPN）、有效位（valid bit）、访问权限位（读/写/执行权限）和其他管理位（脏位、引用位等）。

3.3 缺页异常（Page Fault）

当 CPU 引用一个有效位为 0 的虚拟页时，MMU 会触发缺页异常。缺页处理程序会：

┌─────────────────────────────────────────────────────────────────────┐
│ 缺页异常处理流程 │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ CPU 引用 VP 2（页表中有效位=0） │
│ │ │
│ ↓ │
│ MMU 触发缺页异常，控制权转交给内核的缺页处理程序 │
│ │ │
│ ↓ │
│ 缺页处理程序： │
│ ① 选择一个物理页作为牺牲页（如果已满） │
│ ② 将牺牲页写回磁盘（如果脏位=1） │
│ ③ 从磁盘读取 VP 2 到该物理页 │
│ ④ 更新页表（PPN + 有效位=1） │
│ │ │
│ ↓ │
│ 返回并**重新执行**引发缺页的指令 │
│ │ │
│ ↓ │
│ 这次页表命中，正常访问 │
│ │
└─────────────────────────────────────────────────────────────────────┘

3.4 DRAM 缓存的特殊设计

由于 DRAM 缓存（主存）和磁盘之间的速度差异极大（主存访问约 50-200ns，磁盘访问约 5-10ms，相差数万倍），DRAM 缓存的设计需要特殊考虑：

四、虚拟内存作为内存管理工具

虚拟内存为每个进程提供一致的地址空间，大大简化了链接和加载过程。

┌─────────────────────────────────────────────────────────────────────┐
│ 多个进程共享物理内存的页表映射 │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ 进程 1 的虚拟地址空间 物理内存 进程 2 的虚拟地址空间│
│ ┌─────────┐ ┌─────────┐ ┌─────────┐ │
│ │ VP 0 │───────────────→│ PP 0 │←────────│ VP 0 │ │
│ ├─────────┤ ├─────────┤ ├─────────┤ │
│ │ VP 1 │───────────────→│ PP 3 │←────────│ VP 1 │ │
│ ├─────────┤ ├─────────┤ ├─────────┤ │
│ │ VP 2 │──┐ │ PP 6 │←────────│ VP 2 │ │
│ ├─────────┤ │ ├─────────┤ ├─────────┤ │
│ │ VP 3 │ │ │ … │ │ VP 3 │ │
│ └─────────┘ └────────────→│ PP 9 │←────────│ VP 4 │ │
│ └─────────┘ └─────────┘ │
│ │
│ 💡 不同进程的相同虚拟地址可以映射到不同的物理地址， │
│ 实现内存隔离；也可以映射到相同的物理地址，实现内存共享 │
│ │
└─────────────────────────────────────────────────────────────────────┘

五、虚拟内存作为内存保护工具

页表项中的权限位实现了内存保护机制：

当程序违反权限规则时（例如向只读页面写入），MMU 会触发保护异常，导致段故障（Segmentation Fault），由内核处理或终止程序。

六、地址翻译——MMU 的核心工作

6.1 页命中时的地址翻译

┌─────────────────────────────────────────────────────────────────────┐
│ 页命中时的地址翻译流程 │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ CPU 生成虚拟地址 VA │
│ │ │
│ ↓ │
│ MMU 提取 VPN（虚拟页号）和 VPO（页内偏移） │
│ │ │
│ ↓ │
│ MMU 查询页表（在主存中）：检查 PTE 的有效位 │
│ │ │
│ ↓（有效位=1） │
│ MMU 从 PTE 中取出 PPN（物理页号） │
│ │ │
│ ↓ │
│ 构造物理地址 PA = (PPN << n) + VPO │
│ │ │
│ ↓ │
│ 发送 PA 到主存，获取数据并返回 CPU │
│ │
└─────────────────────────────────────────────────────────────────────┘

6.2 TLB——地址翻译的"加速器"

TLB（Translation Lookaside Buffer，翻译后备缓冲器） 是 MMU 中的一个硬件缓存，用于缓存最近使用的页表项。由于多级页表查找需要多次内存访问，TLB 能够大幅加速地址翻译过程。

┌─────────────────────────────────────────────────────────────────────┐
│ TLB 工作流程 │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ CPU 生成虚拟地址 VA │
│ │ │
│ ↓ │
│ TLB 查找（硬件，单周期） │
│ │ │
│ ├──→ TLB 命中 → 直接从 TLB 获取 PPN，构造 PA │
│ │ │
│ └──→ TLB 未命中 → MMU 访问主存中的页表（需要多次内存访问） │
│ │ │
│ ↓ │
│ 更新 TLB 缓存（逐出旧条目） │
│ │
└─────────────────────────────────────────────────────────────────────┘

💡 TLB 并行查询机制：利用虚拟地址页内偏移量不变的特性，可同步执行缓存访问与地址转换。现代处理器通过地址空间标识符（ASID） 区分不同进程的地址空间，减少任务切换时的 TLB 刷新次数。

6.3 多级页表

现代 64 位系统使用多级页表结构，以节省内存空间并支持大地址空间。

┌─────────────────────────────────────────────────────────────────────┐
│ 四级页表结构（x86-64） │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ VA (48位): [ 9 位 ][ 9 位 ][ 9 位 ][ 9 位 ][ 12 位 ] │
│ │ │ │ │ │ │
│ ↓ ↓ ↓ ↓ ↓ │
│ Level 1 Level 2 Level 3 Level 4 页内偏移 │
│ (PGD) (PUD) (PMD) (PTE) (12位) │
│ │ │ │ │ │
│ ↓ ↓ ↓ ↓ │
│ ┌───┐ ┌───┐ ┌───┐ ┌───┐ │
│ │表 │→ │表 │→ │表 │→ │表 │→ 物理页 │
│ └───┘ └───┘ └───┘ └───┘ │
│ │
│ 💡 多级页表的优势： │
│ • 节省内存——未使用的虚拟地址区域无需分配下级页表 │
│ • 每个进程只需维护顶级页表（在 CR3 寄存器中） │
│ │
└─────────────────────────────────────────────────────────────────────┘

七、案例研究：Intel Core i7 地址翻译

Intel Core i7 处理器采用四级页表结构，支持 48 位虚拟地址和 52 位物理地址。

┌─────────────────────────────────────────────────────────────────────┐
│ Intel Core i7 地址翻译完整流程 │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ CPU 生成 48 位虚拟地址 VA（48 位） │
│ │ │
│ ↓ │
│ ┌─────────────────────────────────────────────────────────────┐ │
│ │ TLB 查找（32 条目 L1 dTLB + 64 条目 L2 TLB） │ │
│ │ │ │ │
│ │ ├── 命中 → 直接得到物理地址 │ │
│ │ │ │ │
│ │ └── 未命中 → 硬件页表遍历（Page Walker） │ │
│ └─────────────────────────────────────────────────────────────┘ │
│ │ │
│ ↓ │
│ 硬件页表遍历： │
│ • 从 CR3 寄存器读取 L1 页表基址 │
│ • 依次访问 L1→L2→L3→L4 页表 │
│ • 每次访问可能触发缺页异常 │
│ │ │
│ ↓ │
│ 得到物理地址，访问 L1/L2/L3 缓存，最后访问主存 │
│ │
└─────────────────────────────────────────────────────────────────────┘

八、内存映射（Memory Mapping）

8.1 mmap 系统调用

内存映射将虚拟内存区域与磁盘上的对象关联起来。Linux 提供了 mmap 系统调用来创建内存映射：

#include <sys/mman.h>

void *mmap(void *addr, size_t len, int prot, int flags, int fd, off_t offset);

参数说明：

8.2 mmap 使用示例

// mmap 示例：将文件映射到内存
#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>

int main() {
int fd = open("test.txt", O_RDWR);
if (fd == –1) {
perror("open");
exit(1);
}

struct stat sb;
if (fstat(fd, &sb) == –1) {
perror("fstat");
exit(1);
}

// 将文件映射到内存
char *data = mmap(NULL, sb.st_size, PROT_READ | PROT_WRITE,
MAP_SHARED, fd, 0);
if (data == MAP_FAILED) {
perror("mmap");
exit(1);
}

// 直接访问内存中的数据（如同操作数组）
printf("File content: %s\\n", data);

// 修改映射区域（会写回文件）
data[0] = 'X';

// 同步到磁盘
msync(data, sb.st_size, MS_SYNC);

// 解除映射
munmap(data, sb.st_size);
close(fd);
return 0;
}

8.3 共享内存与匿名映射

共享内存映射（MAP_SHARED） ：写操作立即反映到文件，其他进程可见，适用于进程间通信。

私有映射（MAP_PRIVATE） ：写操作在内存中进行，不写回文件，通过写时复制（Copy-on-Write，COW） 实现。

匿名映射（MAP_ANONYMOUS） ：没有对应的文件，初始化为零，常用于分配大块内存。

// 匿名映射示例（父子进程共享内存）
#include <sys/mman.h>
#include <unistd.h>
#include <stdio.h>

int main() {
// 创建匿名映射（共享）
int *shared = mmap(NULL, sizeof(int),
PROT_READ | PROT_WRITE,
MAP_SHARED | MAP_ANONYMOUS,
–1, 0);
if (shared == MAP_FAILED) {
perror("mmap");
return 1;
}

*shared = 42;

pid_t pid = fork();
if (pid == 0) {
// 子进程：修改共享内存
printf("Child: shared = %d\\n", *shared);
*shared = 100;
printf("Child changed shared to %d\\n", *shared);
} else {
// 父进程：等待子进程，读取共享内存
wait(NULL);
printf("Parent: shared = %d\\n", *shared);
}

munmap(shared, sizeof(int));
return 0;
}

九、动态内存分配（malloc）

动态内存分配器管理进程的堆（heap），这是 malloc 实验的核心内容。

9.1 基本概念

动态内存分配器维护着进程的虚拟内存区域——堆。堆是一段连续的虚拟内存空间，起始位置由 brk 指针指向。

┌─────────────────────────────────────────────────────────────────────┐
│ 堆结构 │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ 低地址 高地址 │
│ ┌─────────────────────────────────────────────────────────────┐ │
│ │ 已初始化数据 │ 未初始化数据 │ 堆 ↓ │ 空闲 │ ↑ 栈 │ │
│ │ (.data) │ (.bss) │ │ │ │ │
│ └─────────────────────────────────────────────────────────────┘ │
│ ▲ ▲ │
│ │ │ │
│ └── program break (brk) └── 堆顶 │
│ │
└─────────────────────────────────────────────────────────────────────┘

分配器将堆视为一组不同大小的块（block）的集合。每个块要么是已分配的（allocated），供应用程序使用；要么是空闲的（free），可用于未来的分配。

9.2 块结构设计

┌─────────────────────────────────────────────────────────────────────┐
│ 内存块结构 │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ ┌─────────┬─────────────────────┬─────────┐ │
│ │ 头部 │ 载荷 │ 尾部 │ │
│ │ (4字节) │ (payload) │ (4字节) │ │
│ └─────────┴─────────────────────┴─────────┘ │
│ ↑ ↑ │
│ └── 块大小 + 分配位 └── 块大小 + 分配位 │
│ │
│ 💡 头部和尾部内容完全一致。引入尾部是为了实现常数时间复杂度的 │
│ 反向访问——合并空闲块时，需要知道前一个块的状态 │
│ │
└─────────────────────────────────────────────────────────────────────┘

头部/尾部的位设计：

#define WSIZE 4 // 字大小（字节）
#define DSIZE 8 // 双字大小（字节）

// 打包：将大小和分配位合并到一个字中
#define PACK(size, alloc) ((size) | (alloc))

// 读取头部或尾部
#define GET(p) (*(unsigned int *)(p))
#define PUT(p, val) (*(unsigned int *)(p) = (val))

// 提取大小和分配位
#define GET_SIZE(p) (GET(p) & ~0x7) // 低3位清零
#define GET_ALLOC(p) (GET(p) & 0x1) // 最低位

💡 为什么低位可以用于分配位：由于块需要 8 字节对齐，块大小的低 3 位必定为 0，可以安全地用于存储其他信息（如分配位）。

9.3 空闲块组织结构

① 隐式空闲链表（Implicit Free List）

隐式空闲链表将空闲块通过块头部中的大小字段隐含地连接在一起。每次分配时，需要遍历所有块（包括已分配块）来找到合适的空闲块。

┌─────────────────────────────────────────────────────────────────────┐
│ 隐式空闲链表 │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ ┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐ │
│ │ 头│ 载荷 │ │ 头│ 载荷 │ │ 头│ 载荷 │ │ 头│ 载荷 │ │
│ │ 尾│ │ │ 尾│ │ │ 尾│ │ │ 尾│ │ │
│ └─────────┘ └─────────┘ └─────────┘ └─────────┘ │
│ ▲ ▲ ▲ ▲ │
│ │ │ │ │ │
│ └──────────────┴──────────────┴──────────────┘ │
│ 通过顺序扫描遍历所有块 │
│ │
│ 💡 特点： │
│ • 实现简单 │
│ • 分配时间与堆块总数成线性关系 │
│ • 适合作为 baseline │
│ │
└─────────────────────────────────────────────────────────────────────┘

② 显式空闲链表（Explicit Free List）

显式空闲链表在空闲块中增加 prev 和 next 指针，将所有空闲块单独串联起来。这样分配时只需遍历空闲块，无需遍历已分配块。

┌─────────────────────────────────────────────────────────────────────┐
│ 显式空闲链表 │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ ┌─────────────────────────────────────────────────────────────┐ │
│ │ 空闲块 │ │
│ │ ┌──────┬──────┬──────┬──────────────────┬──────┐ │ │
│ │ │ 头部 │ prev │ next │ 载荷 │ 尾部 │ │ │
│ │ └──────┴──────┴──────┴──────────────────┴──────┘ │ │
│ │ ↑ ↑ ↑ │ │
│ │ │ └── 指向前一个空闲块 └── 指向后一个空闲块 │ │
│ │ └── 大小 + 分配位 │ │
│ └─────────────────────────────────────────────────────────────┘ │
│ │
│ 空闲块通过指针连接： │
│ ┌─────┐ ┌─────┐ ┌─────┐ │
│ │空闲1│←──→│空闲2│←──→│空闲3│ │
│ └─────┘ └─────┘ └─────┘ │
│ │
│ 💡 特点：分配时间与空闲块数量成正比，效率更高 │
│ │
└─────────────────────────────────────────────────────────────────────┘

③ 分离适配（Segregated Fit）——C 标准库的实现方案

分离适配是现代分配器（如 glibc malloc）使用的主流方案。它维护多个空闲链表，每个链表与一个大小类相关联。

┌─────────────────────────────────────────────────────────────────────┐
│ 分离适配结构 │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ 大小类 → 空闲链表 │
│ │
│ ┌─────────────┐ │
│ │ size < 16 │──→ 空闲块1 ──→ 空闲块2 │
│ ├─────────────┤ │
│ │ 16 ≤ size < 32 │──→ 空闲块1 ──→ 空闲块2 ──→ 空闲块3 │
│ ├─────────────┤ │
│ │ 32 ≤ size < 64 │──→ 空闲块1 │
│ ├─────────────┤ │
│ │ … │ │
│ └─────────────┘ │
│ │
│ 分配策略： │
│ • 先根据请求大小找到对应的大小类 │
│ • 在该链表中查找合适的空闲块 │
│ • 如果找不到，从更大类中分配 │
│ │
│ 💡 结合了显式链表（快速查找）和最佳适配（减少碎片）的优势 │
│ │
└─────────────────────────────────────────────────────────────────────┘

9.4 放置策略

9.5 合并策略

当释放一个块时，需要检查相邻块是否为空闲块，并进行合并（coalescing）。

合并策略：

• 立即合并：释放后立即与相邻空闲块合并（实现简单）
• 延迟合并：在找不到合适块时再进行合并（吞吐率可能更高）

9.6 内部碎片 vs 外部碎片

9.7 malloc 常见陷阱

// 陷阱1：忘记检查 malloc 返回值
int *p = malloc(n * sizeof(int));
*p = 0; // 如果 p == NULL 则崩溃

// 陷阱2：内存泄漏
p = malloc(100);
p = malloc(200); // 第一个 100 字节的指针丢失，无法释放

// 陷阱3：读未初始化的内存
int *p = malloc(100);
int x = *p; // p 指向的内存未被初始化

// 陷阱4：缓冲区溢出
int *p = malloc(4 * sizeof(int));
p[4] = 0; // 写入超出分配边界

// 陷阱5：使用已释放的内存
free(p);
int x = *p; // 悬垂指针，未定义行为

// 陷阱6：重复释放
free(p);
free(p); // double free，可能导致程序崩溃

十、配套实验：Malloc Lab

Malloc Lab 是 CSAPP 中难度最高的实验之一。它要求实现一个动态内存分配器，包含以下四个核心函数：

10.1 核心代码框架

// mm.h 中的定义
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#include "mm.h"
#include "memlib.h"

/* 基本常量 */
#define WSIZE 4 // 字大小（字节）
#define DSIZE 8 // 双字大小（字节）
#define CHUNKSIZE (1<<12) // 堆扩展大小（4096 字节）

/* 宏定义 */
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define PACK(size, alloc) ((size) | (alloc))
#define GET(p) (*(unsigned int *)(p))
#define PUT(p, val) (*(unsigned int *)(p) = (val))
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)
#define HDRP(bp) ((char *)(bp) – WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) – DSIZE)
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) – WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp) – GET_SIZE(((char *)(bp) – DSIZE)))

static char *heap_listp; // 指向堆的起始位置

/* 辅助函数声明 */
static void *extend_heap(size_t words);
static void *coalesce(void *bp);
static void *first_fit(size_t asize);
static void place(void *bp, size_t asize);

10.2 初始化实现

int mm_init(void) {
// 创建初始堆空间（对齐到双字边界）
if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)–1)
return –1;

PUT(heap_listp, 0); // 对齐填充
PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1)); // 序言块头部
PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1)); // 序言块尾部
PUT(heap_listp + (3 * WSIZE), PACK(0, 1)); // 结尾块

heap_listp += (2 * WSIZE); // 指向序言块载荷起始位置

// 扩展堆空间
if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
return –1;
return 0;
}

static void *extend_heap(size_t words) {
char *bp;
size_t size = words * WSIZE; // 转换为字节数

// 扩展堆
if ((long)(bp = mem_sbrk(size)) == –1)
return NULL;

// 设置新空闲块的头部和尾部
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); // 新的结尾块

// 合并相邻空闲块
return coalesce(bp);
}

10.3 malloc 实现

void *mm_malloc(size_t size) {
size_t asize; // 调整后的块大小
size_t extendsize; // 需要扩展的大小
char *bp;

if (size == 0)
return NULL;

// 调整块大小（包含头部+尾部，对齐到双字边界）
if (size <= DSIZE)
asize = 2 * DSIZE;
else
asize = DSIZE * ((size + DSIZE + (DSIZE – 1)) / DSIZE);

// 查找合适的空闲块
if ((bp = first_fit(asize)) != NULL) {
place(bp, asize);
return bp;
}

// 未找到合适块，扩展堆
extendsize = MAX(asize, CHUNKSIZE);
if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
return NULL;
place(bp, asize);
return bp;
}

10.4 free 与合并实现

void mm_free(void *bp) {
size_t size = GET_SIZE(HDRP(bp));

// 标记为空闲
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));

// 合并相邻空闲块
coalesce(bp);
}

static void *coalesce(void *bp) {
size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
size_t size = GET_SIZE(HDRP(bp));

// 四种情况
if (prev_alloc && next_alloc) {
// 前后都已分配，无需合并
return bp;
} else if (prev_alloc && !next_alloc) {
// 仅与后一个空闲块合并
size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
} else if (!prev_alloc && next_alloc) {
// 仅与前一个空闲块合并
size += GET_SIZE(HDRP(PREV_BLKP(bp)));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
bp = PREV_BLKP(bp);
} else {
// 前后都是空闲块，合并三者
size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
bp = PREV_BLKP(bp);
}
return bp;
}

10.5 优化建议

Malloc Lab 的性能评估基于两个指标：

优化技巧：

评分公式：

[
P = wU + (1 – w) \\times \\min\\left(1, \\frac{T}{T_{\\text{libc}}}\\right)
]

其中 U 为空间利用率，T 为吞吐率，w 默认取 0.6。评分机制平衡了内存利用率和执行速度。

十一、本章知识点思维导图

第 9 章 虚拟存储器
│
├── 1. 虚拟内存基础
│ ├── 物理寻址 vs 虚拟寻址
│ ├── 地址空间（虚拟地址空间、物理地址空间）
│ └── 虚拟内存三大功能（缓存、简化管理、保护）
│
├── 2. 虚拟内存作为缓存
│ ├── 虚拟页（VP）与物理页（PP）
│ ├── 页表（Page Table）
│ ├── 缺页异常（Page Fault）
│ └── DRAM 缓存特性（大页、全相联、写回）
│
├── 3. 地址翻译
│ ├── MMU（内存管理单元）
│ ├── TLB（翻译后备缓冲器）
│ ├── 多级页表（四级页表结构）
│ └── Core i7 案例
│
├── 4. 内存映射
│ ├── mmap 系统调用
│ ├── 共享映射（MAP_SHARED）
│ ├── 私有映射（MAP_PRIVATE，写时复制）
│ └── 匿名映射（MAP_ANONYMOUS）
│
├── 5. 动态内存分配
│ ├── 堆与 brk 指针
│ ├── 块结构（头部、尾部、载荷）
│ ├── 空闲块组织结构
│ │ ├── 隐式空闲链表
│ │ ├── 显式空闲链表
│ │ └── 分离适配
│ ├── 放置策略（首次/下一次/最佳适配）
│ ├── 合并策略（立即/延迟合并）
│ └── 碎片（内部/外部）
│
└── 6. Malloc Lab
├── 实验要求（mm_init, malloc, free, realloc）
├── 辅助函数（extend_heap, coalesce, first_fit, place）
└── 优化技巧（显式链表、分离适配、realloc 优化）

十二、本章小结

第 9 章深入计算机系统最核心的内存管理机制，从虚拟地址到物理地址的翻译，从 malloc 到垃圾收集，构建了完整的内存管理知识体系：

💡 本章最核心的三个洞察：

🔜 下一篇预告

下一章我们将进入 第 10 章：系统级 I/O。

这一章将揭开操作系统输入/输出（I/O）系统的底层机制：

• 📌 Unix I/O 基础：文件描述符、open/close/read/write 系统调用
• 📌 文件类型与权限：普通文件、目录、符号链接、套接字等
• 📌 重定向：dup2 与文件描述符的复制
• 📌 标准 I/O 库：stdio 与 Unix I/O 的关系与区别
• 📌 RIO 包：Robust I/O 的实现
• 📌 文件元数据：stat、access、lseek 等
• 📌 I/O 重定向：shell 中的管道和重定向机制

第 10 章将帮助我们理解 I/O 系统的本质，区分标准 I/O 与系统调用的差异，并掌握编写健壮 I/O 代码的技巧。

敬请期待！

本文为个人学习笔记，仅用于知识分享。如有错误，欢迎指正。
👍🏻 点赞 + 收藏 + 分享，让更多开发者看到这篇深度解析！❤️ 如果觉得有用，请给个赞支持一下作者！