空闲空间管理

1. 引言：核心问题

背景: 内存管理系统（如 malloc 库管理堆内存、操作系统管理地址空间）都需要解决如何管理空闲内存的问题。
挑战: 当需要管理的空闲空间由大小不同的单元组成时（区别于固定大小单元的简单管理），管理变得复杂。
核心问题: 外部碎片 (External Fragmentation)
- 定义: 空闲内存被分割成许多小块，导致即使总空闲空间足够大，也可能没有一个连续的大块来满足较大的内存请求。
- 例子: 总空闲 20 字节，但分成两个 10 字节块，无法满足 15 字节的请求。
本章目标: 探讨如何管理空闲空间以满足变长分配请求，分析不同策略在最小化碎片、时间开销和空间开销方面的优劣。

2. 基本假设

为了简化讨论，做出以下假设：

接口: 类似于 C 库的 malloc(size) 和 free(ptr)。
- malloc: 请求指定大小 size 的内存，返回一个 void * 指针。
- free: 接收指针 ptr，释放对应的内存块。关键: free 不需知道大小，库必须自行记录。
管理区域: 管理的空间称为 堆 (Heap)。
数据结构: 追踪空闲块的数据结构称为 空闲列表 (Free List) (不一定是链表)。
主要关注: 外部碎片（内部碎片，即分配块大于请求大小导致的浪费，暂不作为重点）。
不可移动: 一旦内存分配给用户，分配库不能移动它（无法进行紧凑 Compaction 来整理碎片）。注：OS 在某些情况（如分段）下可能可以进行紧凑。
区域大小: 假设管理的内存区域是连续的，并且初始大小固定（尽管现实中可能通过 sbrk 等方式增长）。

3. 底层机制

内存分配器常用的基本操作和技术：

3.1 分割 (Splitting)

场景: 当找到的空闲块大于请求的大小时。
操作: 将该空闲块分割成两部分：
1. 一块满足用户请求（可能加上头块大小），返回给用户。
2. 另一块（剩余部分）继续留在空闲列表中。
目的: 避免因分配小块而浪费整个大块。

3.2 合并 (Coalescing)

场景: 当调用 free() 释放一块内存时。
操作: 检查被释放块的相邻内存块（物理地址上相邻）是否也空闲。
- 如果相邻块空闲，则将它们合并成一个更大的空闲块。
- 可能合并前一个块、后一个块，或者前后两个块。
目的: 减少碎片，尽可能恢复大的连续空闲空间。

3.3 追踪已分配空间 (Tracking Allocated Space)

问题: free(ptr) 如何知道要释放多大空间？
解决方案: 在分配给用户的内存块之前，存储一个 头块 (Header)。
头块内容:
- 必需: 已分配区域的大小（包括用户请求的大小 + 头块自身大小）。
- 可选: 指向空闲列表的指针（加速查找）、魔数 (Magic Number) 用于完整性检查、状态位等。
free() 操作:
1. 通过指针运算 (void *)ptr - sizeof(header_t) 找到头块地址。
2. 读取头块中的大小信息。
3. （可选）检查魔数。
4. 将整个块（头块 + 用户空间）标记为空闲并尝试合并。
malloc() 注意: 请求 N 字节时，实际需要寻找 N + sizeof(header_t) 大小的空闲块。

3.4 嵌入空闲列表 (Embedding the Free List)

问题: 如何存储空闲列表本身？不能调用 malloc 来创建节点。
解决方案: 利用空闲块自身的空间来存储空闲列表的节点信息。
实现:
- 定义一个节点结构 (e.g., struct node_t { int size; struct node_t *next; })。
- 将这个结构放置在每个空闲块的起始位置。
- size 字段存储该空闲块的（可用）大小。
- next 字段指向下一个空闲块的起始地址（即下一个 node_t 的地址）。
初始化: 整个堆开始时是一个大的空闲块，包含一个 node_t，next 为 NULL。
分配/释放: 更新节点信息，调整链表结构。

3.5 堆增长 (Heap Growth)

场景: 当现有堆空间不足以满足分配请求时。
常见机制: 调用系统调用（如 Unix/Linux 的 sbrk 或 mmap）向操作系统请求更多内存。
OS 操作: 找到空闲物理页，映射到进程的虚拟地址空间，扩展堆的边界。
结果: 分配器获得更大的内存区域进行管理。

4. 基本分配策略

选择哪个空闲块来满足请求的策略：

4.1 最优匹配 (Best Fit)

策略: 遍历整个空闲列表，找到大小最接近且不小于请求大小的空闲块。
优点: 试图减少大块被小请求分割后剩余的碎片大小。
缺点:
- 性能开销: 需要扫描整个列表，较慢。
- 碎片: 容易产生大量非常小的、难以利用的碎片。

4.2 最差匹配 (Worst Fit)

策略: 遍历整个空闲列表，找到最大的空闲块进行分配。
优点: 试图保留较大的剩余块，可能对后续大请求有利。
缺点:
- 性能开销: 需要扫描整个列表，较慢。
- 碎片: 实践证明性能通常很差，容易快速耗尽大块，导致外部碎片化严重。

4.3 首次匹配 (First Fit)

策略: 从列表头开始查找，使用第一个找到的足够大的空闲块。
优点:
- 速度快: 平均情况下不需要扫描整个列表。
缺点:
- 碎片: 容易在列表开头积累大量小碎片，导致后续查找时间增加。
优化: 按地址排序空闲列表，有助于简化合并操作。

4.4 下次匹配 (Next Fit)

策略: 类似于首次匹配，但维护一个指针记录上次查找结束的位置，下次查找从该位置开始。
优点:
- 试图将查找分布到整个列表，避免集中在开头。
- 性能通常接近首次匹配。
缺点: 性能和碎片情况有时不如首次匹配。

5. 进阶方法与考量

除了基本策略，还有更复杂的技术：

5.1 分离空闲列表 (Segregated Lists)

思想: 为特定大小（通常是频繁请求的大小）的对象维护单独的空闲列表。
优点:
- 速度快: 对于特定大小的请求，分配/释放非常快（通常 O(1)）。
- 减少碎片: 对于这些特定大小，几乎没有外部碎片问题。
实现例子: 厚块分配器 (Slab Allocator) (Jeff Bonwick, Solaris)
- 为常用内核对象（如锁、inode）创建对象缓存 (object cache)。
- 每个缓存管理特定大小对象的空闲列表。
- 缓存从通用内存分配器获取厚块 (slab)（通常是页的倍数）。
- 预初始化: Slab 中的对象可以保持初始化状态，避免重复构造/析构开销。
- 内存回收: 当 Slab 中所有对象都空闲时，可以将 Slab 归还给通用分配器。
挑战: 如何确定哪些大小需要分离列表？为每个列表分配多少内存？

5.2 伙伴系统 (Buddy System)

思想: 将内存按 2 的幂次方大小进行管理。
分配:
- 从概念上将整个内存视为大小为 2^N 的块。
- 请求内存时，递归地将块对半分割，直到找到满足请求的最小 2^k 大小的块（2^k >= 请求大小）。
释放:
- 释放块时，检查其伙伴 (buddy)（地址只有一位不同的、大小相同的相邻块）是否也空闲。
- 如果伙伴空闲，则合并成一个 2^k+1 大小的块。
- 递归向上合并，直到无法合并或达到最大块。
优点:
- 快速合并: 伙伴地址计算简单（位运算）。
缺点:
- 内部碎片: 由于只能分配 2 的幂次方大小，请求大小会被向上取整，导致块内浪费。

5.3 性能与扩展性 (Performance and Scalability)

挑战:
- 查找速度: 简单的线性列表扫描在大内存/多请求下可能很慢 (O(N))。
- 多线程/多核: 在并发环境下，需要锁来保护全局数据结构（如空闲列表），可能成为性能瓶颈。
改进:
- 高级数据结构: 使用平衡二叉树、伸展树、跳表等更复杂的数据结构来管理空闲列表，加速查找（通常 O(log N)）。
- 并发优化:
  - 使用更细粒度的锁。
  - 采用线程缓存 (Thread-local Caches) 或 CPU 缓存 (Per-CPU Caches)，让每个线程/CPU 优先在自己的小缓存中分配/释放，减少全局锁竞争。现代分配器（如 tcmalloc, jemalloc）广泛使用此类技术。

6. 总结

空闲空间管理是内存分配的核心，尤其在处理变长请求时面临外部碎片的挑战。
基本机制（分割、合并、头块、嵌入列表）是构建分配器的基础。
基本策略（最优、最差、首次、下次匹配）各有优劣，存在速度和碎片化的权衡。
高级技术（分离列表、伙伴系统、复杂数据结构、并发优化）旨在提高性能、减少碎片和提升可扩展性。
没有银弹: 不存在适用于所有场景的“最佳”策略。选择和调优分配器通常需要考虑具体的工作负载（分配/释放模式、大小分布等）。
构建一个通用、快速、空间高效且可扩展的内存分配器仍然是一个复杂且持续演进的系统工程问题。