概述

在开发代码的时候，常用的编程语言，无论是 Java/C 还是现在流行的 Go，都离不开动态分配内存，因为有的时候，有些数据结构只能在运行时才能知道它的大小，例如请求一个 List 接口之后，也许我们可以知道单个记录的大小，但是并没法预估对端会返回多少条记录，也就没法预估应该预留多少空间用来存放这些记录。

因此动态分配内存对于程序运行来说非常重要，所以这里我先总结一下关于动态分配内存的一些理论概念，如果可能的话，再多一篇看一下真实的实现。

动态内存分配在哪

首先，需要清楚的是，我这里分析的动态内存都是分配在堆上的，对于 Linux 系统中，一个进程在系统中的内存空间是这样的：

栈一般用于运行过程的变量，函数参数传递使用，而堆一般就用于动态内存分配。在 Linux 中，有个系统调用：brk 就是用于返回 堆 的顶部地址，可以通过 sbrk 来扩展堆。

分配原则

一个很重要的概念就是动态内存的分配都是块为单元的，一般来说是 8 的倍数为一个单元，在 64 位系统中，是 16 的倍数。假设这里是以 8 个字节为一块，那么也就意味着无论是申请 1 个 bit 还是申请 8 个 Byte，那么系统都是分配一个块，也就是 8 个字节的大小。

这意味着很多。首先，对于系统来说，分配一个块内存，内存地址中的最后 3 位是没用的，因为都是以 8 字节为基本单位的，所以这 3 位可以用来存放一些额外的信息。其次，因为说了，即使是申请 1 个 bit 也是分配 8 个字节，那么就会造成浪费，这种浪费在 OS 中称为碎片。

碎片根据情况可以分为两种：内部碎片和外部碎片。

碎片

内部碎片

所谓的内部碎片，就是指我分配多了给你，但是你又用不着，那么用不着的部分就是所谓的内部碎片。因为你不用，别人也用不了。

外部碎片

而外部碎片是我还没分配出去，但是，这块内存又太小了，以至于都没有办法分配给别人，导致浪费，这个太小的内存就是所谓的外部碎片。

动态内存分配的要求

然而，碎片化还不是动态内存分配的唯一考虑点，动态内存需要考虑得更多，但是，这些点都和碎片化离不开关系，这些约束位：

  1. 要能够处于任意请求序列（请求和释放动态内存的请求是随意的，没有像先请求先释放之类的要求）
  2. 理解响应请求（请求的响应速度要够快，因为动态内存的需求还是比较多）
  3. 只使用堆（见进程内存结构）
  4. 块对齐
  5. 不修改已分配的块（如果已经分配了一个块，只要没释放，不能移动它）

这里其实就引申出两个目标；

  1. 最大化吞吐率：也就是说，在固定的时间内，能处理越多的（申请/释放）请求越好
  2. 最大化内存使用率：也就是说内部碎片和外部碎片的比例越底越好

这两个目标是相互冲突的，所以分配策略都是在这两个目标上权衡。

实现的关键问题

要像实现一个良好的内存分配器，需要考虑这么几个关键点：

隐式空闲链表

隐式空闲链表是一个解决这些问题的方案，它的分配块的结构长这样：

在最开始的一个块中，浪费 32 bit 用于作为头部信息，其中前 29 位用于表示这个块有多大（包含头部），然后用最后 1 位表示这一块是空闲的还是已分配的，这就完成了块的组织。

对于一段堆内存，只需要记住“链表头“，然后从链表头出发，就可以进行分配操作了。例如现在需要分配一块动态内存，先查看第一块的头部信息（是否分配，块大小），然后根据匹配原则，找到匹配的块，写入这个块的头部信息，对于多余的部分，同样根据实际情况，写入（原块大小-分配块大小，未分配）的头部信息，这样就可以将分配的块分配出去了。

这已经回答了 3 个问题，如何组织空闲块，如何分配和分割块，但是，这种方法对于合并块并不是很好。当需要使用一块动态内存的时候，可以快速得根据这块内存的头部信息定位到下一个块，根据下一个块的（分配/未分配）状态，可以轻松和下一个块合并，但是，这种方法要想和上一个块合并就会很麻烦，时间与块的数量成线性关系。

带边界标记的合并

一个对于 隐式空闲链表 的改进就是，在分配块的最后也加上一块和头部信息一样的尾部块，这样，就可以很方便得完成和前面一块的合并工作，带来的代价就是每一个块多浪费了 32 位内存。

当然，还有一种避免浪费的方法，就是只有是空闲块的时候，才存在尾部信息，是已分配状态的时候不需要尾巴信息，这样可以让内存利用率更高一些。

显式空闲链表

在 隐式空闲链表 中，分配的时间是与块数量成线性关系，所以一个更好的改进就是，查找的时候直接忽略已分配的块就好了，那么就需要将空闲块直接串联起来，组成 显式空闲链表，因此一个新的空闲块的结构为：

因为空闲链表的内存不属于内存使用率的范畴，只要块大小允许，我们怎么用都不过分，这里就是将前一个空闲块和后一个空闲块的地址都保存在当前空闲块中，当需要申请一个新的动态内存的时候，只需要循着这条内存链表往后走，找到符合匹配规则的空闲块就可以了。

但是，这个方法的分配时间还是与空闲块的数量成线性关系，所以可能还有更好的分配方法。

分离的空闲链表

在 隐式空闲链表 和 显式空闲链表 中，都是只有一个链表，所以，为了提供分配速度，多个链表的方法就被创造出来了。

简单的分离存储

简单分离存储的概念很简单，就是维护多条空闲链表保存空闲的块信息，每个链表中的块大小都处于某个范围，例如：

这样，当需要一段动态内存的时候，直接在对应的链表中找到链表的第一块，分出去就好了，多余部分再插回对应的链表中。回收速度也很快，直接回收到对应的链表中，但是，这个分离存储的问题就是没有合并，会造成大量的内部碎片和外部碎片。

分离适配

分离适配的特点就是维护一个包含空闲链表的数组，每个链表都与一个大小类相关联，并且被组织成 隐式空闲链表 或 显式空闲链表。

当需要分配一个块时，先确定一个大小类，然后在这个大小类的链表中查找，根据分配策略如果找到了就分割，将空闲块插回适当的空闲链表中。如果没找到就去更大的大小类中查找。

通过分离适配，在内存使用率和吞吐之间达到一个良好的平衡，时 GNU 的 maclloc 使用的方式。

伙伴系统

伙伴系统是一个特别的 分离适配，因为伙伴系统中的大小块就是 2 的倍数，当需要一个块时，网上取 2 的倍数，然后根据这个大小类去分配。

伙伴系统的问题就是以 2 的倍数为大小类会造成较多的内部碎片。

匹配原则

在分配的时候，因为是查找链表，所以什么时候确认就是找到适合的块是个问题，这里有几种匹配原则供选择：

首次适配（first fit）

从链表出发，找到下一个可以用的空闲块，就用这个块了。优点是趋向于将大的空闲块保留在链表的后面，缺点就是容易在链表头留下小空闲块的碎片。

下一次适配（next fit）

不从链表头开始搜索，而是从上一次搜索的位置开始搜索。有 Donald Knuth 根据首次适配提出的改进，考虑的思路是如果上一次在这里找到了，那么下一次在这里找到的可能性更大。然而，研究表明，这种方式的内存利用率比首次适配更低。

最佳适配（best fit）

检查整个链表，选择与需求最接近的空闲块。好处是内存利用率比 首次适配 和 下一次适配 都高，然而，因为是全局搜索，所以时间比他们都久。