OS伙伴系统的实现

伙伴系统简介

伙伴系统是一种物理内存管理方式，也被用于linux的物理内存管理。

在这种系统中，空闲空间首先从概念上被看成大小为 个物理页的 大空间。当有一个大小为 页的内存分配请求时，空闲空间被递归地一分为二成两个伙伴块，直到成为大小为 刚好可以满足请求的块，即 ，需要注意：

• 优先选择地址较小的块为目标块

下面图片的例子，展示了一个64KB大小的空闲空间被切分，以便提供7KB的块：

在一个块被释放后，分配器会找到其伙伴块，若伙伴块也处于空闲的状态，则讲这两个伙伴块进行合并，形成一个大一号的空闲块，然后继续尝试向上合并。

• 这里需要注意，合并时要求被合并的2块空间都是空闲的，并且他们要是伙伴（即是从同一个大物理空间划分出的2个子块）
• 需要一直尝试合并，直到有伙伴不是空闲块的或者当前块大小已经等于初始块大小（即不能再向上合并）

基于此我们可以基本了解伙伴系统。

算法描述

内存区间的初始化

• 伙伴系统将高地址 32 MB 划分为数个内存区间，每个内存区间有两种状态：已分配和未分配。
• 每个内存区间的大小只可能是 \(4 × 2^i KB\)，其中 i 是整数且 \(0 ≤ i ≤ 10\)。
• 初始，共有 8 个 4 MB 大小的内存区间，状态均为未分配

可用下表表示初始内存空间：

内存区间的分配

• 每次通过伙伴系统分配 \(x B\) 的空间时，找到满足如下三个条件的内存区间：

  1. 该内存区间的状态为未分配。
  2. 其大小不小于 \(x B\)。
  3. 满足上面两个条件的前提下，该内存区间的起始地址最小。

• 如果不存在这样的内存区间，则本次分配失败；否则，执行如下步骤：

  1. 设该内存区间的大小为 \(y B\)，若\(y / 2<x或 y=4 K\)，则将该内存区间的状态设为已分配，将该内存区间分配并结束此次分配过程。

  2. 否则，将该内存区间分裂成两个大小相等的内存区间，状态均为未分配。

  3. 继续选择起始地址更小的那个内存区间，并返回步骤 1。

内存区间的释放

当一个内存区间使用完毕，通过伙伴系统释放时，将其状态设为未分配。

我们称两个内存区间 x 和 y 是可合并的，当且仅当它们满足如下两个条件：

1. x 和 y 的状态均为未分配。
2. x 和 y 是由同一个内存区间一次分裂所产生的两个内存区间，即x和y是一对伙伴。

若存在两个可合并的内存区间，则将两个内存区间合并，若合并后仍存在两个可合并的内存区间，则继续合并，直到不存在两个可合并的内存区间为止。

算法实现

数据结构简介

为了尽量节约空间，我只使用一个大小为1<<13的int型数组去管理页面的分配情况。buddy[1 << 13]表示高32MB的1<<13个页面的分配状态，页面\(i\)状态主要有以下四种:

• Buddy[i] = -1,表示该页面未被分配，且该页面的下一个页面和该页面处于同一个内存块中，即不属于右边界页面
• Buddy[i] = -2,表示该页面未被分配，且该页面的下一个页面和该页面处于不同个内存块中，即属于右边界页面
• Buddy[i] = 1,表示该页面已被分配，且该页面的下一个页面和该页面处于同一个内存块中，即不属于右边界页面
• Buddy[i] = 2,表示该页面已被分配，且该页面的下一个页面和该页面处于不同个内存块中，即属于右边界页面

下面用一张图简单介绍一下：

图中共有8个相邻的页，其中页面1、页面2处于一个块中，页面3、页面4处于一个块中，页面5、页面6、页面7、页面8处于一个块中。块1和块3已被分配，故页面1状态显然为1，页面2已被分配且属于右边界页面，故状态为2，页面3未被分配且不属于右边界页面，故状态为-1，页面4未被分配且属于右边界页面，故状态为-2，以此类推。

为了实现上述功能，我们需要实现如下的三个函数：

• 初始化函数 buddy_init
  • 函数原型为： void buddy_init(void)
  • 调用此函数后，为 MOS 中 64 MB 物理内存的高地址 32 MB 初始化伙伴系统。初始化结束后，伙伴系统中仅有只有 8 个 4 MB 的待分配内存区间。

void buddy_init(void) {
    int i;
  	//所有页面都未被使用，状态赋值为-1
    for (i = 0;i < 8192;i++) {
        buddy[i] = -1;
    }
  	//初始只有8个4MB的物理块，故需要将8个右边界页面赋值为-2
    for (i = 1023;i <= 8192;i += 1024) {
        buddy[i] = -2;
    }
}

• 分配函数 buddy_alloc
  • 函数原型为： int buddy_alloc(u_int size, u_int *pa, u_char *pi)
  • 调用此函数后，通过伙伴系统分配大小不小于 size 字节的空间，分配逻辑见上述描述。如果分配失败，返回 −1。否则，将 pa 指向所分配内存区间的起始地址，设所分配内存区间的大小为 \(4 × 2^i KB\)，令 *pi = i ，并返回 0。

int buddy_alloc(u_int size, u_int *pa, u_char *pi) {
    int length = 0;       //申请的物理块的页面数
    int suceess_find = 0; //是否申请成功的标志
    int start = 0;        //申请的物理块的初始页面号
    int end = 0;          //申请的物理块的结束页面号
    int i = 0;
    for (i = 0;i < 8192;i++) { //开始寻找符合条件的块空间，用start、end标记选择的块信息
        if (buddy[i] < 0) length++; //页面未被分配才可以进行选择
        if (buddy[i] > 0) {  //页面已分配，需要更新start为下一个页面，重新遍历选择
            length = 0;
            start = i +1;
            continue;
        }
        if (buddy[i] == -2 && length * 4096 >= size) { //如果选择的块空间大于size 字节，则选择成功
            end = i;
            suceess_find = 1;
            break;
        }
        if (buddy[i] == -2 && length * 4096 < size) { //否则，更新start为下一个页面，重新遍历选择
            start = i + 1;
            length = 0;
            continue;
        }
    }

    if (!suceess_find) return -1; //如果选择失败，返回-1
    else {   //否则，尝试将空闲空间被递归地一分为二成两个伙伴块，直到块大小刚好可以满足请求
        while (1) {
          	//不能再分割时，选择当前块，更新块内页面状态为已被分配
            if (length == 1 || (length / 2) * 4096 < size){ 
                for (i = start;i < end;i++) buddy[i] = 1;
                buddy[end] = 2;
                break;
            //否则接着分割，选取左边的块为选择块，更新选择块信息（start,end),同时标记分割信息（buddy[end] = -2;）
            } else {
                length = length / 2; //分割后长度减半
                end = start + length -1; //更新新选择块的信息
                buddy[end] = -2; //标记分割信息，buddy[end]属于右边界页面，更新其状态
             }
         }
    }
    *pa = 0x2000000 | (start * 4096); //写回分配块的首地址
    int pow = 0; //分配内存区间的大小为 4×2^i KB，令 *pi = i，并返回0。
    while (length > 0) {
        pow ++;
        length = length >> 1;
    }
    *pi = pow - 1;
    return 0;
}

• 释放函数 buddy_free

  • 函数原型为： void buddy_free(u_int pa)

  • 调用此函数后，通过伙伴系统释放一个状态为已分配的内存区间，其起始地址为 pa 。释放后的合

    并逻辑见上述描述。

//此函数最为麻烦，望耐心观看理解
void buddy_free(u_int pa) {
    int start = (pa - 0x2000000) / 4096; //获取需要被释放空间的首页面地址
    int end = 0; //被释放空间的尾页面地址
    int length = 1; //被释放空间的页面数
    int i = 0;
    //get length of region
    for (i = start;buddy[i] != 2;i++) length++; //获取需要被释放空间的长度
    //release region
    for (i=start;buddy[i] != 2;i++) buddy[i] = -1; //释放需要被释放空间，注意标记尾页面状态为右边界页面
    buddy[i] = -2;
    end = i;

    int flag = 0; //另一个伙伴是否为空闲空间的标志位
    while(1) { //尝试循环合并伙伴块空间
        flag = 0;
        if (length >= 1024){ //如果当前待合并空间长度大于等于1024，即空间大小大于等于4MB，就停止合并
            break;
        } else if (start % (2 * length) == 0) { 
          //这一步实际目的是寻找当前块的伙伴块位于当前块的左边还是右边
          //解释：一个父块分裂为2个子伙伴块时，左边的块的物理首页面号一定是父块长度的整数倍，这是由分配块策略决定的，因为每次分配块大小都是2的正整数次幂，块左边的页面数必然为当前块大小的整数倍，所以分裂后左子块的首页面号必然是父块长度的整数倍，根据这个特性，可以准确的知道当前块的伙伴块的位置
          //例如父块[1024,1025,1026,1027],分裂为子块A[1024,1025],B[1026,1027]，则必有1024%4=0，1026%4!=0
            for (i = end + 1;i <= end + length;i++) { //判别2伙伴块是否都为空闲块，如果不是则停止合并
                if (buddy[i] > 0) flag = 1;
            }
            if (flag == 1) break;
            end = end + length; //如果均为空闲块，合并块，更新块信息
            length = length * 2;
        } else {
            for (i = start - length;i <= start - 1;i++) {//判别2伙伴块是否都为空闲块，如果不是则停止合并
                if (buddy[i] > 0) flag = 1;
            }
            if (flag == 1) break; //如果均为空闲块，合并块，更新块信息
            start = start - length;
            length = length * 2;
        }
        for (i = start;i < end;i++) buddy[i] = -1; //最终更新可合并的最大块内部页面状态，块尾页面设置为未被引用的右边界页面
        buddy[i] = -2;
    }   
}
//大功告成，感谢观看