linux底层内存管理--内核空间的伙伴系统

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中体现：
static inline void __free_one_page(struct page *page,
struct zone *zone, unsigned int order)
{
...
while (order unsigned long combined_idx;
struct page *buddy;
buddy = __page_find_buddy(page, page_idx, order); //找到我们的伙伴
if (!page_is_buddy(page, buddy, order)) //看我们的伙伴是否可以合并
break;
list_del(&buddy->lru);
zone->free_area[order].nr_free--;
rmv_page_order(buddy);
combined_idx = __find_combined_index(page_idx, order); //得到合并后的索引
page = page + (combined_idx - page_idx);
page_idx = combined_idx;
order++;
}
set_page_order(page, order);
list_add(&page->lru,
&zone->free_area[order].free_list[migratetype]);
zone->free_area[order].nr_free++;
}
看 来比早期的位图版本要简洁不少了，并且在数据结构中还少了位图指针，节省了空间并且增强了代码的可读性。看看伙伴的安排，内核的伙伴系统很简单的将整个物 理内存按照单一页面进行索引，也即是0，1，2，3，...但是怎么区分不同的order呢？很简单，如果是order为0，那么就是简单的自然数索引， 如果order为1，那么就是隔一个一个索引，就是说0和2会是一对伙伴，如果order为2，那么就是隔4个，就是0和4会是一对伙伴，如果用十进制比 较不好理解，那么用二进制就很简单了，最终落实到的就是下面的两个公式：
1.B2=B1^(12.PB=B&~(1其 中1中B1和B2代表两个伙伴，公式2表示的是如果能合并的话B代表合并前的索引，而PB代表的是合并之后的索引，其实就是屏蔽了后面的几个二进制位。公 式1主要就是找朋友的方式，其实就是将某一位按位取反了，得到的就是不同的一个相邻的块，比如：000，001，010，011，100，101， 110，111中分别代表十进制0，1，2，3，4，5，6，7，按照伙伴算法公式，如果order为0，那么0/1,2/3,4/5,6/7就是伙伴， 因为它们的每一对的最低位不同，别的位相同，符合公式1，如果order为2，那么0,1,2,3/4,5,6,7就是一对伙伴，因为它们的第3位也就是 1释放页面的另一半就是分配页面了，只有两半互相配合，一张一弛才可以做到和谐，在分配的时候如果当前请求的
order 对应的链表还有空闲块，那么直接分配即可，它的伙伴肯定已经分配了，否则它不可能自己留下，早就和它的伙伴合并成更大的块了，接下来它们哥儿俩开始互相等 待，徘徊于上述的两个情况，最终向情况三收敛，如果当前的请求order没有空闲内存块了，那么就在order+1的链表中找，依次类推，一旦找到的话就 会分解这个更大的块，然后递归的将分解后的小块插入更小的order的链表中，值得注意的是，这里体现了和谐，分配内存的机制并没有故意将内存碎片化而释 放内存的机制却有意将内存整体化，这样最终的结果就是内存向整体化收敛，在分配的时候进行的expand中就是分解操作，虽然是分解，但是是迫不得已的分 解，最小化碎片的分解，其的反向操作就是释放中的__free_one_page，其本质是有意的合并，正好抵消了expand中的迫不得已的分解，由于 迫不得已的分解并没有引入除了需求以外额外的小内存(碎片)，因此结果总是会向内存块整体化合并跑偏，最终最小化碎片，下面看一眼expand函数：
static inline void expand(struct zone *zone, struct page *page,
int low, int high, struct free_area *area,
int migratetype)
{
unsigned long size = 1 while (high > low) {
area--;
high--;
size >>= 1;
VM_BUG_ON(bad_range(zone, &page[size]));
list_add(&page[size].lru, &area->free_list[migratetype]);
area->nr_free++;
set_page_order(&page[size], high);
}
}