linux内核的伙伴算法最大限度的减少了内存的碎片，其实应该说成是尽自己最大的努力减少了内存 的碎片。其思想就是将物理内存分成10个链表，每一个链表的元素代表一系列的连续页面，连续页面的数量随链表的不同而不同，linux中有10个这样的链 表，按照2的从0到9次幂的连续页面数量组成，比如链表0中保存有代表2的0次幂个连续页面的页面，而链表k中保存有2的k次幂个连续的页面，linux 的伙伴系统的精髓不但是如何分配，更重要的是如何释放，具体来讲，释放的过程就是一个合并的过程--反之分配的过程就是一个分解或者直接分配的过程，最终 的结果就是尽可能的得到尽可能大的连续内存块，因为在有连续内存分配需求的时候，大的块可以分解，然而小的非连续的块由于其非连续却不能合并，因此确保连 续块的最大化总是好的，在分配小块的时候，如果在小的块链表中没有空闲块，那么就从较大的块中分配，比如从它的order+1的块中进行分配，结果就是一 个块被分配了，由order+1块分解出来的剩余的一个块空闲，并且插入到order链表，如果由order大小的需求那么就可以分配之，如果没有，那么 就等着刚刚分配的块释放后再次和其合并成2的order+1次幂个连续页面大小的块。
在分配过程中由大块分解而成的小块中没有被分配的块将一直等着被分配的块被释放从而和其合并，合并的操作正是在页面释放的过程中，最终的结果就是相当与没 有分解大块，伙伴系统一直在向这个结果收敛，这就是为何伙伴系统能避免碎片的原因。伙伴系统在分配和释放两个方向上执行分解和合并两个互逆的操作，如果一 开始系统没有碎片，那么最终的碎片将最小化，因为互逆的操作将最大力度的抵消碎片的产生，这就是精髓了。伙伴在这里的意义包含几种情况，一对伙伴表示两个 块，按照从0开始的索引，一对伙伴就是从偶数开始到其相邻奇数的两个相邻的块，如果order为0，那么k/k+1(k为偶数)就是一对伙伴，如果 order为2，那么k/k+2(k为偶数)就是一对伙伴，伙伴就是两个相邻的块，它们的关系有三种，第一就是一个被分配时，那么另一个就等着这个分配出 去的块被释放后合并，然后递归的进行更大order的合并；第二就是如果两个都被分配，那么肯定有一个先被释放，那么化为情况一，注意在等待伙伴被释放的 同时，该块可以被分配，从而情况一化为情况二，但是最终它们结果总是趋向于情况三，也就是都被释放从而被合并然后插入到更大一层的链表中。
具体到代码上就没有理论那么琅琅上口了，如果你看的是早期版本，会发现每一个链表都有一个位图，该位图展示该链表中伙伴的情况，该位图设计上十分复杂，最 终被追求简单的内核无情抛弃，2.6.28内核版本是比较新的版本了，它里面没有用位图，而是直接判断，具体在__free_one_page中体现：
在分配过程中由大块分解而成的小块中没有被分配的块将一直等着被分配的块被释放从而和其合并，合并的操作正是在页面释放的过程中，最终的结果就是相当与没 有分解大块，伙伴系统一直在向这个结果收敛，这就是为何伙伴系统能避免碎片的原因。伙伴系统在分配和释放两个方向上执行分解和合并两个互逆的操作，如果一 开始系统没有碎片，那么最终的碎片将最小化，因为互逆的操作将最大力度的抵消碎片的产生，这就是精髓了。伙伴在这里的意义包含几种情况，一对伙伴表示两个 块，按照从0开始的索引，一对伙伴就是从偶数开始到其相邻奇数的两个相邻的块，如果order为0，那么k/k+1(k为偶数)就是一对伙伴，如果 order为2，那么k/k+2(k为偶数)就是一对伙伴，伙伴就是两个相邻的块，它们的关系有三种，第一就是一个被分配时，那么另一个就等着这个分配出 去的块被释放后合并，然后递归的进行更大order的合并；第二就是如果两个都被分配，那么肯定有一个先被释放，那么化为情况一，注意在等待伙伴被释放的 同时，该块可以被分配，从而情况一化为情况二，但是最终它们结果总是趋向于情况三，也就是都被释放从而被合并然后插入到更大一层的链表中。
具体到代码上就没有理论那么琅琅上口了，如果你看的是早期版本，会发现每一个链表都有一个位图，该位图展示该链表中伙伴的情况，该位图设计上十分复杂，最 终被追求简单的内核无情抛弃，2.6.28内核版本是比较新的版本了，它里面没有用位图，而是直接判断，具体在__free_one_page中体现：
static inline void __free_one_page(struct page *page,
本文转自 dog250 51CTO博客，原文链接:http://blog.51cto.com/dog250/1273390
