文章目录
【 1. 伙伴系统的结构设计 】 【 2. 分配算法 】 【 3. 回收算法 】
伙伴系统
2
m
2^m
2 m
2
0
2^0
2 0
2
1
2^1
2 1
2
2
2^2
2 2
2
m
2^m
2 m 伙伴系统中可利用空间表中的结点构成如下图所示：llink 和 rlink 为结点类型的指针域，分别用于指向直接前驱和直接后继结点。tag ：用于标记内存块的状态，是占用块（用 1 表示）还是空闲块（用 0 表示）kval ：记录该存储块的容量。由于系统中各存储块都是 2 的 m 幂次方，所以 kval 记录 m 的值。 伙伴系统节点的 C 实现： typedef struct WORD_b {
struct WORD_b * llink;
int tag;
int kval;
struct WORD_b * rlink;
OtherType other;
} WORD_b, head;
在伙伴系统中，由于系统会不断地接受用户的内存申请的请求，所以会产生很多大小不同但是容量都是为
2
m
2^m
2 m
2
m
2^m
2 m 可利用空间表的 C 实现： # define m 16 typedef struct HeadNode {
int nodesize;
WORD_b * first;
} FreeList[ m+ 1 ] ;
伙伴系统的分配算法很简单。假设用户向系统申请大小为 n 的存储空间，若
2
k
−
1
<
n
≤
2
k
2^{k-1} < n \leq 2^k
2 k − 1 < n ≤ 2 k
2
k
2^k
2 k 如果该链表不为 NULL，可以直接采用头插法从头部取出一个结点，提供给用户使用； 如果大小为 2k 的链表为 NULL，就需要依次查看比
2
k
2^k
2 k
例如，用户向系统申请一块大小为 7 个字的空间，而系统总的内存为 24 个字，则此时按照伙伴系统的分配算法得出：
2
2
2^2
2 2
2
3
2^3
2 3
2
3
2^3
2 3 如果有，则从该链表中摘除一个结点，直接分配给用户使用； 如果没有，则需依次查看比
2
3
2^3
2 3
2
4
2^4
2 4
2
3
2^3
2 3
2
3
2^3
2 3
2
3
2^3
2 3
使用伙伴系统进行存储空间的管理过程中，在用户申请空间时，由于大小不同的空闲块处于不同的链表中，所以 分配完成的速度会更快，算法相对简单 。 无论使用什么内存管理机制，在内存回收的问题上都会面临一个共同的问题：如何把回收的内存进行有效地整合，伙伴系统也不例外。 当用户申请的内存块不再使用时，系统需要将这部分存储块回收，回收时需要判断是否可以和其它的空闲块进行合并。在寻找合并对象时，伙伴系统和边界标识法不同，在伙伴系统中每一个存储块都有各自的 伙伴 ，当用户释放存储块时只需要判断该内存块的伙伴是否为空闲块，如果是则将其合并，然后合并的新的空闲块还需要同其伙伴进行判断整合，反之直接将存储块根据大小插入到可利用空间表中即可 。 判断一个存储块的伙伴的位置时，采用的方法为：如果该存储块的起始地址为 p，大小为
2
k
2^k
2 k
{
p
+
2
k
，若
p
取余
2
k
+
1
=
0
p
−
2
k
，若
p
取余
2
k
+
1
=
2
k
\begin{cases} p+2^k，若p取余2^{k+1}=0\\\\ p-2^k，若p取余2^{k+1}=2^k\end{cases}
⎩
⎨
⎧ p + 2 k ，若 p 取余 2 k + 1 = 0 p − 2 k ，若 p 取余 2 k + 1 = 2 k
例如，当大小为
2
8
2^8
2 8
2
9
2^9
2 9
2
8
2^8
2 8
768
768
768
2
8
2^8
2 8
回收存储空间时，对于 空闲块的合并 ，不是取决于该空闲块的相邻位置的块的状态；而是 完全取决于其伙伴块 。所以即使其相邻位置的存储块时空闲块，但是由于两者不是伙伴的关系，所以也不会合并。这也就是该系统的缺点之一：由于 在合并时只考虑伙伴，所以容易产生存储的碎片 。
