在本章中，我们从对虚拟内存的讨论中稍稍绕道，讨论任何内存管理系统的基本方面，无论是malloc库(管理进程堆的页面)还是操作系统本身(管理进程的地址空间部分)。具体来说，我们将讨论围绕空闲空间管理（free-space management）的问题。
让我们把问题说得更具体些。管理空闲空间当然很容易，我们将在讨论分页（paging）的概念时看到这一点。当你管理的空间被划分成固定大小的单元时，这很容易;在这种情况下，你只需要保留这些固定大小单位的列表;当客户端请求其中一个时，返回第一个元素。
当你管理的空闲空间由不同大小的单元组成时，空闲空间管理变得更加困难(也更加有趣);在用户级内存分配库中(如malloc()和free())，以及在使用分段（segmentation）来实现虚拟内存时管理物理内存的操作系统中，都会出现这种情况。无论哪种情况，存在的问题都被称为外部碎片（external fragmentation）:空闲空间被分割成不同大小的小块，因此是碎片;后续的请求可能会失败，因为没有一个连续的空间可以满足请求，即使空闲空间的总量超过了请求的大小。

图中显示了这个问题的一个例子。在本例中，可用的总空闲空间是20字节;不幸的是，它被分成两个大小为10的块。因此，一个15字节的请求将失败，即使有20字节空闲。这样我们就得到了本章讨论的问题。

关键的问题：怎样管理空闲空间 当满足可变大小的请求时，应该如何管理空闲空间?可以使用哪些策略来最小化碎片?替代方法的时间和空间开销是什么?

17.1 假设 Assumptions

本文的大部分讨论将集中在用户级内存分配库中发现的分配器的伟大历史。我们借鉴了Wilson的优秀调查[W+95]，但鼓励感兴趣的读者查阅源文件本身以了解更多细节。

它有近80页长;因此，你真的必须要感兴趣!

我们假设有一个基本的接口，如malloc()和free()所提供的接口。具体来说，void malloc(size_t size)接受单个参数size，即应用程序请求的字节数;它返回一个指针(没有特定类型，或者C语言中的void指针)，指向这个大小(或更大)的区域。补充例程void free(void ptr)接受一个指针并释放相应的块。注意接口的含义:用户在释放空间时，不会告诉库它的大小;因此，当只给它一个指针时库必须能够计算出一个内存块有多大。我们将在本章稍后的部分讨论如何做到这一点。
这个库管理的空间在历史上被称为堆，用于管理堆中空闲空间的通用数据结构是某种空闲链表（free list）。该结构包含对内存托管区域中所有空闲空间块的引用。当然，这个数据结构本身不需要是一个链表，而只是某种跟踪可用空间的数据结构。
我们进一步假设我们主要关注外部碎片（external fragmentation），如上所述。分配器当然也有内部碎片（internal fragmentation）的问题;如果分配器分发的内存块大于所请求的内存块，那么该块中任何未请求的(也就是未使用的)空间都被认为是内部碎片(因为浪费发生在已分配的单元内部)，这是空间浪费的另一个例子。但是，为了简单起见，而且由于它是两种类型的碎片中更有趣的一种，我们将主要关注外部碎片。
我们还假设一旦将内存分发给客户端，它就不能被重新定位到内存中的另一个位置。例如，如果程序调用malloc()，并得到一个指向堆中某个空间的指针，那么该内存区域本质上是由程序“拥有”的(并且不能被库移动)，直到程序通过对free()的相应调用返回它。因此，不可能压缩空闲空间，这将有助于消除碎片。然而，在实现分段（segmentation）时，可以在操作系统中使用压缩来处理碎片（如上述关于分段的章节所述）。

一旦你将一个指向内存块的指针交给一个C程序，通常很难确定对该区域的所有引用(指针)，这些引用可能存储在其他变量中，甚至在执行过程中的给定点存储在寄存器中。在强类型的、垃圾收集的语言中可能不是这样，因此可以将压缩作为一种技术来对抗碎片。

最后，我们假设分配器管理一个连续的字节区域。在某些情况下，分配器可以请求该区域增长;例如，当内存耗尽时，用户级内存分配库可能会调用内核来增加堆(通过sbrk等系统调用)。然而，为了简单起见，我们假设这些区域在其整个生命周期中都是一个固定的大小。

17.2 底层机制 Low-level Mechanisms

在深入研究一些策略细节之前，我们将首先讨论大多数分配器中使用的一些常见机制。首先，我们将讨论拆分和合并的基础知识，这是大多数分配器中常见的技术。其次，我们将展示如何快速且相对轻松地跟踪已分配区域的大小。最后，我们将讨论如何在空闲空间中构建一个简单的链表来跟踪哪些是空闲的，哪些不是。

拆分和合并 Splitting and Coalescing

空闲链表包含一组描述堆中仍然剩余的空闲空间的元素。因此，假设下面的30字节堆:

这个堆的空闲列表将有两个元素。一个元素描述前10字节的空闲段(字节0-9)，一个元素描述另一个空闲段(字节20-29)：

如上所述，任何大于10字节的请求都会失败(返回NULL);只是没有一个可用的这种大小的连续内存块。对于这个大小(10字节)的请求，任意一个空闲块都可以很容易地满足。但是如果请求小于 10 个字节会发生什么？
假设我们只请求一个字节的内存。在这种情况下，分配器将执行一个称为拆分（splitting）的操作:它将找到可以满足请求的空闲内存块并将其拆分为两部分。它将返回给调用者的第一个块；第二个块将保留在链表中。因此，在我们上面的示例中，如果请求 1 个字节，并且分配器决定使用链表中两个元素中的第二个来满足请求，则对 malloc() 的调用将返回 20（1 字节分配的区域），列表最终将如下所示：

在图中，你可以看到链表基本保持不变;唯一的变化是空闲区域从20开始，现在是21，空闲区域的长度现在只有9。因此，当请求小于任何特定空闲块的大小时，分配器通常使用拆分。

这个讨论假设没有标头（headers），这是我们现在做出的一个不切实际但简化的假设。

在许多分配器中发现的一种推论机制称为空闲空间合并（coalescing）。再举一个上面的例子(释放10个字节，使用10个字节，再释放10个字节)。
给定这个(很小的)堆，当应用程序调用free(10)，从而返回堆中间的空间时，会发生什么?如果我们简单地将这个空间添加到我们的链表中，不需要考虑太多，我们可能会得到这样的链表:

注意这个问题:虽然整个堆现在是空闲的，但它似乎被分成了三个块，每个块10个字节。因此，如果用户请求20个字节，简单的链表遍历将找不到这样一个空闲块，并返回失败。
为避免此问题，分配器所做的是在释放一大块内存时合并可用空间。想法很简单：当返回内存中的空闲块时，仔细查看您返回的块的地址以及附近的空闲空间块；如果新释放的空间紧挨着一个（或两个，如本例中）现有的空闲块，则将它们合并为一个更大的空闲块。因此，通过合并，我们的最终链表应如下所示：

实际上，在进行任何分配之前，这就是堆链表表最初的样子。通过合并，分配器可以更好地确保应用程序可以使用大的空闲区段。

跟踪已分配区域的大小 Tracking The Size Of Allocated Regions

你可能已经注意到接口free(void ptr)不接受size参数;因此，假定给定一个指针，malloc库可以快速确定要释放的内存区域的大小，从而将空间合并回空闲列表中。
为了完成这个任务，大多数分配器在内存的头块（header block）中存储一些额外的信息，通常就在分发内存块之前。让我们再看一个示例(图17.1)。在这个例子中，我们正在检查一个大小为20字节的分配块，它由ptr指向;假设用户调用malloc()并将结果存储在ptr中，例如，ptr = malloc(20)；

标头（header）最低限度地包含分配区域的大小(在本例中是20);它还可能包含加速回收的额外指针、提供额外完整性检查的幻数（magic number）和其他信息。让我们假设一个简单的标头包含区域的大小和一个幻数，就像这样:

上面的示例与图17.2所示类似。当用户调用free(ptr)时，标准库就会使用简单的指针算法来计算标头从哪里开始:


获得这样一个指向标头的指针后，库可以很容易地确定幻数是否与预期值匹配作为健全性检查（assert(hptr->magic == 1234567)），并通过简单的数学运算计算新释放区域的总大小（即，将标头的大小添加到区域的大小）。请注意最后一句中很小但很关键的细节：空闲区域的大小是标题的大小加上分配给用户的空间的大小。因此，*当用户请求 N 字节的内存时，库不会搜索大小为 N 的空闲块；相反，它搜索大小为 N 加上标头大小的空闲块。

嵌入一个空闲链表 Embedding A Free List

到目前为止，我们已经将简单的空闲链表视为一个概念性实体;它只是一个描述堆中可用内存块的链表。但我们如何在空闲空间中构建这样一个链表呢?
在更典型的链表中，当分配新节点时，当需要为节点提供空间时，只需调用malloc()。不幸的是，在内存分配库中，您不能这样做!相反，您需要在空闲空间本身内构建列表。如果这听起来有点奇怪，不要担心;是啊，但不会怪到你做不到!
假设我们有一个4096字节的内存块要管理(即，堆是4KB)。为了将其作为一个空闲链表来管理，我们首先必须初始化该链表;最初，链表应该有一个条目，大小为4096(减去标头header大小)。下面是链表中一个节点的描述:

现在让我们看一些初始化堆并将空闲链表的第一个元素放入该空间的代码。我们假设堆是在通过调用系统调用mmap()获得的一些空闲空间内构建的;这不是构建这样的堆的唯一方法，但在本例中很适合我们。这是代码：

运行这段代码后，列表的状态是它只有一个条目，大小为 4088。是的，这是一个很小的堆，但它是我们这里的一个很好的例子。head指针包含这个范围的起始地址；让我们假设它是 16KB（尽管任何虚拟地址都可以）。在视觉上，堆看起来像你在图 17.3 中看到的那样。

现在，让我们假设请求的内存块大小为100字节。为了处理这个请求，库将首先找到一个足够大的块来容纳这个请求;因为只有一个空闲块(大小:4088)，所以将选择这个块。然后，块将被拆分（split）成两个:一个足够满足请求(以及上面描述的头)的块，以及剩余的空闲块。假设一个8字节的header(一个整数size和一个整数magic number)，堆中的空间现在看起来像图17.4所示。

因此，在请求 100 字节时，库从现有的一个空闲块中分配 108 字节，返回一个指向它的指针（在上图中标记为 ptr），将标头header信息存储在分配空间之前，以供以后free()使用，并将链表中的一个空闲节点缩小到 3980 字节（4088 减 108）。
现在让我们看看有三个分配的区域时的堆，每个区域有100个字节(包括标头108个字节)。这个堆的可视化如图17.5所示。

正如您在其中看到的，现在已经分配了堆的前324个字节，因此我们看到该空间中有3个标头header以及3个由调用程序使用的100字节区域。空闲链表仍然没有什么意思:只有一个节点(由head指向)，但是现在在三次分割之后只有3764字节。但是当调用程序通过free()返回一些内存时会发生什么呢?
在本例中，应用程序通过调用free(16500)返回已分配内存的中间块(值16500是通过将内存区域的开始部分16384与前一个块的108和该块的标头的8个字节相加得到的)。该值在前面的图中由指针sptr显示。
库立即计算出空闲区域的大小，然后将空闲块添加回空闲链表中。假设我们在空闲链表的头部插入，空间现在看起来像这样(图17.6)。

现在我们有一个链表，它从一个小的空闲块(100字节，由链表的head指向)和一个大的空闲块(3764字节)开始。我们的链表上终于有了不止一个元素!是的，空闲空间是碎片化的，这是一种不幸但常见的现象。
最后一个例子:现在让我们假设最后两个正在使用的块被释放了。如果没有合并，就会出现碎片(图17.7)。

正如你从图中看到的，我们现在有一个大混乱!为什么?很简单，我们忘了合并（coalesce）链表。尽管所有的内存都是空闲的，但它被切成碎片，因此尽管不是一个内存，但看起来却是碎片化的内存。解决方法很简单：遍历链表并合并（merge）相邻的块；完成后，堆将再次完整。

扩大堆 Growing The Heap

我们应该讨论在许多分配库中发现的最后一种机制。具体来说，如果堆耗尽了空间，应该怎么做?最简单的方法就是失败。在某些情况下，这是唯一的选择，因此返回NULL是一种体面的方法。不要难过!你努力了，虽然失败了，但打得很好。
大多数传统的分配器从一个小的堆开始，然后在它们用完时向操作系统请求更多的内存。通常，这意味着它们进行某种类型的系统调用(例如，大多数UNIX系统中的sbrk)来增加堆，然后从那里分配新的块。为了服务sbrk请求，操作系统找到空闲的物理页，将它们映射到请求进程的地址空间，然后返回新堆的末端值;此时，可以使用更大的堆，并且可以成功地为请求提供服务。

17.3 基本策略 Basic Strategies

现在我们有了一些机制，让我们来看看管理空闲空间的一些基本策略。这些方法主要基于您自己可以想到的非常简单的策略；在阅读之前尝试一下，看看你是否想出了所有的替代品（或者一些新的！）。
理想的分配器既快速又最小化碎片。不幸的是，由于分配流（stream of allocation）和free请求可以是任意的(毕竟，它们是由程序员决定的)，任何特定的策略都可能在错误的输入集下表现得非常糟糕。因此，我们不会描述“最佳”方法，而是讨论一些基本方法并讨论它们的优缺点。

最佳匹配 Best Fit

最佳匹配策略非常简单:首先，搜索空闲列表，找到与请求大小相同或更大的空闲内存块。然后，返回该候选组中最小的一个;这就是所谓的最佳拟合块(也可以称为最小拟合块)。遍历空闲链表一次就足以找到要返回的正确块。
最佳匹配背后的直觉很简单:通过返回与用户要求相近的块，最佳匹配试图减少浪费的空间。然而，这是有代价的;当执行彻底搜索正确的空闲块时，朴素的实现会付出很大的性能代价。

最差匹配 Worst Fit

最差匹配方法与最佳匹配相反;找到最大的块并返回请求的数量;将剩余(大)块保留在空闲链表中。因此，Worst fit 试图让大块留下，而不是由最佳匹配方法产生的大量小块留下。但是，仍然需要对空闲空间进行全面搜索，因此这种方法的成本可能很高。更糟糕的是，大多数研究表明，它的性能很差，导致过多的碎片，同时仍然有很高的开销。

首次匹配 First Fit

首次匹配方法简单地找到第一个足够大的块，并将请求的数量返回给用户。与前面一样，剩余的空闲空间将保留以供后续请求使用。
First fit具有速度上的优势——不需要彻底搜索所有空闲空间，但有时会用小对象污染空闲链表的开头。因此，分配器如何管理空闲链表的顺序就成了一个问题。一种方法是使用基于地址的排序;通过空闲空间的地址保持列表的顺序，合并变得更容易，碎片趋于减少。

下次匹配 Next Fit

相比于总是在列表的开头开始第一次匹配搜索，下次匹配算法保留一个额外的指针，指向链表中最后查找的位置。这样做是为了在整个链表中更均匀地分散对空闲空间的搜索，从而避免链表开头的分割。这种方法的性能与first fit非常相似，因为它再次避免了穷举搜索。

一些例子 Examples

以下是上述策略的几个例子。想象一个包含三个元素的自由链表，大小分别为10、30和20(我们忽略标头header和其他细节，只关注策略是如何操作的)。

假设一个大小为15的分配请求。最佳匹配方法是搜索整个列表，并发现20是最佳匹配，因为它是能够容纳请求的最小空闲空间。得到的空闲链表:

正如在本例中所发生的，并且通常发生在最佳匹配中，现在只剩下一小块空闲块。最差匹配方法与此类似，但它找到的是最大的块，在本例中为30。结果列表：

在本例中，首次匹配策略执行与最差匹配策略相同的操作，也寻找第一个可以满足请求的空闲块。区别在于搜索成本;best-fit和worst-fit都会遍历整个链表;First-fit只检查空闲块，直到找到合适的块，从而降低搜索成本。
这些示例仅仅触及了分配策略的表面。为了更深入地理解，需要对实际工作负载和更复杂的分配器行为(例如，合并)进行更详细的分析。也许可以作为家庭作业的一部分，你说呢？

17.4 其他方法 Other Approaches

除了上面描述的基本方法外，还有许多建议的技术和算法以某种方式改进内存分配。我们在这里列出了一些供你考虑(也就是说，让你考虑的不仅仅是best-fit分配)。

分离链表 Segregated Lists

一个有趣的方法已经存在一段时间了，那就是使用分离链表（segregated lists）。基本思想很简单: 如果一个特定的应用程序有一个(或几个)流行大小的请求，保留一个单独的链表来管理该大小的对象;所有其他请求被转发到一个更通用的内存分配器。
这种方法的好处是显而易见的。通过将一块内存专门用于特定大小的请求，碎片问题就小得多了;此外，当分配和free请求的大小合适时，它们可以很快得到满足，因为不需要对链表进行复杂的搜索。
就像任何好主意一样，这种方法也会将新的复杂性引入系统。例如，与一般内存池相比，应该将多少内存分配给用于特定大小的特殊请求的内存池？一个特殊的分配器，uber工程师 Jeff Bonwick 的slab 分配器（设计用于Solaris 内核），以一种相当好的方式处理这个问题[B94]。
具体来说，当内核启动时，它为可能经常被请求的内核对象(如锁、文件系统索引节点等)分配许多对象缓存（object caches）;因此，每个对象缓存都是给定大小的独立空闲链表，并提供内存分配和快速释放请求的服务。当给定缓存的可用空间不足时，它会从更通用的内存分配器请求一些内存板（slabs of memory）(请求的总数量是页面大小和问题对象的倍数)。相反，当给定slab中对象的引用计数全部为零时，一般分配器可以从专用分配器回收它们，这通常在VM系统需要更多内存时进行。

Aside：伟大的工程师真的很伟大 像Jeff Bonwick这样的工程师(他不仅编写了这里提到的slab分配器，而且还是令人惊叹的文件系统ZFS的领导者)是硅谷的核心。几乎在任何伟大的产品或技术背后，都有一个人(或一小群人)，他们的才华、能力和奉献精神都远远高于平均水平。正如(Facebook的)马克•扎克伯格(Mark Zuckerberg)所说:“在自己的角色上出类拔萃的人，并不比非常优秀的人强一点点。他们比我们强100倍。”这就是为什么直到今天，一两个人还能创办一家永远改变世界面貌的公司(想想谷歌、苹果或Facebook)。努力工作，你也可能成为这样的“100倍”人。如果不行，就和这样的人一起工作;你一天学到的东西比大多数人一个月学到的还多。如果做不到，就会感到悲伤。

slab分配器还超越了大多数分离链表方法，将链表中的空闲对象保持在预初始化状态。Bonwick指出，初始化和销毁数据结构是昂贵的[B94];通过将已释放的对象保持在初始化状态，slab分配器避免了每个对象频繁的初始化和销毁周期，从而显著降低了开销。

伙伴分配 Buddy Allocation

由于合并对分配器非常重要，因此一些方法被设计来简化合并。二分伙伴分配器（binary buddy allocator）[K65]就是一个很好的例子。
在这样的系统中，空闲内存首先在概念上被认为是一个大小为2N的大空间。当发出内存请求时，搜索空闲空间会递归地将空闲空间分成两部分，直到找到一个足够大的块来容纳该请求(进一步分成两部分会导致空间太小)。此时，请求的块被返回给用户。下面是在搜索7KB块时分配64KB空闲空间的示例(图17.8)。

在这个例子中，最左边的8KB块被分配(用深灰色表示)并返回给用户;注意，这个方案可能会受到内部碎片（internal fragmentation）的影响，因为只允许给出2的幂次大小的块。
好友分配的美妙之处就在于释放该块时会发生什么。当将8KB块返回到空闲链表时，分配器检查“buddy”8KB是否空闲;如果是，则将这两个块合并为一个16KB的块。然后分配器检查16KB块的buddy是否仍然空闲;如果是这样，它将这两个区块合并在一起。这个递归合并过程继续沿着树向上，要么恢复整个空闲空间，要么在发现有伙伴在使用时停止。
伙伴分配如此有效的原因是确定特定块的伙伴很简单。你问怎么做？想想上面空闲空间中块的地址。如果你仔细想想，你会发现每个伙伴对的地址只有一个位不同；哪个位由伙伴树中的级别决定。因此，您对二分伙伴分配方案的工作原理有了基本的了解。与往常一样，有关更多详细信息，请参阅 Wilson 调查 [W+95]。

其他想法 Other Ideas

上面描述的许多方法的一个主要问题是它们缺乏可伸缩性（scaling）。具体来说，搜索链表可能非常慢。因此，高级分配器使用更复杂的数据结构来解决这些成本，以简单换取性能。例子包括平衡二叉树（balanced binary trees），伸展树（splay trees），或部分有序树（partially-ordered trees）[W+95]。
考虑到现代系统通常有多个处理器并运行多线程的工作负载(您将在关于并发性的书的一节中详细了解这一点)，花费大量精力使分配器在基于多处理器的系统上良好工作也就不足为奇了。Berger等[B+00]和Evans [E06]中发现了两个很好的例子;详细内容请查阅。
随着时间的推移，人们对内存分配器有了成千上万的想法，这只是其中的两个;如果你好奇，可以自己阅读。如果做不到这一点，请阅读glibc分配器是如何工作的[S15]，以便让您了解真实世界是什么样子的。

17.5 总结 Summary

在本章中，我们讨论了内存分配器的最基本形式。这样的分配器存在于任何地方，链接到你编写的每个C程序中，也存在于底层OS中，OS为它自己的数据结构管理内存。与许多系统一样，在构建这样的系统时需要做出许多权衡，您对分配器的确切工作负载了解得越多，就越能对其进行优化，使其更好地工作于该工作负载。在现代计算机系统中，创建一个快速的、空间高效的、可伸缩的、适用于广泛工作负载的分配器仍然是一个持续存在的挑战。

References

[B+00] “Hoard: A Scalable Memory Allocator for Multithreaded Applications” by Emery D.
Berger, Kathryn S. McKinley, Robert D. Blumofe, Paul R. Wilson. ASPLOS-IX, November 2000.
Berger and company’s excellent allocator for multiprocessor systems. Beyond just being a fun paper, also
used in practice!
[B94] “The Slab Allocator: An Object-Caching Kernel Memory Allocator” by Jeff Bonwick.
USENIX ’94. A cool paper about how to build an allocator for an operating system kernel, and a great
example of how to specialize for particular common object sizes.
[E06] “A Scalable Concurrent malloc(3) Implementation for FreeBSD” by Jason Evans. April,
2006. http://people.freebsd.org/˜jasone/jemalloc/bsdcan2006/jemalloc.pdf. A detailed look at
how to build a real modern allocator for use in multiprocessors. The “jemalloc” allocator is in widespread
use today, within FreeBSD, NetBSD, Mozilla Firefox, and within Facebook.
[K65] “A Fast Storage Allocator” by Kenneth C. Knowlton. Communications of the ACM,
Volume 8:10, October 1965. The common reference for buddy allocation. Random strange fact: Knuth
gives credit for the idea not to Knowlton but to Harry Markowitz, a Nobel-prize winning economist.
Another strange fact: Knuth communicates all of his emails via a secretary; he doesn’t send email
himself, rather he tells his secretary what email to send and then the secretary does the work of emailing.
Last Knuth fact: he created TeX, the tool used to typeset this book. It is an amazing piece of software4.
[S15] “Understanding glibc malloc” by Sploitfun. February, 2015. sploitfun.wordpress.com/
2015/02/10/understanding-glibc-malloc/. A deep dive into how glibc malloc works. Amazingly
detailed and a very cool read.
[W+95] “Dynamic Storage Allocation: A Survey and Critical Review” by Paul R. Wilson, Mark
S. Johnstone, Michael Neely, David Boles. International Workshop on Memory Management,
Scotland, UK, September 1995. An excellent and far-reaching survey of many facets of memory
allocation. Far too much detail to go into in this tiny chapter!

Homework (Simulation)

程序malloc.py让您可以像本章中描述的那样研究一个简单的空闲空间分配器的行为。有关其基本操作的详细信息，请参阅README。

Questions

1. 首先使用标志-n 10 -H 0 -p BEST -s 0运行，以生成一些随机分配和释放。你能预测alloc()/free()将返回什么吗?你能猜出每次请求后空闲链表的状态吗?随着时间的推移，你注意到了什么?
2. 当使用最差匹配策略搜索空闲列表(-p WORST)时，结果有什么不同?有什么变化?
3. 如果使用首次匹配 (-p FIRST)会怎样?当你使用首次匹配时什么会加速?
4. 对于上述问题，如何保持链表的顺序可能会影响为某些策略寻找空闲位置所需的时间。使用不同的空闲链表顺序(-l ADDRSORT， -l SIZESORT+， -l SIZESORT-)来查看策略和链表顺序如何影响。
5. 合并空闲列表可能非常重要。增加随机分配的数量(比如-n 1000)。随着时间的推移，更大的分配请求会发生什么?使用或不使用合并(即，不使用或使用-C标志)运行。你看到结果有什么不同?在每种情况下，空闲链表随时间的变化有多大?在这种情况下，链表的顺序重要吗?
6. 当您将百分比分配分数-P更改为大于50时会发生什么?当它接近100时，分配会发生什么?当百分比接近0时呢?
7. 您可以提出什么样的特定请求来生成高度碎片化的空闲空间?使用-A标志创建分段空闲链表，并查看不同的策略和选项如何更改空闲列表的组织。