空闲空间管理

• 假定所有的接口都像malloc()和free() 那样。也就是malloc()在堆空间申请一块指定大小（其实比指定的大小稍大一点）的内存；free()只需要接收一个指针，然后就可以得知这块被分配的内存的位置和大小
• 假定我们只研究外部碎片。不过分配程序可能会出现内部碎片的问题，例如当分配程序给出的内存块大小比请求的大小更大（例如分配程序为了保证内存对齐而分配的内存与需要的内存大小不同），那么这些多余的内存就是内部碎片
• 假设内存一旦被分配给用户，就不能被重定位至其它位置。在这种假设下不能做出紧凑内存空间的操作，但是操作系统的分段其实是可以做出这种操作的
• 假设分配程序管理的是大小固定的一整片内存区域。一般情况下，当有需求时，分配程序可以向内核申请堆空间，不过简单起见，我们假设分配程序管理的内存区域的大小固定

分隔与合并

• 分割(Splitting)
  • 我们现在申请一块一定大小的内存，如果内存中有一块空闲空间，其大小大于我们申请的大小，那么分配程序就会执行分割操作
  • 这个操作会将那块空闲空间分割成两部分：一部分的大小是我们需要的，这一部分返回给我们；另一部分剩余的内存仍然属于空闲空间
• 合并(Coalescing)
  • 当有两块或多块连续的空闲空间时，分配系统会将它们合并为一块大空闲空间

追踪已分配空间的大小

• free()接口只要求用户传入一个指针，却没要求用户传入要释放的空间大小，那free()如何得知要释放的空间大小呢？答案是malloc() 在头块(Header) 内保存了一些额外信息，包括指针指向内存的大小信息，而free()可以获取头块的信息
• malloc()在申请内存时，除了申请的内存外，还会额外申请一块内存空间作为头块。头块的位置在申请内存更低位，紧挨着申请的内存。
• 头块内存储了一些数据，例如所分配空间的大小、一个额外的指针来加速空间释放、一个幻数来提供完整性检查等
• malloc()会返回指向申请的内存的指针而不是指向头块 的指针，
• 头块的大小是固定的，所以可以通过简单的指针运算来获得指向头块的指针，free()函数就可以很轻松地获取头块指针，检测幻数是否符合预期值、简单计算得到要释放的空间（头块+申请内存） 的大小，然后释放空间

堆的增长

• 传统的分配程序会从很小的堆开始，当这个堆的空间耗尽时，再向操作系统申请更大的空间
• 通常这意味着它们进行了某些系统调用（如Unix的sbrk），操作系统在执行sbrk系统调用时会找到空闲的物理内存页，将它们映射到请求进程的地址空间中去，并返回新的堆的末尾地址

最优匹配(Best-fit)

• 最优匹配的策略很简单：遍历一整个空闲列表，找到与请求大小一样或更大的空闲块，然后返回这组候选者中最小的一块
• 这样可以尽可能地避免空间浪费
• 但是需要一整次遍历，要付出较高的性能代价

最差匹配(Worst-fit)

• 它会通过遍历列表，尝试寻找最大的内存块，通过分割来满足用户的需求
• 这样可以在内存中尽量保留较大的块
• 但是它也需要一整次遍历，而且大多数研究表明它的性能非常差，通常导致过量的碎片和过大的开销

首次匹配(First-fit)

• 它会在遍历时找到第一个足够大的块，并分割、将用户需要的部分返回给用户
• 首次匹配不需要遍历整张列表，具有速度优势
• 这有时会让列表的开头有很多小块
• 空闲列表的顺序如何管理会变得很重要。一种方式是基于地址排序(Address-based ordering)。通过保持空闲块内存地址有序，合并操作会很容易，从而减少了内存碎片

下次匹配(Next-fit)

• 下次匹配算法维护了一个指针，这个指针会指向上次查找结束的位置，从那里开始查找足够大的块
• 与首次匹配相似，不过下次匹配让对空闲空间的查找操作扩散到了整个列表里，避免了对列表开头的频繁分割

分离空闲列表(Segregated list)

• 如果某个应用程序经常申请一种或几种大小的内存空间，那就使用一个独立的列表只管理这样大小的对象，其它大小的请求都交给更通用的内存分配程序
• 这样可以减轻碎片的问题
• 使用厚块分配程序(Slab allocator) 可以管理这些拿出来专门使用的内存。在内核启动时，它为可能频繁请求的内核对象创建了一些对象缓存(Object cache)，如锁和文件系统inode等。这样的对象缓存分离了特定大小的空闲列表，因此能够更快地响应内存请求和释放。当某个缓存的空闲空间将要耗尽时，分配程序会向内核申请一些内存厚块(Slab)；反之，如果某个缓存的空闲空间过多，则会回收一部分
• 这种分配系统还会将回收的内存先暂存起来，等到需要的时候可以直接使用，避免了频繁的初始化/销毁对象

二分伙伴分配程序(Binary buddy allocator)

• 空闲空间被视作大小为$2^n$个字节的大空间
• 当有一个内存分配请求时，空闲空间被递归地一分为二，直到刚好可以满足请求（再分就没法满足了），于是请求的块返回给了用户
• 由于只能返回2的次方数字节，所以可能会有内部碎片问题
• 伙伴系统可以很轻松地知道与每个块相邻的“伙伴”块的位置
• 在一个块被释放时，伙伴系统会检查它的伙伴是否空闲，如果是就合并这两个块，然后递归上溯，直到合并一整个内存区域或者有一个块的伙伴还没被释放