虽然可以使用低级的mmap和munmap函数来创建和删除虚拟主存的区域，但是大多数C程序还是会在运行时需要额外虚拟主存时，使用一种动态主存分配器(dynamic memory allocator)。
一个动态主存分配器维护着一个称为堆 (heap)(图10.35)的进程虚拟主存区域。在大多数的Unix系统中，堆是一个请求二进制零的区域，它紧接在未初始化的bss区域后开始，并向上扩大(向更高的地址)。对于每个进程，内核维护着一个变量brk(读作“break”)，它指向堆的顶部。
分配器将堆视为一组不同大小的块 (block)的集合来维护。每个块就是一个连续的虚拟主存组块(连续多个虚拟页)，要么是已分配的，要么是空闲的。
分配器有两种基本风格。两种风格都要求程序显示地分配块，不同之处在于由负责释放已分配的块。
显示分配器(explicit allocator)：要求程序显示地释放任何已分配的块。例如，C标准库提供一种叫做malloc程序包的显式分配器。C程序通过调用malloc函数来分配一个块，并通过调用free函数来释放一个块。C++中的new和delete操作符与C中的malloc和free相当。
隐式分配器(implicit allocator)：要求分配器检测何时一个已分配块不再被程序使用，然后就释放这个块。隐式分配器也叫作垃圾收集器 (garbage collector)，而自动释放未使用的已分配的块的过程叫做垃圾收集 (garbage collection)。诸如Lisp、ML以及Java之类的高级语言就用垃圾收集来释放已分配的块。
本节剩下的部分讨论的是显示分配器的设计和实现。我们将在10.10小结中讨论隐式分配器。为了更具体，我们的讨论集中于管理堆区域的分配器。然而，学生们应该明白，主存分配是一个普遍的概念，例如，图形处理密集的程序就经常使用标准分配器来要求获得一大块虚拟主存，然后使用与应用相关的分配器来管理块中的主存，以支持图形节点的创建和销毁。
10.9.1 malloc和free函数
C标准库提供了一个称为malloc程序包的显示分配器。程序通过调用malloc函数来从堆中分配块。
1 2 3 4 #include <stdlib.h> void * malloc (size_t size)
malloc函数返回一个指针，指向大小为至少size字节的主存块，这个块会为可能包含在这个块内的所有数据对象类型做对齐。在我们熟悉的Unix系统上，malloc返回一个8字节边界对齐的块。size_t类型被定义为unsigned int(无符号整数)。
如果malloc遇到问题(例如，程序要求的主存块比可用的虚拟主存还要大)，那么它就返回NULL，并设置errno。malloc不初始化它返回的主存。那些想要已初始化的动态主存的应用程序可以使用calloc，calloc是一个基于malloc的瘦包装函数，它将分配的主存初始化为0。想要改变一个以前已分配块的大小，可以使用realloc函数。
动态主存分配器(例如malloc)可以通过使用mmap和munmap函数，显示地分配和释放堆主存，还可以使用sbrk函数。
1 2 3 4 #include <unistd.h> void * sbrk (int incr)
sbrk通过将内核的brk指针增加incr来扩大和减小堆。若果成功，它就返回brk的旧值，否则，它就返回-1，并将errno设置为ENOMEM。如果incr为零，那么sbrk就返回brk的当前值。用一个为负的incr来调用sbrk是合法的。而且很巧妙，因为返回值(brk的旧值)指向在新堆顶上面的第abs(incr)字节。
程序通过调用free函数来释放已分配的堆块。
1 2 3 4 #include <stdlib.h> void free (void *ptr)
ptr参数必须指向一个从malloc获得的已分配块的起始位置。如果不是，那么free的行为就是错的0。更糟的是，free什么都不返回，就不会告诉应用程序出了错误。
图10.36展示了使用malloc和free是如何管理一个C程序的16字的(非常)小的堆的。每个方框代表一个4字节的字。内部有阴影的方框表示已分配，内部无阴影的方框表示空闲块。初始时，堆是由一个大小为16字的、双字对齐的空闲块组成的。
图10.36(a)：程序请求一个4字的块。malloc的响应是：从空闲块的前部切出一个4字的块，并返回一个指向这个块的第一字的指针。
图10.36(b)：程序请求一个5字的块。malloc的响应时：从空闲块的前部分配一个6字的块。在本例中，malloc在块里填充了一个额外的字，是为了保持空闲块是双字边界对齐的。
图10.36(c)：程序请求一个6字的块，而malloc就从空闲块的前部切出一个6字的块。
图10.36(d)：程序释放在图10.36(b)中分配的那个6字的块。注意，在调用free返回之后，指针p2仍然指向被释放了的块。应用有责任在它调用一个新的malloc重新分配之前，不再使用p2。
图10.36(e)：程序请求一个2字的块。在这种情况中，malloc分配在前一步中被释放了的块的一部分，并返回一个指向这个新块的指针。
10.9.2 为什么要使用动态主存分配
程序使用动态主存分配的最重要原因是，它们经常直到程序实际运行时，才知道某些数据结构的大小。例如，假设要求我们编写一个C程序，它读一个n个ASCII码整数的链表，每一行一个整数，从stdin到一个C数组。输入是由整数n，和接下来要读和存储到数组中的n个整数组成的。最简单的方法就是用某种硬编码的最大数组大小静态地定义这个数组：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 #define MAXN 15213 int array [MAXN];int main () int i, n; scanf ("%d" , &n); if (n > MAXN); printf ("Input file too big" ); for (i=0 ; i<n; i++) scanf ("%d" , &array [i]); return 0 ; }
用这样的硬编码的大小来分配数组通常不是好想法。MAXN的值是任意的，和机器上可用的虚拟主存的实际数量没有关系。而且，如果这个程序的使用者想读取一个比MAXN更大的文件，唯一的办法就是用一个更大的MAXN值来重新编译这个程序。虽然对于这个简单的示例来说这不成问题，但是硬编码数组界限的出现对于拥有百万行代码和大量使用者的大型软件产品而言是一场维护的噩梦。
一种更好的办法是在运行时，在已知了n的值之后，动态地分配这个数组。使用这种方法，数组大小的最大值就只由可用的虚拟主存数量来限制了。
1 2 3 4 5 6 7 8 9 10 int main () int *array , i, n; scanf ("%d" , &n); array = (int *)Malloc(n * sizeof (int )); for (i=0 ; i<n; i++) scanf ("%d" , &array [i]); return 0 ; }
动态主存分配是一种有用而重要的编程技术。
10.9.3 分配器的要求和目标
显示分配器必须在一些相当严格的约束条件下工作：
处理任意请求序列。一个应用可以有任意序列的分配请求和释放请求，只要满足约束条件：每个释放请求必须对应于一个当前已分配的块，这个块产生于以前的分配请求。
立即响应请求。分配器必须立即相应分配请求。因此，不允许分配器为了提高性能缓冲请求重新排列。
只使用堆。分配器使用的任何非标量数据结构都必须保存在堆里。
对齐块。分配器必须对齐块，使得它可以保存任何类型的数据对象。在大多数系统中，这意味着分配器返回的块是8字节对齐的。
不修改已分配的块。分配器只能操作或者改变空闲块。特别是，一旦块被分配了，就不允许修改或者移动它了。因此，诸如压缩已分配块这样的技术是不允许使用的。
在这些条件下，分配器的编写者试图实现吞吐率最大化和存储器使用率最大化，而这两个性能目标经常是相互冲突的。
目标1：最大化吞吐率 。假定n个分配和释放请求的某种序列：R0,R1,…,Rk,…,Rn-1。目标2：最大化主存利用率 。天真的程序员经常不正确地假设虚拟主存是一个无限的资源。实际上，一个系统中被所有进程分配的虚拟主存的全部数量是受磁盘上交换空间的数量限制的。好的程序员知道虚拟主存是一个有限的空间，必须高效地使用，对于可能被要求分配和释放大块主存的动态主存分配器来说，尤其如此。峰值利用率 (peak utilization)。假定n个分配和释放请求的某种序列：R0,R1,…,Rk,…,Rn-1。有效载荷 (payload)是p字节。在 请求Rk完成之后，聚集有效载荷 (aggregate payload)，表示为Pk，为当前已分配的块的有效载荷之和，而Hk表示堆的当前的大小。
10.9.4 碎片
造成堆利用率很低的主要原因是一种称为碎片 (fragmentation)的现象，这种现象是当有未使用的主存但不能满足分配请求。有两种形式的碎片：内部碎片 (internal fragmentation)和外部碎片 (external fragmentation)。
内部碎片是描述一个已分配块比有效载荷大的现象。很多原因都可能造成这个问题。例如，一个分配器的实现可能对增加块的大小以满足边界对齐。
内部碎片的量化是简单的，就是已分配块和它们的有效载荷之差的和。因此，在任意时间点，内部碎片的数量只取决之前的请求和分配器的实现方式。
外部碎片是描述空闲存储器合计起来能够满足一个分配请求，但是没有一个单独的空闲块大到能处理这个请求的现象。
外部碎片比内部碎片的量化要困难的多。因为它不仅取决于以前的请求和分配器的实现方式，还取决于未来的请求。假设k个请求之后，所有空闲块的大小都恰好是4个字。这个堆会有外部碎片吗？答案取决于将来的请求，如果将来所有的分配请求都比4个字小，那么就不会有外部碎片。如果有一个或多个请求比4个字大，那么这个堆就会有外部碎片。
因为外部碎片难以量化，所以分配器试图维持少量的大空闲块，而不是维持大量的小空闲块。
10.9.5 实现问题
可以想象出的最简单的分配器，会把堆组织成一个大的字节数组，还有一个指针P，初始指向这个数组的第一个字节。为了分配size字节，malloc将P的当前值保存在栈里，将P增加size，并将P的旧值返回到调用函数。free只是简单地返回调用函数，而不做任何其他事情。
这个简单的分配器是一种极端情况。因为每个malloc和free只执行很少量的指令，吞吐率会极好。然而，因为分配器从不重复使用任何块，存储器利用率将极差。一个实际的分配器要在吞吐率和利用率之间把握好平衡，就必须考虑以下几个问题。
空闲块组织： 我们如何记录空闲块。放置： 我们如何选择一个合适的空闲块来放置一个新分配的块？分隔： 在我们将一个新分配的块放置到某个空闲块之后，我们如何处理这个空闲块中的剩余部分？合并： 我们如何处理一个刚刚被释放的块？
本章的剩余部分，将详细讨论这些问题。因为像放置、分隔以及合并这样的基本技术贯穿在许多不同的空闲块组织方式中，所以我们将在一种叫做隐式空闲链表的简单空闲块组织结构中来介绍它们。
10.9.6 隐式空闲链表
任何实际的分配器都需要一些数据结构，用来划分块边界，并区别已分配块和空闲块。大多数分配器将这些信息嵌在块本身当中。一个简单的方法如图10.37所示。
在这种结构下，一个块是由一个字的头部、有效载荷，以及可能的填充组成的。头部记录了这个块的大小(包括头部和所有填充)，以及这个块是已分配的还是空闲的。如果我们强加一个双字的对齐约束条件，那么块大小就总是8的倍数，且块大小的最低3位总是零。因此，我们只需要存储块大小的29个高位，用剩余的3位来记录其他信息。我们用头部的最低位指明这个块是已分配的，还是空闲的。例如，假设我们有一个已分配的块，大小为24(0x18)字节。那么它的头部将是：
0x00000018 | 0x1 = 0x00000019.
类似地，一个块大小为40(0x28)字节的空闲块有如下的头部：
0x00000028 | 0x0 = 0x00000028.
头部后面就是应用调用malloc时申请的有效载荷。有效载荷后面是一块不使用的填充块，其大小可以是任意的。填充可能是分配器策略的一部分，用来对付外部碎片。或者也需要用它来满足对齐要求。
假设块的格式如图10.37所示，我们可以将堆组织为一个连续的已分配块和空闲块的序列，如图10.38所示。
我们称这种结构为隐式空闲链表 ，是因为空闲块是通过头部中的大小字段隐式地连接着的。分配器可以通过遍历堆中的所有块，从而间接地遍历整个空闲块的结合。注意，我们需要特别标记出结束的块，在这个示例中，就是一个设置了已分配位而大小为0的终止头部(terminating header)。
隐式空闲链表的优点是简单。显著的缺点是任何操作的开销，例如放置分配的块需要搜索空闲块，与堆中已分配块和空闲块的总数呈线性关系。
很重要的一点是，意识到系统对齐要求和分配器对齐要求对最小快的大小有强制要求。例如，我们假设一个双字对齐的要求，那么每个块的大小都必须是双字(8字节)的倍数。因此，图10.37中的块格式就导致最小的块大小为两个字：一个字作头，另一个字维持对齐要求。
10.9.7 放置分配的块
当一个应用请求一个k字节的块时，分配器搜索空闲链表，查找一个足够大、可以放置所请求块的空闲块。分配器执行这种搜索的方式是由放置策略 (placement policy)确定的。一些常见的策略是首次适配(first fit)、下一次适配(next fit)和最佳适配(best fit)。
首次适配 从头开始搜索空闲链表，选择第一个合适的空闲块。下一次适配 和首次适配很相似，只不过不是从链表的起始处开始每次搜索，而是从上一次查询结束的地方开始。最佳适配 检查每个空闲块，选择匹配所需请求大小的最小空闲块。
首次适配的一个优点是它趋向于将大的空闲块保留在链表的后面。缺点是它趋向于在靠近链表起始处留下小空闲块的”碎片”，这就增加了对较大块的搜索时间。下一次适配是由Donald Knuth作为首次适配的一种替代品最早提出的，源于这样一个想法：如果我们上一次在某个空闲块里已经发现了一个匹配，那么很可能下一次我们也能在这个剩余块中发现匹配。下一次适配比首次适配运行起来明显要快一些。然而，一些研究表明，下一次适配的主存利用率比首次适配低得多。研究还表明最佳适配比首次试配和下一次适配的主存利用率都高一些。然而，在简单空闲链表组织结构中，比如隐式空闲链表中，使用最佳适配的缺点是它要求对堆进行彻底的搜索。在后面，我们将看到更加巧妙的分离式空闲链表结构，它实现了最佳适配策略，而不需要进行彻底的堆搜索。
10.9.8 分割空闲块
一旦分配器找到一个匹配的空闲块，它就必须做另一个策略决定，那就是分配这个空闲块中多少空间。一个选择是用整个空间块。虽然这种方式简单而快捷，但是主要的缺点是会造成内部碎片。如果放置策略趋向于生产好的匹配，那么额外的内部碎片也是可以接收的。
然而，如果匹配不太好，那么分配器通常会选择将这个空闲块分割成两部分。第一部分变成分配块，而剩下的变成一个新的空闲块。图10.39展示了分配器如何分隔图10.38中8个字的空闲块，来满足一个应用对堆主存3个字的请求。
10.9.9 获取额外的堆存储器
如果分配器不能为请求找到合适的空闲块，将会发生什么呢？一个选择是通过合并那些虚拟主存中相邻的空闲块来创建一些更大的空闲块(在下一节中描述)。然而，如果这样还是不能生成一个足够大的块，那么分配器就会向内核请求额外的堆主存，要么是调用mmap，要么是通过调用sbrk函数。在任一种情况下，分配器都会将额外的(或增加的)主存转换成一个大的空闲块，将这个块插入到空闲链表中，然后将被请求的块放置在这个新的空闲块中。
10.9.10 合并空闲块
当分配器释放一个已分配块时，可能有其他空闲块与这个新释放的空闲块相邻。这些相邻的空闲块可能引起一种现象，叫做假碎片 (fault fragmentation)，这里有许多可用的空闲块被切割称为小的、无法使用的空闲块。比如，图10.40展示了释放图10.39中分配块后得到的结果。结果是两个相邻的空闲块，每个有效载荷都为3个字。因此，接下来一个请求4字有效载荷的malloc就会失败，即使两个空间块的合计大小足够大，可以满足这个请求。
为了对付假碎片问题，任何实际的分配器都必须合并相邻的空闲块，这个过程称为合并 (coalescing)。这就提出了一个重要的策略决定，那就是何时执行合并。分配器可以选择立即合并 (immediate coalescing)，也就是在一个块被释放的时候，就合并所有的相邻块。或者它也可以选择推迟合并 (deferred coalescing)，也就是等到某个稍晚的时候再合并空闲块。例如，分配器可以推迟合并，直到某个分配请求失败，然后扫描整个堆，合并所有空闲块。
立即合并简单明了，可以在常数时间内完成，但是对于某些请求模式，这种方式会产生一种抖动：块会反复地合并，然后马上分割。例如，在图10.40中，反复地分配和释放一个3个字的块将产生大量不必要的分割和合并。在我们对分配器的讨论中，我们会假设使用立即合并，但是你应该了解，快速的分配器通常会选择某种形式的推迟合并。
10.9.11 带边界标记的合并
分配器是如何实现合并的？让我们称我们想要释放的块为当前块。那么，合并下一个空闲块很简单且高效。当前块的头部指向下一个块的额头不，可以检查这个指针以判断下一个块是否是空闲的。如果是，就将它的大小简单地加到当前块的头部上，这两个块在常数时间内被合并。
但是我们该如何合并前面的块呢？给定一个带头部的隐式空闲链表，唯一的选择将是搜索整个链表，记住前面块的位置，直到我们到达当前块。使用隐式链表，这意味着每次调用free的时间都与块的数目成线性关系。即使更巧妙的空闲链表组织，搜索时间也不会是常数。
Knuth提出了一种聪明而通用的技术，叫做边界标记(boundary tag) ，允许在常数时间内进行对前面块的合并。这种思想，如图10.41所示，是在每个块的结尾处添加一个脚部 (footer边界标记),其中脚部就是头部的一个副本。如果每个块包含这样一个脚部，那么分配器就可以通过检查它的脚部，判断前面一个块的起始位置和状态，这个脚部总是在距当前块结尾位置一个字的距离。
考虑当分配器释放当前块时所有可能存在的情况：
前面的块和后面的块都是已分配的。
前面的块是已分配的，后面的块是空闲的。
前面的块是空闲的，而后面的块是已分配的。
前面的和后面的块都是空闲的。
图10.42展示了我们如何对这四种情况进行合并。
边界标记是简单优雅的，它对许多不同类型的分配器和空闲链表结构都是通用的。然而，它也存在一个缺陷。要求每个块都保持一个头部和一个脚部，在应用程序操作许多小块时，会产生显著的主存开销，例如，如果一个图形应用通过反复调用malloc和free，来动态地创建和销毁图形节点，并且每个图形节点只要求两个字，那么头部和脚部将占用每个已分配块的一半的空间。
幸运的是，有一种非常聪明的边界标记的优化方法。已分配的块实际上不需要脚部，空闲的块才需要脚部。我们可以仅在块被释放，写脚部曾经的覆盖效载荷。
10.9.12 综合：实现一个简单的分配器
我们的分配器使用如图10.43所示的memlib.c包提供的一个堆模型。模型的目的在于允许我们再不干涉已存在的malloc包的情况下，运行我们的分配器。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 static char *mem_start_brk; static char *mem_brk; static char *mem_max_addr; void mem_init (int size) mem_start_brk = (char *)Malloc(size); mem_brk = mem_start_brk; mem_max_addr = mem_start_brk + size; } void *mem_sbrk (int incr) char * old_brk = mem_brk; if ( (incr<0 ) || ((mem_brk+incr) > mem_max_addr)) { errno = ENOMEM; return (void *)-1 ; } mem_brk += incr; return old_brk; }
分配器包含在一个源文件中(malloc.c)，用户可以编译链接这个源文件到它们的应用之中。分配器提供三个函数给应用程序：
1. int mm_init(void);
2. void* mm_malloc(size_t size);
3. void mm_free(void bp);
分配器使用图10.41所示的块格式，空闲链表结构为隐式空闲链表，具有图10.44所示的恒定形式(invariant form)。
第一个字(4字节)是一个用于与结尾块双字边界对齐的填充字。填充后面紧跟着一个特殊的序言块(prologue block)，这是一个8字节的已分配块，只由一个头部和一个脚部组成。序言块是在初始化时创建的，并且永不释放。在序言块后紧跟的是零个或多个由malloc或者free调用创建的普通块。堆总是以一个特殊的结尾块(epilogue block)来结束，这个块是一个大小为零的已分配块，只有一个头部组成。序言块和结尾块是一种消除合并时边界条件的技巧。分配器使用一个私有(静态)全局变量(heap_listp)，它总是指向序言块。(作为小优化，我们可以让它指向下一个块，而不是序言块)。
下面是我们在分配器编码中将要使用的基本常数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #define WSIZE 4 #define DSIZE 8 #define CHUNKSIZE (1<<12) #define OVERHEAD 8 #define MAX(x,y) ((x)>(y) ? (x):(y)) #define PACK(size, alloc) ((size) | (alloc)) #define GET(p) (*(size_t *)(p)) #define PUT(p, val) (*(size_t *)(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)))
在空闲链表中操作头部和脚部可能是很麻烦的，因为它要求大量使用强制类型转换和指针运算。因此，定义一个小的宏集合来访问和遍历空闲链表是很有帮助的。比如我们可以用如下代码确定下一个块的大小:
size_t size = GET_SIZE(HDRP(NEXT_BLKP(bp)));
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 int mm_init (void ) if ((heap_listp = mem_sbrk(4 *WSIZE)) == NULL ) return -1 ; PUT(heap_listp, 0 ); PUT(heap_listp+WSIZE, PACK(OVERHEAD, 1 )); PUT(heap_listp+DSIZE, PACK(OVERHEAD, 1 )); PUT(heap_listp+WSIZE+DSIZE, PACK(0 , 1 )); heap_listp += DSIZE; if (extend_heap(CHUNCKSIZE/WSIZE) == NULL ) return -1 ; return 0 ; }
mm_init函数从主存中得到4个字，并将它们初始化，从而创建一个空的空闲链表。然而它调用extend_heap函数(下面的代码块中展示)，这个函数将堆扩展CHUNKSIZE字节，并且创建初始空闲块。此刻分配器已初始化了，并且准备好接受来自应用的分配和释放请求。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 static void * extend_heap (size_t words) char * bp; size_t size; size = (words % 2 ) ? (words+1 )*WSIZE : words*WSIZE; if ((int )(bp = mem_sbrk(size)) < 0 ) 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); }
extend_heap函数会在两种情况下被调用：①当堆被初始化时；②mm_malloc不能找到一个合适的匹配块时。为了保持对齐，extend_heap将请求大小向上取整为2字的倍数，然后向虚拟主存系统请求额外的堆空间。在很可能出现最后一个块是空闲块的情况下，我们调用coalesce函数来合并两个空闲块，并返回指向合并后的块的块指针。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 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_BKLP(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(HDRP(bp), PACK(size, 0 )); return (bp); } 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 )); return (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 )); return (PREV_BLKP(bp)); } }
我们的空闲链表结构十分巧妙，它的序言块和结尾块总是标记为已分配，使得我们能够忽略麻烦的边界情况，也就是释放的块在堆的起始或结尾处。如果没有这些特殊的块，我们必须在每次释放块时，检查这些并不常见的边界情况，这将导致代码混乱，容易出错，执行更多指令。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 void * mm_malloc (size_t size) size_t asize; size_t extendsize; char * bp; if (size<=0 ) return NULL ; if (size <= DSIZE) asize = DSIZE + OVERHAED; else asize = DSIZE * ((size + (OVERHEAD) + (DSIZE-1 )) / DSIZE); if ( (bp = find_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; }
需要你为分配器实现一个find_fit函数，对隐式空闲链表执行首次适配搜索
1 static void * find_fit (size_t asize)
需要你为分配器实现一个place函数，j将分配块放置在空闲块的起始位置，仅当剩余部分的大小大于等于最小块大小16字节时才分割(加块结构)。
1 static void place (void * bp, size_t asize)
10.9.13 显式空闲链表
隐式空闲链表结构，因为块分配与堆块的综述呈线性关系，所以对通用的分配器，隐式空闲链表是不合适的(尽管对于堆块预先就知道是很小的特殊分配器来说，它是比较好的)。
一种更好的办法是将空闲块组织为某种形式的显示数据结构。因为程序不需要一个空闲块的主体，所以实现这个数据结构的指针可以存放在这些空闲块的主体里面。例如，可以使用一个双向空闲链表结构，在每个空闲块中，包含一个pred(前驱)和succ(后继)指针，如图10.50所示。
使用双向链表，而不是隐式空闲链表，使首次适配的分配时间从块总数的线性时间，减少到了空闲块数量的线性时间。不过释放一个块的时间可以是线性的，也可以是常数的，这取决于我们在空闲链表中对块排序的策略。
一种方法是后进先出 (LIFO)的顺序维护链表，将新释放的块放置在链表的开始处。使用LIFO的顺序和首次适配的放置策略，分配器会最先检查最近使用过的块。在这种情况下，释放一个块可以在常数时间内完成。如果使用了边界标记(当前块可以借助上一块的尾部找到上一块，是个隐式指针)，那么合并也可以在常数时间内完成。
另一种方法是按照地址顺序 来维护链表，其中链表中每个块的地址都小于它的祖先的地址。在这种情况下，释放一个块需要线性时间的搜索，来定位合适的祖先。按照地址排序的首次适配比LIFO的首次适配有更高的存储器利用率，接近最佳适配的利用率。
一般而言，显示链表的缺点是空闲块必须足够大，以包含所有需要的指针，以及头部和可能的脚部。这就导致了更大的最小块大小，也潜在地提高了内部碎片的程度。
10.9.14 分离的空闲链表
就像我们已经看到的，一个使用单向空闲链表的分配器需要与空闲块数量成线性关系的时间来分配块。一种流行的减少分配时间的方法，通常称为分离存储 (segregated storage)，维护多个空闲链表，其中每个链表中的块有大致相等的大小。
一般的思路是将所有可能的块大小分成几类(size class)。分配器维护着一个空闲链表数组，每类一个空闲链表数组，按照大小的升序排列。当分配器需要一个大小为n的块时，它就搜索相应的空闲链表。如果它不能找到相应大小的块与之匹配，它就搜索下一个链表，依次类推。
有关动态存储分配的文献描述了很多种分离存储方法，主要的区别在于它们如何划分类，何时进行合并，何时向操作系统请求额外的堆存储器，是否允许分隔，等等。为了使你大致了解有哪些可能性，我们会描述两种基本的方法：简单分离存储 (simple segregated storage)和分离适配 (segregated fit)。
简单分离存储
使用简单分离存储，每个大小类的空闲链表包含大小相等的块。一个{17-32}大小块，其空闲链表全由32字节的块组成。
为了分配一个给定大小的块，我们检查相应的空闲链表。如果链表非空，我们就简单地分配其中第一块的全部。分空闲块是不会分割的。如果链表为空，分配器就向操作系统请求一个固定大小的额外主存组块(通常是页面大小的整数倍)，将这个组块(chunk)分成大小相等的块，并将这些块连接起来形成性的空闲链表。要释放一个块，分配器只要简单地将这个块插入到相应的空闲链表的前部。
这种方法有许多优点。分配和释放块都是很快的常数时间操作。而且，每个组块(chunk)中都是大小相等的块，不分割，不合并，这意味着每个块分配释放的开销很小。既然每个组块只有大小相同的块，那么一个已分配块的大小就可以从它的地址中推断出来。因为没有合并，所以已分配块的头部就不需要一个已分配/空闲标记。因此已分配块不需要头部，同时因为没有合并，它们也不需要脚部。因为分配和释放操作都是在空闲链表的起始处操作，所以链表只需要是单向的，而不用是双向的了。关键点在于，唯一在任何块中都需要的字段是每个空闲块中的一个字的succ指针，因此最小快大小就是一个字。
一个显著的缺点是，简单分离存储很容易造成内部和外部碎片。因为空闲块是不会被分隔的，所以可能会造成内部碎片。更糟的是，某些引用模式会引起极多的外部碎片，因为是不会合并空闲块的。
研究者提出了一种粗糙的合并形式来对付外部碎片问题。分配器记录操作系统返回的每个组块(chunk)中的空闲块的数量。无论何时，如果有一个组块完全由空闲块组成，那么分配器就从它的当前大小类中删除这个组块，使得它对其他大小类可用。
分离适配
使用这种方法，分配器维护着一个空闲链表的数组。每个空闲链表适合一个大小类相关联的，每个链表包含大小不同的块，这些块的大小是大小类的元素。有许多不同的分离适配分配器，我们描述一个简单版本。
为了分配一个块，我们必须确定请求的大小类，并且对适当的空闲链表做首次适配，查找一个合适的块。如果我们找到了一个，那么我们(可选地)分割它，并将剩余的部分插入到适当的空闲链表中。如果我们找不到合适的块，那么我们就搜索下一个更大的大小类的空闲链表。如此重复，直到找到一个合适的块。如果没有空闲链表中有合适的块，那么我们就向操作系统请求额外的堆主存，从这个新的堆主存中分配出一块，将剩余的部分放置在最大的大小类中。要释放一个块，我们自行合并，并将结果放置到相应的空闲链表中。
分离适配方法是一种常见的选择，C标准库中提供GNU malloc包就是采用的这种方法，因为这种方法既快速，对主存的使用也很有效率。搜索时间减少了，因为搜索被限制在堆的某个部分，而不是整个堆。主存利用率得到了改善，因为有一个有趣的事实：对分离空闲链表的简单的首次适配搜索相当于对整个堆的最佳适配搜索。
伙伴系统
伙伴系统(buddy system)是分离匹配的一种特例，其中每个大小类都是2的幂。基本的思路是假设一个堆的大小为2^m个字，我们为每个块大小2^k维护一个分离空闲链表，其中0≤k≤m。请求块大小向上取整为最接近的2的幂。最开始时，只有一个大小为2^m个字的空闲块。
为了分配一个大小为2^k的块，我们找到第一个可用的、大小为2^j的块，其中k≤j≤m。如果j=k，那么我们就找到了。否则，我们递归地二分这个块，直到j=k。当我们进行这样的分割时，每个剩下的半块(也叫作伙伴)，被放置在相应的空闲链表中。要释放一个大小为2^k的块，我们继续合并空闲的伙伴。当我们遇到一个已分配的伙伴时，我们就停止合并。
关于伙伴系统的一个关键事实是，给定地址和块大小，很容易计算出它的伙伴的地址。例如，一个块，大小为32字节，地址为：xxx…x00000，它的伙伴的地址为 xxx…x10000。换句话说，一个块的地址和它的伙伴只有一位不相同。
伙伴系统分配器的主要优点是它的快速搜索和快速合并。主要缺点是要求块大小为2的幂可能导致显著的内部碎片。因此，伙伴系统分配器不适合通用目的的工作负载。然而，对于某些与应用相关的工作负载，其中块大小预先知道是2的幂，伙伴系统分配器就很有吸引力了。
