伙伴算法

    频繁的请求和释放不同大小的一组连续页框，必然导致在已分配的块内分散了许多小块的空闲页框。由此带来的问题是，即使有足够的页框可以满足要求，但要分配一个大块的连续页框无法满足。(内存外碎片问题)   
    linux的伙伴算法把所以的空闲页面分为10个块链表，每个链表中的一个块含有2的幂次方个页面，我们把这种快叫做“页块”或简称“块”。例如：第0个链表中快的大小都是2^0(1个页面)，第一个链表中块的大小都为2^1(2个页面), 第9个链表中块的大小都为2^9(512个页面)。
        伙伴系统所采用的数据结构是一个叫做free_area的数组，其示意图如图所示：
            
        struct free_area_struct{
                        struct page *next;
                        struct page *prev;    
                        struct int *map; 
        }free_arean[10];
          ^{数组free_area的每项包含3个域：next,prev和map。指针next,prev用于将物理页面结构struct page链接成一个双向链表，其中的数字表示内存块的其实页面号。例如：图中大小为4的页块有俩块，一块从第4页开始，一块从第56页开始。nr_free表示2^k的空闲页块的个数。例如图中大小为1（2^0）的页块有1个，为4的页块有两个。其中的map域指向一个位图。}