管理空闲空间当然可以很容易，我们会在讨论分页概念时看到。 如果需要管理的空间被划分为固定大小的单元，就很容易。在这种情况下，只需要维护这些大小固定的单元的列表，如果有请求，就返回列表中的第一项。

        如果要管理的空闲空间由大小不同的单元构成，管理就变得困难（而且有趣）。这种情况出现在用户级的内存分配库（如malloc()和free()），或者操作系统用分段（segmentation） 的方式实现虚拟内存。在这两种情况下，出现了外部碎片（external fragmentation）的问题： 空闲空间被分割成不同大小的小块，成为碎片，后续的请求可能失败，因为没有一块足够大的连续空闲空间，即使这时总的空闲空间超出了请求的大小。

         上面展示了该问题的例子。在这个例子中，全部可用空闲空间是 20 字节，但被切成两个 10 字节大小的碎片，导致一个 15 字节的分配请求失败。所以需要解决的问题是：

                                        关键问题：如何管理空闲空间

        要满足变长的分配请求，应该如何管理空闲空间？什么策略可以让碎片最小化？不同方法的时间和空间开销如何？

一、假设

         假定①基本的接口就像 malloc() 和 free() 提供的那样。具体来说，void * malloc(size t size)需要一个参数 size，它是应用程序请求的字节数。函数返回一个指针（没有具体的类型，在 C 语言的术语中是 void 类型），指向这样大小（或较大一点）的一块空间。对应的函数 void free(void *ptr)函数接受一个指针，释放对应的内存块。请注意该接口的隐含意义，在释放空间时，用户不需告知库这块空间的大小。因此，在只传入一个指针的情况下，库必须能够弄清楚这块内存的大小。我们将在稍后介绍是如何得知的。

         该库管理的空间被称为堆，在堆上管理空闲空间的数据结构通常称为空闲列表（free list）。该结构包含了管理内存区域中所有空闲块的引用。当然，该数据结构不一定真的是列表，而只是某种可以追踪空闲空间的数据结构。

         主要关心的是外部碎片（external fragmentation），当然，分配程序也可能有内部碎片（internal fragmentation）的问题。如果分配程序给出的内存块超出请求的大小，在这种块中超出请求的空间（因此而未使用）就被认为是内部碎片（因为浪费发生在已分配单元的内部），这是另一种形式的空间浪费。但是，简单起见，同时也因为它更有趣，这里主要讨论外部碎片。

         还假设②，内存一旦被分配给客户，就不可以被重定位到其他位置。例如，一个程序调用 malloc()，并获得一个指向堆中一块空间的指针，这块区域就“ 属于 ”这个程序了，库不能再移动，直到程序调用相应的 free() 函数将它归还。。因此，不可能进行紧凑 （compaction）空闲空间的操作，从而减少碎片。但是，操作系统层在实现分段（segmentation） 时，却可以通过紧凑来减少碎片（正如第16章讨论的那样）。

二、底层机制

        先来介绍大多数分配程序采用的通用机制。首先，探讨①空间分割与合并的基本知识。其次，看看如何②快速并相对轻松地追踪已分配的空间。最后， 讨论③如何利用空闲区域的内部空间维护一个简单的列表，来追踪空闲和已分配的空间。

         1. 分割与合并

        空闲列表包含一组元素，记录了堆中的哪些空间还没有分配。假设有下面的30字节的堆：

         这个堆对应的空闲列表会有两个元素，一个描述第一个10字节的空闲区域（字节0～9）， 一个描述另一个空闲区域（字节20～29）：

         通过上面介绍可以看出，任何大于 10 字节的分配请求都会失败（返回 NULL），因为没有足够的连续可用空间。而恰好 10 字节的需求可以由两个空闲块中的任何一个满足。但是，申请小于10 字节空间，会发生什么？

        假设我们只申请一个字节的内存。这种情况下，分配程序会执行所谓的分割（splitting）动作：它找到一块可以满足请求的空闲空间，将其分割，第一块返回给用户，第二块留在空闲列表中。在我们的例子中，假设这时遇到申请一个字节的请求，分配程序选择使用第二块空闲空间，对malloc() 的调用会返回20（1字节分配区域的地址），空闲列表会变成这样：

        从上面可以看出，空闲列表基本没有变化，只是第二个空闲区域的起始位置由 20 变成 21，长度由 10 变为 9 了。因此，如果请求的空间大小小于某块空闲块，分配程序通常会进行分割。

        许多分配程序中因此也有一种机制，名为合并（coalescing）。还是看前面的例子（10 字节的空闲空间，10字节的已分配空间，和另外10字节的空闲空间）。 

        对于这个（小）堆，如果应用程序调用 free(10)，归还堆中间的空间，会发生什么？如果只是简单地将这块空闲空间加入空闲列表，不多想想，可能得到如下的结果： 

         问题出现了：尽管整个堆现在完全空闲，但它似乎被分割成了3个10字节的区域。这时， 如果用户请求20字节的空间，简单遍历空闲列表会找不到这样的空闲块，因此返回失败。

        为了避免这个问题，分配程序会在释放一块内存时合并可用空间。想法很简单：在归还一块空闲内存时，仔细查看要归还的内存块的地址以及邻近的空闲空间块。如果新归还的空间与一个原有空闲块相邻（或两个，就像这个例子），就将它们合并为一个较大的空闲块。通过合并，最后空闲列表应该像这样：

 

         2. 追踪已分配空间的大小

        free(void *ptr) 接口没有块大小的参数。因此它是假定，对于给定的指针，内存分配库可以很快确定要释放空间的大小，从而将它放回空闲列表。

         要完成这个任务，大多数分配程序都会在头块（header）中保存一点额外的信息，它在内存中，通常就在返回的内存块之前。我们再看一个例子（见图17.1）。在这个例子中，检查一个 20 字节的已分配块，由 ptr 指着，设想用户调用了 malloc()，结果保存在 ptr 中：ptr = malloc(20)

        该头块中至少包含所分配空间的大小（这个例子中是20）。它也可能包含一些额外的指针来加速空间释放，包含一个幻数来提供完整性检查，以及其他信息。我们假定，一个简单的头块包含了分配空间的大小和一个幻数：

typedef struct header_t{
    int size; 
    int magic; 
} header_t; 

         上面的例子看起来会像图 17.2 的样子。用户调用 free(ptr) 时，库会通过简单的指针运算得到头块的位置：

void free(void *ptr){ // 在块的前端开辟的信息

        header_t *hptr = (void *)ptr - sizeof(header_t);} 

         获得头块的指针后，库可以很容易地确定幻数是否符合预期的值，作为正常性检查 （assert（hptr->magic == 1234567）），并简单计算要释放的空间大小（即头块的大小加区域长度）。请注意前一句话中一个小但重要的细节：实际释放的是头块大小加上分配给用户的空间的大小。因此，如果用户请求N字节的内存，库不是寻找大小为N的空闲块，而是寻找 N 加上头块大小的空闲块。

        3. 嵌入空闲列表

        这个简单的空闲列表还只是一个概念上的存在，它就是一个列表， 描述了堆中的空闲内存块。但如何在空闲内存自己内部建立这样一个列表呢？

        假设我们需要管理一个 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 所示。 

 

        对于 100 字节的请求，库从原有的一个空闲块中分配了 108 字节，返回指向它的一个指针（如图用 ptr 表示），并在其之前连续的 8 字节中记录头块信息，供未来的 free() 函数使用。同时将列表中的空闲节点缩小为 3980 字节（4088-108）. 

         再来看该堆，其中有3个已分配区域，每个100（加上头块是108）。这个堆如图17.5 所示。

        堆的前 324 字节已经分配，因此我们看到该空间中有3个头块，以及3个 100 字节的用户使用空间。空闲列表还是无趣：只有一个节点（由head指向），但在 3次分割后， 现在大小只有3764字节。但如果用户程序通过 free() 归还一些内存，会发生什么？ 

        这个例子中，应用程序调用 free(16500)，归还了中间的一块已分配空间（内存块的起始地址 16384 加上前一块的 108，和该块的头块的 8 字节，得到了 16500 ）这个值在前图中用 sptr 指向

         库马上弄清楚了这块要释放空间的大小，并将空闲块加回空闲列表。假设我们将它插入到空闲列表的头位置，该空间如图17.6所示。

        现在的空闲列表包括一个小空闲块（100字节，由列表的头指向）和一个大空闲块（3764 字节）。

        最后一个例子：现在假设剩余的两块已分配的空间也被释放。没有合并，空闲列表将非常破碎，如图17.7所示。 

        从图中可以看出，我们现在一团糟！为什么？简单，我们忘了合并（coalesce）列表项， 虽然整个内存空间是空闲的，但却被分成了小段，因此形成了碎片化的内存空间。解决方案很简单：遍历列表，合并（merge）相邻块。完成之后，堆又成了一个整体。 

        4. 让堆增长

        如果堆中的内存空间耗尽，应该怎么办？最简单的方式就是返回失败。在某些情况下这也是唯一的选择，因此返回NULL也是一种体面的方式。

         大多数传统的分配程序会从很小的堆开始，当空间耗尽时，再向操作系统申请更大的空间。通常，这意味着它们进行了某种系统调用（例如，大多数 UNIX 系统中的 sbrk ），让堆增长。操作系统在执行 sbrk 系统调用时，会找到空闲的物理内存页，将它们映射到请求进程的地址空间中去，并返回新的堆的末尾地址。这时，就有了更大的堆，请求就可以成功满足。

三、基本策略

         理想的分配程序可以同时保证快速和碎片最小化。遗憾的是，由于分配及释放的请求序列是任意的（毕竟，它们由用户程序决定），任何特定的策略在某组不匹配的输入下都会变得非常差。所以我们不会描述“最好”的策略，而是介绍一些基本的选择，并讨论它们的优缺点。

         1. 最优匹配

        最优匹配（best fit）策略非常简单：首先遍历整个空闲列表，找到和请求大小一样或更大的空闲块，然后返回这组候选者中最小的一块。这就是所谓的最优匹配（也可以称为最小匹配）。

        只需要遍历一次空闲列表，就足以找到正确的块并返回。 最优匹配背后的想法很简单：选择最接它用户请求大小的块，从而尽量避免空间浪费。 然而，这有代价。简单的实现在遍历查找正确的空闲块时，要付出较高的性能代价。

        2. 最差匹配

        最差匹配（worst fit）方法与最优匹配相反，它尝试找最大的空闲块，分割并满足用户需求后，将剩余的块（很大）加入空闲列表。最差匹配尝试在空闲列表中保留较大的块， 而不是向最优匹配那样可能剩下很多难以利用的小块。但是，最差匹配同样需要遍历整个空闲列表。更糟糕的是，大多数研究表明它的表现非常差，导致过量的碎片，同时还有很高的开销。

        3. 首次匹配 

        首次匹配（first fit）策略就是找到第一个足够大的块，将请求的空间返回给用户。同样， 剩余的空闲空间留给后续请求。

        首次匹配有速度优势（不需要遍历所有空闲块），但有时会让空闲列表开头的部分有很多小块。因此，分配程序如何管理空闲列表的顺序就变得很重要。一种方式是基于地址排序（address-based ordering）。通过保持空闲块按内存地址有序，合并操作会很容易，从而减少了内存碎片。 

        4. 下次匹配 

        不同于首次匹配每次都从列表的开始查找，下次匹配（next fit）算法多维护一个指针， 指向上一次查找结束的位置。其想法是将对空闲空间的查找操作扩散到整个列表中去，避免对列表开头频繁的分割。这种策略的性能与首次匹配很接它，同样避免了遍历查找。 

         例子

        下面是上述策略的一些例子，设想一个空闲链表包含 3 个元素，长度依次为 10、30、20：

四、其他方式

        1. 分离空闲链表

        基本想法很简单： 如果某个应用程序经常申请一种（或几种）大小的内存空间，那就用一个独立的列表，只管理这样大小的对象。其他大小的请求都交给更通用的内存分配程序。

         通过拿出一部分内存专门满足某种大小的请求，碎片就不再是问题了。而且，由于没有复杂的列表查找过程，这种特定大小的内存分配和释放都很快。

         这种方式也为系统引入了新的复杂性。例如，应该拿出多少内存来专门为某种大小的请求服务，而将剩余的用来满足一般请求？设计了厚块分配程序处理这个问题。

        具体来说，在内核启动时，它为可能频繁请求的内核对象创建一些对象缓存（object cache），如锁和文件系统 inode 等。这些的对象缓存每个分离了特定大小的空闲列表，因此能够很快地响应内存请求和释放。如果某个缓存中的空闲空间快耗尽时，它就向通用内存分配程序申请一些内存厚块（slab）（总量是页大小和对象大小的公倍数）。相反，如果给定厚块中对象的引用计数变为 0，通用的内存分配程序可以从专门的分配程序中回收这些空间，这通常发生在虚拟内存系统需要更多的空间的时候。

        厚块分配程序比大多数分离空闲列表这得更多，它将列表中的空闲对象保持在预初始化的状态。Bonwick 指出，数据结构的初始化和销毁的开销很大[B94]。通过将空闲对象保持在初始化状态，厚块分配程序避免了频繁的初始化和销毁，从而显著降低了开销。 

        2. 伙伴系统

        合并对分配程序很关键，设计了一些方法，让合并变得简单，一个好例子就是二分伙伴分配程序。

         在这种系统中，空闲空间首先从概念上被看成大小为 2^N 的大空间。当有一个内存分配请求时，空闲空间被递归地一分为二，直到刚好可以满足请求的大小（再一分为二就无法满足）。这时，请求的块被返回给用户。在下面的例子中，一个64KB大小的空闲空间被切分，以便提供7KB的块：

 

         在这个例子中，最左边的 8KB 块被分配给用户（如上图中深灰色部分所示）。 这种分配策略只允许分配 2 的整数次幂大小的空闲块，因此会有内部碎片（internal fragment）的麻烦。

        伙伴系统的漂亮之处在于块被释放时。如果将这个8KB的块归还给空闲列表，分配程序会检查“ 伙伴 ”8KB 是否空闲。如果是，就合二为一，变成 16KB 的块。然后会检查这个16KB块的伙伴是否空闲，如果是，就合并这两块。这个递归合并过程继续上溯，直到合并整个内存区域，或者某一个块的伙伴还没有被释放。

        伙伴系统运转良好的原因，在于很容易确定某个块的伙伴。怎么找？仔细想想上面例子中的各个块的地址。如果你想得够仔细，就会发现每对互为伙伴的块只有一位不同，正是这一位决定了它们在整个伙伴树中的层次。

        3. 其他想法

        上面提到的众多方法都有一个重要的问题，缺乏可扩展性（scaling）。具体来说，就是查找列表可能很慢。因此，更先进的分配程序采用更复杂的数据结构来优化这个开销，牺牲简单性来换取性能。例子包括平衡二叉树、伸展树和偏序树。

         考虑到现代操作系统通常会有多核，同时会运行多线程的程序（本书之后关于并发的章节将会详细介绍），因此人们这了许多工作，提升分配程序在多核系统上的表现。

五、小结

        在本章中，我们讨论了最基本的内存分配程序形式。这样的分配程序存在于所有地方，与编写的每个 C 程序链接，也和管理其自身数据结构的内存的底层操作系统链接。与许多系统一样，在构建这样一个系统时需要这许多折中。对分配程序提供的确切工作负载了解得越多，就越能调整它以更好地处理这种工作负载。在现代计算机系统中，构建一个适用于各种工作负载、快速、空间高效、可扩展的分配程序仍然是一个持续的挑战。