伙伴系统(buddy system)是分离适配的一种特例,其中每个大小类都是 2 的籍。基本的思路是假设一个堆的大小为

个字,我们为每个块大小

维护一个分离空闲链表,其中

请求块大小向上舍入到最接近的 2 的幂。最开始时,只有一个大小为

个字的空闲块。

为了分配一个大小为

的块,我们找到第一个可用的、大小为

的块,其中

如果

,那么我们就完成了。否则,我们递归地二分割这个块,直到当我们进行这样的分割时,每个剩下的半块(也叫做伙伴)被放置在相应的空闲链表中。要释放一个大小为

的块,我们继续合并空闲的伙伴。当遇到一个已分配的伙伴时,我们就停止合并。

关于伙伴系统的一个关键事实是,给定地址和块的大小,很容易计算出它的伙伴的地址。例如,一个块,大小为 32 字节,地址为:

它的伙伴的地址为

换句话说,一个块的地址和它的伙伴的地址只有一位不相同。

伙伴系统分配器的主要优点是它的快速搜索和快速合并。主要缺点是要求块大小为 2 的幂可能导致显著的内部碎片。因此,伙伴系统分配器不适合通用目的的工作负载。然而,对于某些特定应用的工作负载,其中块大小预先知道是 2 的幂,伙伴系统分配器就很有吸引力了。