今天去面试，一位面试官提到了内存管理的伙伴系统，当时就懵了，因为根本就没有听说过。晚上回来在实验室查了一些资料，现总结如下：
1.伙伴系统概念
伙伴系统是一种经典的内存管理方法。Linux伙伴系统的引入为内核提供了一种用于分配一组连续的页而建立的一种高效的分配策略，并有效的解决了外碎片问题。
2.伙伴系统的组织结构
Linux中的内存管理的“页”大小为4KB。把所有的空闲页分组为11个块链表，每个块链表分别包含大小为1，2，4，8，16，32，64，128，256，512和1024个连续页框的页块。最大可以申请1024个连续页，对应4MB大小的连续内存。每个页块的第一个页的物理地址是该块大小的整数倍。
结构如图所示：第i个块链表中，num表示大小为(2^i)页块的数目，address表示大小为(2^i)页块的首地址。
3.伙伴系统的内存分配及释放
当向内核请求分配(2^(i-1)，2^i]数目的页块时，按照2^i页块请求处理。如果对应的块链表中没有空闲页块，则在更大的页块链表中找。当分配的页块中有多余的页时，伙伴系统根据多余的页框大小插入到对应的空闲页块链表中。
当释放单页的内存时，内核将其置于CPU高速缓存中，对很可能出现在cache的页，则放到“快表”的列表中。在此过程中，内核先判断CPU高速缓存中的页数是否超过一定“阈值”，如果是，则将一批内存页还给伙伴系统，然后将该页添加到CPU高速缓存中。
当释放多页的块时，内核首先计算出该内存块的伙伴的地址。内核将满足以下条件的三个块称为伙伴：(1)两个块具有相同的大小，记作b。(2)它们的物理地址是连续的。(3)第一块的第一个页的物理地址是2*(2^b)的倍数。如果找到了该内存块的伙伴，确保该伙伴的所有页都是空闲的，以便进行合并。内存继续检查合并后页块的“伙伴”并检查是否可以合并，依次类推。
4.伙伴系统的反碎片机制
内核将已分配页分为以下三种不同的类型：
(1)不可移动页：这些页在内存中有固定的位置，不能够移动。
(2)可回收页：这些页不能移动，但可以删除。内核在回收页占据了太多的内存时或者内存短缺时进行页面回收。
(3)可移动页：这些页可以任意移动，用户空间应用程序使用的页都属于该类别。它们是通过页表映射的。当它们移动到新的位置，页表项也会相应的更新。
在内存子系统初始化期间，所有的页都被标记为可移动的。在启动期间，核心内核分配的内存是不可移动的。此时内核的策略是分配一个尽可能大的连续内存块，将其从可移动列表转换到不可移动列表。分配一个尽可能大的连续内存块而不是选择更小的满足要求的内存块的原因如下：
例如：现有一块可移动的具有16页的连续空闲内存块。当内核需要分配1页不可移动内存页时。分配器选择后8页(而不是一页)转移到不可移动列表，然后从不可移动列表中选择1页用于分配。如果内核又需要分配1页不可移动内存页则从不可移动列表中选择一页用于分配，下图显示了进行4次分配后内存的分布。
但如果内核只选择1页用于分配将其加入到不可移动列表，当下次需要分配时又选择一页加入到不可移动列表，下图显示了按照这种方式进行4次分配后内存的分布。
因此，当没有满足可用于分配的不可移动空闲块时，分配器会在可移动列表中迁移一个尽可能大的连续内存块给不可移动列表。这样避免了启动期间内核分配的内存散列到物理内存各处，从而使其他类型的内存分配免受碎片的干扰。
