本章讨论内存管理系统（如 malloc 库或操作系统分段管理）中的空闲空间管理（Free-space Management）。
当空闲空间由不同大小的单元构成时，会出现外部碎片（External Fragmentation）：空闲空间被分割成许多不连续的小块，导致即使总空闲空间足够，也无法满足较大的连续分配请求。
核心问题如何高效管理变长的分配请求？采用什么策略能最小化碎片，并平衡时间和空间开销？
核心假设
本章主要讨论用户级内存分配库（如 malloc 和 free）的空闲空间管理，并基于以下假设：
- 基本接口：
malloc(size)请求指定字节空间并返回指针；free(ptr)释放空间。库必须能仅凭指针推断出内存块大小。 - 空闲列表（Free List）：用于追踪堆中所有空闲内存块的数据结构。
- 关注外部碎片：主要解决外部碎片问题。虽然分配过大块会导致内部碎片（已分配块内部的浪费），但本章重点在于如何避免无法满足连续分配请求。
- 不可重定位：一旦内存分配给程序，其位置固定，库无法通过**紧凑（Compaction）**操作来减少碎片。
- 固定区域：假设分配程序管理的是一块大小固定的连续字节区域。
底层机制
在深入策略之前，需要理解分配程序的三个通用机制：分割、合并以及空间追踪。
分割与合并（Splitting and Coalescing）
空闲列表（Free List）记录堆中未分配的区域。
- 分割（Splitting）：当请求的空间小于某个空闲块时，分配程序将该块分割，一部分返回给用户，剩余部分留在空闲列表中。
- 示例：在 10 字节的空闲块中申请 1 字节，该块起始地址由 20 变为 21，长度变为 9。
- 合并（Coalescing）：当释放内存时，如果新归还的空间与原有的空闲块地址相邻，分配程序会将它们合并为一个较大的连续空闲块，以解决“假碎片”问题。
- 示例：释放中间 10 字节后，若不合并会产生三个 10 字节碎片；合并后则恢复为 30 字节的连续空间。
追踪已分配空间的大小
free(ptr) 接口不包含大小参数，因此库需要通过**头块（Header）**来追踪分配信息。头块通常存放在返回给用户的内存块之前。
- 头块内容：至少包含内存块的大小，通常还包含一个**幻数（Magic Number）**用于完整性检查。
typedef struct header_t {
int size;
int magic;
} header_t; - 释放流程：调用
free(ptr)时，库通过指针运算找到头块，验证幻数并获取块大小。
void free(void *ptr) {
header_t *hptr = (void *)ptr - sizeof(header_t);
}
额外开销实际释放和分配的空间是“用户请求大小 + 头块大小”。这意味着头块会带来一定的空间开销。
嵌入空闲列表
在内存分配库中，无法通过 malloc() 来创建空闲列表节点。相反，我们需要在空闲空间内部建立列表。
1. 初始化
假设有一个 4KB 的堆（通过 mmap() 获取），我们需要在其中初始化第一个空闲节点。
typedef struct node_t {
int size;
struct node_t *next;
} node_t;
// 初始化堆：将第一个空闲节点嵌入空闲空间起始处
node_t *head = mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0);
head->size = 4096 - sizeof(node_t);
head->next = NULL;2. 分配与分割
当请求 100 字节时，库会找到足够的空闲块并进行分割：
- 分配 108 字节（100 字节数据 + 8 字节头块）。
- 剩余空间更新为一个新的
node_t，留在空闲列表中。
3. 释放与碎片化
当内存被释放时，库将释放的块插回空闲列表。如果没有 合并（Coalescing） 机制，空闲列表会变得非常破碎。
4. 合并
通过遍历列表并合并物理地址相邻的块，可以将破碎的堆重新恢复为连续的整体。
让堆增长
当堆空间耗尽时，分配程序通常有两种选择：
- 返回失败：返回
NULL指针。 - 向操作系统申请更多空间：大多数系统支持通过系统调用（如 UNIX 中的
sbrk）来增加堆的大小。操作系统会映射新的物理内存页到进程地址空间，分配程序随后将新空间纳入空闲列表管理。
基本策略
理想的分配程序应兼顾速度与碎片最小化。以下是几种常见的空闲空间搜索策略：
| 策略 | 描述 | 优点 | 缺点 |
|---|---|---|---|
| 最优匹配 (Best Fit) | 遍历列表，选择能满足请求且最小的空闲块。 | 尽量减少空间浪费。 | 遍历开销大；容易产生大量微小碎片。 |
| 最差匹配 (Worst Fit) | 遍历列表，选择最大的空闲块进行分割。 | 剩余块较大，可能更有用。 | 遍历开销大；研究表明碎片化严重。 |
| 首次匹配 (First Fit) | 找到第一个足够大的块即返回。 | 查找速度快。 | 列表开头容易堆积小碎片。 |
| 下次匹配 (Next Fit) | 类似首次匹配，但从上次查找结束的位置开始。 | 查找负载均匀分布。 | 性能与首次匹配接近。 |
策略示例
假设空闲列表包含 10、30、20 字节的块，请求 15 字节：
- 最优匹配：选择 20 字节块，剩余 5 字节。
- 最差匹配：选择 30 字节块，剩余 15 字节。
- 首次匹配：在本例中也会选择 30 字节块（第一个满足条件的块），但查找开销更低。
其他方式
除了基本策略，还有一些更高级的技术来优化分配性能和简化合并。
分离空闲列表（Segregated List）
- 核心思想：为频繁申请的特定大小的对象维护独立的空闲列表。
- 优点：分配和释放极快；在该特定大小范围内无碎片。
- Slab Allocator：Solaris 中的厚块分配程序。它在内核启动时为常用对象（如 inode）创建对象缓存。当缓存不足时，向通用分配程序申请“厚块（slab）”；当 slab 内对象引用归零时，回收空间。此外，它通过保持对象在“预初始化”状态来降低开销。
伙伴系统（Buddy System）
- 二分伙伴分配程序：空闲空间被视为 的大块。
- 分配流程：递归地将块一分为二，直到刚好满足请求大小。
- 示例：64KB 空间切分以满足 7KB 请求（最终分配 8KB）。
- 合并流程：释放块时，检查其“伙伴”块是否也空闲。如果是，则合并并继续递归上溯。
- 优点：合并极其简单（伙伴块地址仅有一位不同）。
- 缺点：由于只能分配 2 的幂次大小，存在内部碎片。
其他优化方向
- 可扩展性：使用平衡二叉树、伸展树等复杂数据结构加速查找。
- 多核支持：针对多线程环境优化分配程序，减少锁竞争。
小结
内存分配程序需要在速度、空间效率和可扩展性之间进行权衡。了解具体的工作负载有助于选择或调整最合适的分配策略。在现代多核系统中，构建高效的分配程序仍是挑战。