伙伴算法例子
地址011011110000，可以被2^(2+1）整除，所以伙伴地址是其下半部，加4就行，所以答案是011011110100; 16大小时，不能被2^(4+1)整除，所以伙伴地址是其上半部，地址减去16，结果为0110 1110 0000。至于为什么这样整除决定，请查看伙伴地址定义
1．原理
Linux的伙伴算法把所有的空闲页面分为10个块组，每组中块的大小是2的幂次方个页面，例如，第0组中块的大小都为20 （1个页面），第1组中块的大小为都为21（2个页面），第9组中块的大小都为29（512个页面）。也就是说，每一组中块的大小是相同的，且这同样大小的块形成一个链表。
我们通过一个简单的例子来说明该算法的工作原理。
假设要求分配的块其大小为128个页面（由多个页面组成的块我们就叫做页面块）。该算法先在块大小为128个页面的链表中查找，看是否有这样一个空闲块。如果有，就直接分配；如果没有，该算法会查找下一个更大的块，具体地说，就是在块大小为256个页面的链表中查找一个空闲块。如果存在这样的空闲块，内核就把这256个页面分为两等份，一份分配出去，另一份插入到块大小为128个页面的链表中。如果在块大小为256个页面的链表中也没有找到空闲页块，就继续找更大的块，即512个页面的块。如果存在这样的块，内核就从512个页面的块中分出128个页面满足请求，然后从384个页面中取出256个页面插入到块大小为256个页面的链表中。然后把剩余的128个页面插入到块大小为128个页面的链表中。如果512个页面的链表中还没有空闲块，该算法就放弃分配，并发出出错信号。
以上过程的逆过程就是块的释放过程，这也是该算法名字的来由。满足以下条件的两个块称为伙伴：
· 两个块的大小相同
· 两个块的物理地址连续
伙伴算法把满足以上条件的两个块合并为一个块，该算法是迭代算法，如果合并后的块还可以跟相邻的块进行合并，那么该算法就继续合并。
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/29012686/viewspace-1130187/ ，如需转载，请注明出处，否则将追究法律责任。
