学习数据结构与编程（50）伙伴系统

伙伴系统是一种专用于动态内存管理的机制，其特点在于仅能分配2的幂次方数量的内存空间，并且在回收内存时仅对“伙伴空间”进行合并操作。

例如，当内存大小为64时，伙伴系统会为该内存建立一组双向循环链表，分别用于管理2的0次方、2的1次方、2的2次方……直至2的6次方幂等不同大小的可用空间。

即使用户只需要分配一个大小为3的空间，系统也只能提供一个大小为4（即2²）的空间作为分配结果。

在系统初始化阶段，并不会为每个链表预先填充可用空间。而是仅在2⁶对应的链表中插入一个大小为64的空间节点。

当用户需要分配内存时，系统会查找与所需内存大小最接近的链表。如果该链表存在可用空间，则直接从链表中取出第一个空闲块；若无可用空间，则继续依次查找其他可能匹配的空间。

假设现在需要从这64个空间中分配一个大小为3的空间，系统如何处理呢？

系统会从第一个链表开始查找，直到找到对应于2⁶（即64）的空间。此时会将前4个单位的空间分配给用户使用。但剩下的60个单位无法再归还至原链表中，只能将其插入到更小尺寸对应的链表里。

具体的分配方式如下：将总空间拆分为若干部分——分别为4、4、8、16、32。

其中前4个单位分给用户使用；其余部分（即后面的4、8、16和32）则依次插入到对应于2²、2³、2⁴和2⁵次方幂的链表中去。

这一过程遵循以下规则：

1. **