如果要管理的空闲空间由大小不同的单元构成，管理就变得困难（而且有趣）。这种情况出现在用户级的内存分配库（如 malloc()和 free()），或者操作系统用分段（segmentation）的方式实现虚拟内存。在这两种情况下，出现了外部碎片（external fragmentation）的问题：空闲空间被分割成不同大小的小块，成为碎片，后续的请求可能失败，因为没有一块足够大的连续空闲空间，即使这时总的空闲空间超出了请求的大小。
上面展示了该问题的一个例子。在这个例子中，全部可用空闲空间是 20 字节，但被切成两个 10 字节大小的碎片，导致一个 15 字节的分配请求失败。所以本章需要解决的问题是：
关键问题：如何管理空闲空间 要满足变长的分配请求，应该如何管理空闲空间？什么策略可以让碎片最小化？不同方法的时间和空间开销如何？
假设
- 通过 malloc()和 free()在堆上分配和释放内存
- 只有外部碎片
- 内存一旦被分配给客户，就不可以被重定位到其他位置
底层机制
分割与合并
空闲列表包含一组元素，记录了堆中的哪些空间还没有分配。假设有下面的 30 字节的堆：
这个堆对应的空闲列表会有两个元素，一个描述第一个10字节的空闲区域（字节0～9），一个描述另一个空闲区域（字节 20～29）：
分割（splitting）动作：它找到一块可以满足请求的空闲空间，将其分割，第一块返回给用户，第二块留在空闲列表中。在我们的例子中，假设这时遇到申请一个字节的请求，分配程序选择使用第二块空闲空间，对 malloc()的调用会返回 20（1 字节分配区域的地址），空闲列表会变成这样：
分配程序会在释放一块内存时合并可用空间。想法很简单：在归还一块空闲内存时，仔细查看要归还的内存块的地址以及邻它的空闲空间块。如果新归还的空间与一个原有空闲块相邻（或两个，就像这个例子），就将它们合并为一个较大的空闲块。
通过合并，最后空闲列表应该像这样：
通过合并，分配程序可以更好地确保大块的空闲空间能提供给应用程序。
追踪已分配空间的大小
你可能注意到，free(void *ptr)接口没有块大小的参数。因此它是假定，对于给定的指针，内存分配库可以很快确定要释放空间的大小，从而将它放回空闲列表。
要完成这个任务，大多数分配程序都会在头块（header）中保存一点额外的信息，它在内存中，通常就在返回的内存块之前。
头块中至少包含所分配空间的大小（也可能包含一些额外的指针来加速空间释放，包含一个幻数来提供完整性检查，以及其他信息。我们假定，一个简单的头块包含了分配空间的大小和一个幻数：
typedef struct header_t {
int size;
int magic;
} header_t;用户调用 free(ptr)时，库会通过简单的指针运算得到头块的位置：
void free(void *ptr) {
header_t *hptr = (void *)ptr - sizeof(header_t);
}
获得头块的指针后，库可以很容易地确定幻数是否符合预期的值，作为正常性检查（assert（hptr->magic == 1234567）），并简单计算要释放的空间大小（即头块的大小加区域长度）。请注意前一句话中一个小但重要的细节：实际释放的是头块大小加上分配给用户的空间的大小。因此，如果用户请求 N 字节的内存，库不是寻找大小为 N 的空闲块，而是寻找N 加上头块大小的空闲块。
嵌入空闲列表
假设我们需要管理一个 4096 字节的内存块（即堆是 4KB）。为了将它作为一个空闲空间列表来管理，首先要初始化这个列表。开始，列表中只有一个条目，记录了大小为 4096的空间（减去头块的大小）。下面是该列表中一个节点描述：
typedef struct node_t {
int size;
struct node_t *next;
} node_t;现在来看一些代码，它们初始化堆，并将空闲列表的第一个元素放在该空间中。假设堆构建在某块空闲空间上，这块空间通过系统调用 mmap()获得。这不是构建这种堆的唯一选择，但在这个例子中很合适。下面是代码：
// mmap() returns a pointer to a chunk of free space
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;执行这段代码之后，列表的状态是它只有一个条目，记录大小为 4088。head 指针指向这块区域的起始地址，假设是 16KB（尽管任何虚拟地址都可以）。堆看起来如图 17.3 所示。 现在，假设有一个 100 字节的内存请求。为了满足这个请求，库首先要找到一个足够大小的块。因为只有一个 4088 字节的块，所以选中这个块。然后，这个块被分割（split）为两块：一块足够满足请求（以及头块，如前所述），一块是剩余的空闲块。假设记录头块为 8 个字节（一个整数记录大小，一个整数记录幻数），堆中的空间如图 17.4 所示。
遍历列表，合并（merge）相邻块。完成之后，堆又成了一个整体。
让堆增长
我们应该讨论最后一个很多内存分配库中都有的机制。具体来说，如果堆中的内存空间耗尽，最简单的方式就是返回失败。
大多数传统的分配程序会从很小的堆开始，当空间耗尽时，再向操作系统申请更大的空间。调用sbrk让堆增长。操作系统在执行 sbrk 系统调用时，会找到空闲的物理内存页，将它们映射到请求进程的地址空间中去，并返回新的堆的末尾地址。这时，就有了更大的堆，请求就可以成功满足。
基本策略
- 最优匹配
- 最差匹配
- 首次匹配
- 下次匹配
其他方式
除了上述基本策略外，人们还提出了许多技术和算法，来改进内存分配。这里我们列出一些来供你考虑（就是让你多一些思考，不只局限于最优匹配）。
- 分离空闲列表
- 伙伴系统
空闲空间首先从概念上被看成大小为 2^N 的大空间。当有一个内存分配请求时，空闲空间被递归地一分为二，直到刚好可以满足请求的大小（再一分为二就无法 满足）。形成一棵二叉树
递归合并伙伴，如果将这个 8KB 的块归还给空闲列表，分配程 序会检查“伙伴”8KB 是否空闲。如果是，就合二为一，变成 16KB 的块。然后会检查这 个 16KB 块的伙伴是否空闲，如果是，就合并这两块。
每对互为伙伴的块的内存地址只有一位不同，找到对应伙伴很容易
小结
- 讨论了最基本的内存分配程序形式。
- 上面提到的众多方法都有一个重要的问题，缺乏可扩展性（scaling）。具体来说，就是 查找列表可能很慢。因此，更先进的分配程序采用更复杂的数据结构来优化这个开销，牺 牲简单性来换取性能。例子包括平衡二叉树、伸展树和偏序树。
- 考虑到现代操作系统通常会有多核，同时会运行多线程的程序（本书之后关于并发的章节将会详细介绍），因此人们这了许多工作，提升分配程序在多核系统上的表现。