隐式空闲链表的实现
在上图的朴素视线中，我们 malloc(4) 但是实际上开了 5 个块，使用了头部的块来标记了这一段内存申请的大小长度
用了一个字来存储这个信息显然是低效的，同时如果要存储接下来这段是占用还是空闲，我们又要开一个字，基于此，隐式空闲链表对它进行了改进
在这个堆块中我们使用了一个字，也就是第一张图中的，一个块，来同时存储了是否分配和分配多少的信息
在这种情况中，一个块是由一个字（也就是 4 字节，本章中一个双字是 8 字节，4 字节也就是 32 位）的头部、有效载荷，以及可能的一些额外的填充组成的。头部编码了这个块的大小(包括头部和所有的填充），以及这个块是已分配的还是空闲。如果我们强加一个双字的对齐约束条件，那么这个头部编码的块的大小就总是 8 的倍数，同时块的大小最低三位总是 0（对于这个数学上的 trick 看下面的计算）
在这种情况下，我们用其中的最低位（已分配位）来指明这个块是已分配的还是空闲的。
例如，假设我们有一个已分配的块，大小为 24(0x18)字节（头部+载荷+填充）。那么它的头部将是
0x00000018 | 0x1 = 0x00000019 总大小或上已分配（也就是末尾的 0x1）
类似的，一个块大小为 40（0x28）字节的空闲块有如下的头部：
0x00000028 | 0x0 = 0x00000028 也就是总大小或上未分配（也就是末尾的 0x0）
规定分配格式后，对于堆组织可以分配为一个连续的已分配块和空闲块的序列如图
隐式空闲链表习题
确定下面 malloc 请求序列产生的块大小和头部值。假设：1）分配器保持双字对齐，并且使用块格式如图 9-35 中所示的隐式空闲链表。2）块大小向上舍入为最接近的 8 字节的倍数
| 请求 | 块大小（十进制字节） | 块头部（十六进制字节） |
|---|---|---|
| malloc(1) | ||
| malloc (5) | ||
| malloc (12) | ||
| malloc (13)) | ||
| 这道题触及了一些核心的概念，例如对齐要求、最小块大小以及头部编码。确定块大小的一般方法是，将所请求的有效载荷和头部大小的和舍入到对齐要求（在此例中是 8 字节）最近的整数倍。比如，malloc(1) 请求的块大小是 4+1=5，然后舍入到 8。而 malloc(13) 请求的块大小是 13+4=17，舍入到 24。 |
| 请求 | 块大小（十进制字节） | 块头部（十六进制字节） |
|---|---|---|
| malloc(1) | 8 | 0x9 |
| malloc (5) | 16 | 0x11 |
| malloc (12) | 24 | 0x11 |
| malloc (13)) | 24 | 0x9 |
分配空闲块的策略
- 首次适配 (First fit):
- 从头开始搜索空闲链表，选择第一个合适的空闲块:
- 可以取总块数 ( 包括已分配和空闲块 ) 的线性时间
- 在靠近链表起始处留下小空闲块的 “碎片”
- 下一次适配 (Next fit):
- 和首次适配相似，只是从链表中上一次查询结束的地方开始
- 比首次适应更快: 避免重复扫描那些无用块
- 一些研究表明，下一次适配的内存利用率要比首次适配低得多
- 最佳适配 (Best fit):
- 查询链表，选择一个最好的空闲块： 适配，剩余最少空闲空间
- 保证碎片最小——提高内存利用率
- 通常运行速度会慢于首次适配
分割内存块-如何处理取到的空闲块
一旦分配器找到一个匹配的空闲块，它就必须做另一个策略决定，那就是分配这个空闲块中多少空间。
- 一个选择是用整个空闲块。虽然这种方式简单而快捷，但是主要的缺点就是它会造成内部碎片。如果放置策略趋向于产生好的匹配，那么额外的内部碎片也是可以接受的
- 然而，如果匹配不太好，那么分配器通常会选择将这个空闲块分割为两部分。第一部分变成分配块，而剩下的变成一个新的空闲块。下图展示了分配器如何分割 8 个字的空闲块，来满足一个应用的对堆内存 3 个字的请求
在下面这张图中，我们申请 4 块，为了效率就要把 6 块分为两部分，4+2
申请额外的内存块
如果分配器不能为请求块找到合适的空闲块将发生什么呢？一个选择是通过合并那些在内存中物理上相邻的空闲块来创建一些更大的空闲块（在下一节中描述）。然而，如果这样还是不能生成一个足够大的块，或者如果空闲块已经最大程度地合并了，那么分配器就会通过调用 sbrk 函数，向内核请求额外的堆内存。分配器将额外的内存转化成一个大的空闲块，将这个块插入到空闲链表中，然后将被请求的块放置在这个新的空闲块中
合并空闲块
分割空闲块后可能会遇到这种情况
当分配器释放一个已分配块时，可能有其他空闲块与这个新释放的空闲块相邻。这些邻接的空闲块可能引起一种现象，叫做假碎片（fault fragmentation），就是有许多可用的空闲块被切割成为小的、无法使用的空闲块
上面这个图中，每一个的有效载荷都为 3 个字。因此，接下来一个对 4 字有效载荷的请求就会失败，即使两个空闲块的合计大小足够大，可以满足这个请求
为了解决假碎片问题，任何实际的分配器都必须合并相邻的空闲块，这个过程称为合并（coalescing）。这就出现了一个重要的策略决定，那就是何时执行合并，分配器可以选择：
- 立即合并（immediate coalescing），也就是在每次一个块被释放时，就合并所有的相邻块
- 推迟合并（deferred coalescing），也就是等到某个稍晚的时候再合并空闲块。例如，分配器可以推迟合并，直到某个分配请求失败，然后扫描整个堆，合并所有的空闲块
带边界标记的合并
合并下一个空闲块
让我们称想要释放的块为当前块。那么，合并（内存中的）下一个空闲块很简单而且高效
当前块的头部指向下一个块的头部，可以检查这个指针以判断下一个块是否是空闲的。如果是，就将它的大小简单地加到当前块头部的大小上，这两个块在常数时间内被合并
合并上一个空闲块
给定一个带头部的隐式空闲链表，唯一的选择将是搜索整个链表，记住前面块的位置，直到我们到达当前块。使用隐式空闲链表，这意味着每次调用 free 需要的时间都与堆的大小成线性关系。即使使用更复杂精细的空闲链表组织，搜索时间也不会是常数
边界标记
Knuth 提出了一种聪明而通用的技术，叫做边界标记（boundary tag），来解决合并上一个块的问题，因为我们无法在当前块得知上一个块头部的信息，但是下一个空闲块的头正好是当前块的指针尾部，我们可以常数读取这个头部信息，边界标记允许在常数时间内进行对前面块的合并
在每个块的结尾处添加一个脚部（footer，边界标记），其中脚部就是头部的一个副本。如果每个块包括这样一个脚部，那么分配器就可以通过检査它的脚部，判断前面一个块的起始位置和状态，这个脚部总是在距当前块开始位置一个字的距离
考虑当分配器释放当前块时所有可能存在的情况：
- 前面的块和后面的块都是已分配的。
- 前面的块是已分配的，后面的块是空闲的。
- 前面的块是空闲的，而后面的块是已分配的。
- 前面的和后面的块都是空闲的。
- 情况 1：前面的和后面块都已分配
- 情况 2：前面块已分配，后面块空闲
- 情况 3：前面块空闲，后面块已分配
- 情况 4：后面块和前面块都空闲
边界标记的缺陷
如果一个图形应用通过反复调用 malloc 和 free 来动态地创建和销毁图形节点，并且每个图形节点都只要求两个内存字，那么头部和脚部将占用每个已分配块的一半的空间
边界标记的性能优化
当我们试图在内存中合并当前块以及前面的块和后面的块时，只有在前面的块是空闲时，才会需要用到它的脚部。如果我们把前面块的已分配/空闲位存放在当前块中多出来的低位中，那么已分配的块就不需要脚部了，这样我们就可以将这个多出来的空间用作有效载荷了，不过请注意，空闲块仍然需要脚部
边界标记练习
确定下面每种对齐要求和块格式的组合的最小的块大小。假设：隐式空闲链表，不允许有效载荷为零，头部和脚部存放在 4 字节的字中
最小块大小对内部碎片有显著的影响。因此，理解和不同分配器设计和对齐要求相关联的最小块大小是很好的。很有技巧的一部分是，要意识到相同的块可以在不同时刻被分配或者被释放。因此，最小块大小就是最小已分配块大小和最小空闲块大小两者的最大值。例如，在最后一个子问题中，最小的已分配块大小是一个 4 字节头部和一个 1 字节有效载荷，舍入到 8 字节。而最小空闲块的大小是一个 4 字节的头部和一个 4 字节的脚部，加起来是 8 字节，已经是 8 的倍数，就不需要再舍入了。所以，这个分配器的最小块大小就是 8 字节
回顾
关键的分配策略总结
Placement policy：放置策略
首次适配，下一次适配，最佳适配，等等
减少碎片以提高吞吐量
有趣的观察：近似于最佳适配算法，独立的空闲链表不需要搜索整个空闲链表
Splitting policy：分割策略
我们什么时候开始分割空闲块？
我们能够容忍多少内部碎片？
Coalescing policy：合并策略
立即合并（Immediate coalescing：每次释放都合并）
延迟合并（Deferred coalescing：尝试通过延迟合并，即直到需要才合并来提高释放的性能。例如：
为malloc扫描空闲链表时可以合并
外部碎片达到阈值时可以合并
Implicit Lists：总结
实现：非常简单
分配开销：
linear time worst case（最坏情况线性时间）
释放开销：
constant time worst case（最坏情况常数时间），“even with coalescing”（即使合并）
Memory usage：内存使用
will depend on placement policy（取决于分配策略）
First-fit, next-fit or best-fit（首次适配，下一次适配或最佳适配）
Not used in practice for malloc/free because of linear-time allocation（由于线性时间分配，没有用于malloc/free）
used in many special purpose applications（用于许多特殊目的的应用）
However, the concepts of splitting and boundary tag coalescing are general to all allocators（然而，分割和边界标记合并的概念对于所有的分配器来说都是通用的）
