堆管理算法中的Buddy System(伙伴系统)算法

在一个Buddy System算法中，堆管理者只分配特定大小的内存块，成为permitted size。针对每个permitted size，都有一个空闲链表来维护。

一般这些大小会选择2的幂次方，或者斐波那契数列。因为这样会方便地将除最小的那个数之外的其它数都分为两个permitted size之和。

当负责分配内存的堆管理者接受到请求s大小的内存请求时，会讲s对齐到一个permitted size。然后从那个permitted size的空闲链表中分配一块内存给他。如果没有在那个空闲链表中找到内存，就在大一级的内存中找一块内存分配给用户，然后将剩余的另一半挂到这个permitted size的空闲链表中。

这个算法中的空闲链表一般采用位图(bitmap)算法来实现。因为这样会使内存回收合并变得很高效。

在Zend引擎中的堆管理算法中就使用到了伙伴系统算法，我们来看一下zend_mm_heap结构中相关的数据结构：

zend_mm_free_block *free_buckets[ZEND_MM_NUM_BUCKETS*2];

堆管理算法中的Buddy System(伙伴系统)算法

原文：http://blog.csdn.net/topasstem8/article/details/42595685