9.1.1. 伙伴方法¶

顺序适配方法依赖空闲块的链表，每次内存请求都要搜索合适的块。 因此，对包含 \(n\) 个块的 freelist，找到合适空闲块的时间 在最坏情况下是 \(\Theta(n)\)。 合并相邻空闲块也有些复杂。 最后，我们要么为链表使用额外的空间， 要么占用内存池内的空间来支持内存管理器操作。 采用第二种方案时， 空闲块和保留块都需要标记和大小字段。 空闲块中的字段不占用任何额外空间（因为它们存储在闲置的内存 里），但保留块中的字段会产生额外的空间开销。

伙伴系统解决了上述大部分问题。 查找合适大小的块很高效， 合并相邻空闲块很简单， 而且保留块内不需要存储标记或其他信息字段。 伙伴系统假定内存大小为某个整数 \(N\) 对应的 \(2^N\)。 空闲块和保留块的大小始终是 \(2^k\) （\(k < N\)）。 任一时刻，可能同时存在各种大小的空闲块和保留块。 伙伴系统为每种大小的空闲块维护一个单独的列表。 这样的列表至多有 \(N\) 个，因为只可能有 \(N\) 种不同的块大小。

当 \(m\) 个字的请求到来时，我们首先确定使 \(2^k \geq m\) 的最小 \(k\)。 如果该块大小的空闲列表中存在大小为 \(2^k\) 的块， 就从中选取一块。 伙伴系统不考虑内部碎片： 整个大小为 \(2^k\) 的块都被分配。

如果不存在大小为 \(2^k\) 的块， 就找下一个更大的块。 把这个块对半分裂（必要时反复分裂）， 直到得到想要的大小为 \(2^k\) 的块。 分裂过程产生的其他副产物块被放到相应的 freelist 上。

上例展示了对 256 个单元的内存池执行一系列插入和释放操作的 结果。 假设我们有一系列大小为 5、20、30、50 的请求。 它们分别由大小为 8、32、32、64 的块满足。 如果我们随后释放第三个请求的记录（大小为 30 的那个）， 结果如图所示。 前 8 个单元中仍有一条记录（大小 5），第二个已用块（32 单元） 中有一条记录（大小 20），最后一个已用块（64 单元）中有一条 记录（大小 50）。 我们有一个大小为 \(2^3 = 8\) 的空闲块、一个大小为 \(2^4 = 16\) 的空闲块， 以及两个大小为 \(2^6 = 64\) 的空闲块。

伙伴系统的缺点是允许内部碎片。 例如，257 个字的请求需要一个大小为 512 的块。 伙伴系统的主要优点是：

1. 外部碎片更少。

2. 查找合适大小的块比最佳适配之类的方法代价更低， 因为我们只需在大小为 \(2^k\) 的块的块列表上找到第一个 可用块即可。

3. 合并相邻空闲块很容易。

这种方法之所以称为伙伴系统，是因为它合并的方式。 任何大小为 \(2^k\) 的块的 \(buddy\) （伙伴）是另一个大小相同、地址相同 （即内存中的字节位置，按二进制值读出） 但第 \(k\) 位相反的块。 例如，下图中起始地址为 00000 的 16 大小的块， 其伙伴地址为 10000。 同样，地址为 100000 的 32 大小的块，其伙伴为 000000。 如果空闲块按地址值排序，就可以通过搜索正确的块大小列表找到 伙伴。 合并只需把合并后的伙伴地址移到更大块大小的 freelist 上 （这可能又要求把两个相邻的较大空闲块合并）。

9.1.2. 其他方法¶

除了顺序适配和伙伴方法之外，还有许多专用的内存管理方法。 如果应用足够复杂，最好把可用内存划分成若干内存 区域，每个区域采用不同的内存管理方案。 例如，某些区域可能具有先进先出的简单内存访问模式。 这种区域可以用简单的栈来高效管理。 另一个区域可能只分配定长记录，因而可以用简单的 freelist 管理。 其他区域可能需要本节讨论的某种通用内存分配方法。 分区的优点是部分内存可以得到更高效的管理。 缺点是如果区域大小选择不当，一个区域可能被填满， 而其他区域还有富余内存。

内存管理的另一种做法是对所有内存请求施加标准大小。 我们在磁盘文件管理中已经见过这种概念的例子： 所有文件都按簇大小的倍数分配。 这种方法会导致内部碎片， 但管理由簇组成的文件比管理任意大小的文件更容易。 簇方案还让我们可以放松"内存请求必须由一块连续内存服务"的 限制。 大多数磁盘文件管理器和操作系统主存管理器 都工作在簇或页系统上。 块管理通常用缓冲池来高效分配内存中的可用块。