伙伴算法buddy

Buddy System把系统中的可用存储空间划分为存储块(Block)来进行管理, 每个存储块的大小必须是2的n次幂(Pow(2, n)), 即1, 2, 4, 8, 16, 32, 64, 128...
假设系统全部可用空间为Pow(2, k), 那么在Buddy System初始化时将生成一个长度为k + 1的可用空间表List, 并将全部可用空间作为一个大小为Pow(2, k)的块挂接在List的最后一个节点上, 如下图:

当用户申请size个字的存储空间时, Buddy System分配的Block大小为Pow(2, m)个字大小(Pow(2, m-1) < size < Pow(2,  m)).
此时Buddy System将在List中的m位置寻找可用的Block. 显然List中这个位置为空, 于是Buddy System就开始寻找向上查找m+1, m+2, 直到达到k为止. 找到k后, 便得到可用Block(k), 此时Block(k)将分裂成两个大小为Pow(k-1)的块, 并将其中一个插入到List中k-1的位置, 同时对另外一个继续进行分裂. 如此以往直到得到两个大小为Pow(2, m)的块为止, 如下图所示:
 
如果系统在运行一段时间之后, List中某个位置n可能会出现多个块, 则将其他块依次链接可用块链表的末尾:

当Buddy System要在n位置取可用块时, 直接从链表头取一个就行了.

当一个存储块不再使用时, 用户应该将该块归还给Buddy System. 此时系统将根据Block的大小计算出其在List中的位置, 然后插入到可用块链表的末尾. 在这一步完成后, 系统立即开始合并操作. 该操作是将"伙伴"合并到一起, 并放到List的下一个位置中, 并继续对更大的块进行合并, 直到无法合并为止.

何谓"伙伴"? 如前所述, 在分配存储块时经常会将一个大的存储块分裂成两个大小相等的小块, 那么这两个小块就称为"伙伴".在Buddy System进行合并时, 只会将互为伙伴的两个存储块合并成大块, 也就是说如果有两个存储块大小相同, 地址也相邻, 但是不是由同一个大块分裂出来的, 也不会被合并起来. 正常情况下, 起始地址为p, 大小为Pow(2, k)的存储块, 其伙伴块的起始地址为: p + Pow(2, k) 和 p - Pow(2, k).

下面把数据结构一书中Buddy算法分配存储块的C++伪码帖出来以供大家参考:

Space AllocBuddy(FreeList &avail, int n)
{
    //avail[0..m]为可利用空间表, n为申请分配量, 若有不小于n的空闲块,
    //则分配相应的存储块, 并返回其首地址, 否则返回NULL
    for(k=0; k<=m && (avail[k].nodesize < n+1 || !avail[k].first); ++k);//查找满足分配要求的子表
    if(k>m) return NULL;//分配失败, 返回NULL;
    else {//可进行分配
        pa = avail[k].first;//指向可分配子表的第一个节点
        pre = pa->llink; suc = pa->rlink;//分配指向前驱和后继
        if(pa == suc) avail[k].first = NULL;//分配后该子表变为空表
        else {//从子表删除*pa节点
            pre->rlink = suc; suc->llink = pre; avail[k].first = suc;
        }
    }
    for(i = 1; avail[k-i].nodesize >= n+1; ++i) {
        pi = pa + pow(2, k-i); pi-> rlink = pi; pi ->llink = pi;
        pi -> tag = 0; pi -> kval = k-i; avail[k-i].first = pi;
    }//将剩余块插入相应子表
    pa -> tag = 1; pa -> kval = k-(--i);
    return pa;
}

 

页面分配与回收

对系统中物理页面的请求十分频繁。例如当一个可执行映象被调入内存时，操作系统必须为其分配页面。当映象执行完毕和卸载时这些页面必须被释放。物理页面的另一个用途是存储页表这些核心数据结构。虚拟内存子系统中负责页面分配与回收的数据结构和机制可能用处最大。

系统中所有的物理页面用包含mem_map_t结构的链表mem_map来描叙，这些结构在系统启动时初始化。每个 mem_map_t描叙了一个物理页面。其中与内存管理相关的重要域如下：

count

记录使用此页面的用户个数。当这个页面在多个进程之间共享时，它的值大于1。

age

此域描叙页面的年龄，用于选择将适当的页面抛弃或者置换出内存时。

map_nr

记录本mem_map_t描叙的物理页面框号。

页面分配代码使用free_area数组来寻找和释放页面，此机制负责整个缓冲管理。另外此代码与处理器使用的页面大小和物理分页机制无关。

free_area中的每个元素都包含页面块的信息。数组中第一个元素描叙1个页面，第二个表示2个页面大小的块而接下来表示4个页面大小的块，总之都是2的次幂倍大小。list域表示一个队列头，它包含指向mem_map数组中page数据结构的指针。所有的空闲页面都在此队列中。map域是指向某个特定页面尺寸的页面组分配情况位图的指针。当页面的第N块空闲时，位图的第N位被置位。

图free-area-figure画出了free_area结构。第一个元素有个自由页面（页面框号0），第二个元素有4个页面大小的2个自由块，前一个从页面框号4开始而后一个从页面框号56开始。

 

 页面分配

Linux使用Buddy算法来有效的分配与回收页面块。页面分配代码每次分配包含一个或者多个物理页面的内存块。页面以2的次幂的内存块来分配。这意味着它可以分配1个、2个和4个页面的块。只要系统中有足够的空闲页面来满足这个要求(nr_free_pages > min_free_page)，内存分配代码将在free_area中寻找一个与请求大小相同的空闲块。free_area中的每个元素保存着一个反映这样大小的已分配与空闲页面 的位图。例如，free_area数组中第二个元素指向一个反映大小为四个页面的内存块分配情况的内存映象。

分配算法首先搜寻满足请求大小的页面。它从free_area数据结构的list域着手沿链来搜索空闲页面。如果没有这样请求大小的空闲页面，则它搜索两倍于请求大小的内存块。这个过程一直将持续到free_area 被搜索完或找到满足要求的内存块为止。如果找到的页面块大于请求的块则对其进行分割以使其大小与请求块匹配。由于块大小都是2的次幂所以分割过程十分简单。空闲块被连进相应的队列而这个页面块被分配给调用者。

 

  页面回收

将大的页面块打碎进行分配将增加系统中零碎空闲页面块的数目。页面回收代码在适当时机下要将这些页面结合起来形成单一大页面块。事实上页面块大小决定了页面重新组合的难易程度。

当页面块被释放时，代码将检查是否有相同大小的相邻或者buddy内存块存在。如果有，则将它们结合起来形成一个大小为原来两倍的新空闲块。每次结合完之后，代码还要检查是否可以继续合并成更大的页面。最佳情况是系统的空闲页面块将和允许分配的最大内存一样大。