Buddy System

Published: August 01, 2020 by Authur Lee

Categories:
Data_Structure 44

伙伴系统(buddy system)是操作系统中用到的另一种动态存储管理方法。

和边界标识法的异同：

同：在用户提出申请时，分配一块大小“恰当”的内存区分配给用户；反之，在用户释放内存区时立即回收。
异：在伙伴系统中，不论是占用块或者空闲块，其大小均为2的k次幂(k为某个正整数)

可利用空间表的结构

【假设】系统的可利用空间容量为 $2^m$ 个字(地址从0到 $2^m-1$ )

开始运行时，整个内存区是一个大小为 $2^m$ 的空闲块。

在运行了一段时间之后，整个内存区被分隔成若干占用块和空闲块。

为了再分配时查找方便，我们将所有大小相同的空闲块建于一张子表中，每个子表是一个双重链表，这样的链表可能有m+1个，将这m+1个表头指针用向量结构组织成一个表。-> 这就是伙伴系统中的可利用空间表。

图示以及解释

head为结点头部，是一个由4个域组成的记录，其中llink域和rlink域分别指向同一链表中的前驱和后继结点； tag域为值为"0"或"1"的标志域； kval域的值为2的幂次k； space是一个大小为 $2^k-1$ 个字的连续内存空间。

伙伴系统中的可利用空间表

#define m 16	// 可利用空间总容量64K字的2的幂次，子表的个数 m+1
typedef struct WORD_b {
	WORD_b *llink;	// 指向前驱结点
	int tag;		// 块标志，0空闲，1占用
	int kval;		// 块大小，值为2的幂次k
	WORD_b *rlink;	// 头部域，指向后继结点
	OTHERTYPE other;// 字的其他部分
} WORD_b, head;		// WORD：内存字类型，结点的第一个字也称为head

typedef struct HeadNode {
	int nodesize;	// 该链表的空闲块的大小
	WORD_b *first;	// 该链表的表头指针
} FreeList[m + 1];	// 表头向量类型

分配算法

当用户题数大小为n的内存请求时，首先在可利用表上寻找结点大小与n相匹配的子表，若此子表非空，则将子表中任一结点分配之；若此子表为空，则需从结点更大的非空子表中去查找，直到找到一个空闲块，则将其中一部分分配给用户，而将剩余部分插入相应子表中。

下面是算法语言描述：

WORD_b* 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 + 2^(k - i); pi->rlink = pi; pi->llink = pi;
            pi->tag = 0; pi->kval = k - i; avail[k - i].first = pi;
        }                                       // 将剩余块插入相应子表
        // 为什么插入的子表一定为空呢？(因为为空所以 avail[k - i].first = pi)
        // 如果该子表不为空，则就不会出现该“等级”的子表的剩余块(结点)，
        // 在“更低等级”的时候就被解决掉了而不会轮到该子表。
        pa->tag = 1; pa->kval = k-(--i);
    }
    return pa;
}

回收算法

在用户释放不再使用的占用块时，系统需将这新的空闲块插入到可利用空间表中。在伙伴系统中，我们仅需考虑互为“伙伴”的两个空闲块的归并。

【伙伴是什么】在分配时经常需要将一个大的空闲块分裂成两个大小相同的存储区，这两个由同一大块分裂出来的小块就称之“互为伙伴”。

【关于“伙伴”的注意事项】在伙伴系统中回收空闲块时，只当其伙伴为空闲块时才归并称大块。也就是说，若有两个空闲块，即便大小相同且地址相邻，但不是同一大块分裂出来的，也不归并在一起。

【如何判断是否为“伙伴”】假设p为大小为 $2^k$ 的空闲块的初始地址，且 p MOD $2^{k+1}$ = 0，则初始地址为p和p+ $2^k$ 的两个空闲块互为伙伴.

在回收空闲块时，应首先判别其伙伴是否为空闲块(若否，则只要将释放的空闲块简单插入在相应子表中即可；若是，则需要在相应子表中找到其伙伴并将之删除)，然后再判别合并后的空闲块的伙伴是否是空闲块。依此重复，直到归并所得空闲块的伙伴不是空闲块，再插入到相应的子表中。

计算伙伴块的起始地址

起始地址为p，大小为 $2^k$ 的内存块，其伙伴块的起始地址为：

伙伴起始地址计算公式

举个例子，假设整个可利用内存区大小为2^10=1024(地址从0到1023)，则大小为2^8，起始地址为512的伙伴块的起始地址为768；大小为2^7，起始地址为384的伙伴块的起始地址为256.

优缺点

优点：算法简单、速度快
缺点：只归并伙伴，容易产生碎片