原文地址 http://blog.csdn.net/s_e_a_n/article/details/5829978
2.4 伙伴系统算法

伙伴系统（buddy system）算法及下节要讲的slab分配器是Linux内存分配的两大核心算法。它们的目的都是提高内存分配效率的同时降低内存碎片。

其实解决内存碎片有两种办法：

I     将不连续的内存页映射到连续的线性地址区间；

II    将大内存分成各种固定大小的块，每次分配时，尽量使用最接近申请大小的那一块，尽量避免为满足小块内存的申请而分拆大的块。

办法I即是vmalloc的思想，但有时后要求申请到内存必须是连续，这就需要方法II。其实方法I还有一个缺点：它需要修改页表，需要硬件的频繁动作，这增加了内存申请和使用的时间。因此多数情况都采用方法II来申请内存。伙伴系统算法即是方法II的一个使用算法。

伙伴系统特征如下：

I     把所有的空闲页框分组为MAX_ORDER(ICE为11)个块链表，每个块链表分别包含大小为2n（n为0~10的整数）个连续的页框，即1、2、4、6、8、16、32、64、128、256、512和1024个连续的页框。

II     每个块的第一个页框的物理地址是该块大小的整数倍。

下图显示了伙伴系统内存组织图，对应着管理区结构中的free_area数组，它们通过页描述符中的list_head链在一起。页描述符首地址放在节点结构的node_mem_map，也可通过全局变量mem_map访问。free_area结构中还有一个nr_free字段，表示各个链表中空闲块的数目。


只以这两个特性不足以表现伙伴系统的强大。它的卓越点在动态管理上。比如要申请一页内存，但0链表中的块已经全部用完了。一般系统通常的做法是到1链表中找一个块给申请者。这无疑浪费了一页的内存。伙伴系统的做法是将这个块分成两个一页的块，一块给申请者，另一块插到0链表中。同样，如果1链表中的块也用完了，就会到2链表中找，找到后会将该块分成三块：两个一页的块和一个两页的块。一个一页的块给申请者，另一个插入到0链表，两页的块插入到1链表。依此类推，直到查到10链表，仍然没有空闲块，才会返回出错。

同样原理用在释放内存上。假设有一页的块要释放，伙伴系统会把它插入到0链表的相应位置，同时查看与前后块是否为伙伴（地址是否连续，如连续再查看排在前面的块的地址是否是两页的整数倍）。如果是，则将这两块合并成一个两页的块插入到1链表的相应位置，然后再查看与前后块是否是伙伴，依此递归，直到已不是伙伴或到10链表。

注意：释放的时候无法保证按顺序释放啊，就是说伙伴可能不在前后块，那岂不是无法合并了？而且不一定前面的就是两页的整数倍。。

两两合并，每次释放时都检查下释放的是哪一块，是否能和别的空闲块合并等就行了啊．