伙伴算法

伙伴

两个chunk满足以下三个条件称作伙伴

1. 大小相同
2. 地址连续
3. 从同一个大块中分离

一对伙伴有三种情况

1. 一个chunk已分配，另一个chunk空闲
2. 两个chunk都已分配
3. 两个chunk都空闲，合并

alloc

struct free_area free_area[MAX_ORDER]

数组的每个元素都是某个阶数的free chunk的链表，MAX_ORDER为最大阶数，默认为11

free_area[0]链表中每个chunk都是1个页

free_area[1]链表中每个chunk都是2个页

free_area[2]链表中每个chunk都是4个页

…

free_area[10]链表中每个内存块都是1024个页

当申请$2^n$个页的chunk时，到free_area[n]中查找，如果有free chunk就拆下来分配

如果没有，就到free_area[n+1]中查找，如果有free chunk就拆下来，分成大小相等的两部分，前一部分放入free_area[n]头部，后一部分分配出去

如果没有，就再到free_area[n+2]中查找，如果有free chunk就拆下来，分成大小相等的两部分，前一部分放入

free_area[n+1]头部，后一部分分成大小相等的两部分，前一部分放入free_area[n]，后一部分分配出去

如果没有，继续向上找，直到free_area[MAX_ORDER]，如果还没有就放弃分配

free

当释放$2^n$个页的chunk时，到free_area[n]中查找，如果没有伙伴就放入链表头部

如果有，拆下伙伴，合并，然后到free_area[n+1]中查找，如果没有伙伴就放入链表头部

如果有，拆下伙伴，合并，继续向上查找，直到不能合并或者合并为最大的块

缺点

1. 小块会阻碍旁边两个大块合并
2. 按$2^n$大小分配，存在浪费现象
3. 有较多链表和位图操作，开销大

---