动态存储管理之伙伴系统

缘起

【1】中我们介绍了动态内存管理的边界标识算法, 特点是能够支持高效的回收.

本文继续介绍动态内存管理, 内容是伙伴系统.

分析

伙伴系统的链表上的节点长如下这个样子

而整个伙伴系统的数据结构如下

即向量+链表（2种线性表组合）的数据结构，类似于图的邻接链表表示法. 假设数组名叫做BuddySystem

伙伴系统比较tricky的地方利用了 2的次幂的二分特性.

即一块2^k的内存拆分成两块就变成了2块 2^(k-1)的内存. 则这两块内存就可以插入到别的链表上去了. 基于此，伙伴系统的分配内存的算法可以描述为

我申请的空间n满足

1
2^(k-i)< n <=2^(k-i+1)

则我照理应该将BuddySystem[k-i+1]上的一个节点给它，但是很不幸，我们BuddySystem[k-i+1]上如果没有任何节点的话, 则我们只能往大里找，譬如 BuddySystem[k]上有节点. 我们知道，BuddySystem[k]这根链表上的节点的内存大小都是 2^k字节的. 所以我们只能从BuddySystem[k]上拿一个节点，这个节点的大小是2^k的，所以取出 2^(k-i+1)大小的内存给申请者，然后余下的进行如下的划分

划分出来的内存块依次插入到其他BuddySystem的链表中去. 说难听点，就是把BuddySystem[k]上的某个节点（为了常数时间操作，就取头结点）五马分尸了.

显然，伙伴系统的实现比【1】中的边界标识法要简单.

下面考虑伙伴系统的内存回收. 和【1】一样，回收内存块的时候，依旧要考虑合并地址邻近的内存块防止碎片的问题.

注意，伙伴系统的回收算法就体现了何谓伙伴了?

所谓的伙伴，就是原本从一块大内存中分出来的叫伙伴. 例如下图中的A和B是伙伴，C和D是伙伴，但是B和C，纵使他们地址相邻，依旧不是伙伴.

不是伙伴的内存块是不能合并的, 例如上图中B和C尽管相邻，并且还都是空闲块，但是不能合并，为什么? 否则的话，就和分配算法不符，导致分配出现问题. 所以回收算法是回收一块内存之后，要先判定其伙伴是否是空闲块，如果是的话，则合并之（对合并之后的大块进行同样的算法），并从伙伴系统中删除此伙伴，否则插入此内存块.

所以伙伴系统的特点是实现简单，速度较快，但是缺点是只归并伙伴，容易出现碎片.

那么怎么快速求出一块内存的伙伴呢?

这是不难理解的

伙伴系统算法实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include "stdafx.h"
#include <iostream>

using namespace std;

const int m = 16; // 伊始堆的大小是 2^16 字节

const int INITIALSIZE = 1<<m; // 伊始是2^16字节的堆

typedef struct MemoryBlock
{
	MemoryBlock *next; // 指向下一个内存块的指针
	int tag; // 块的占用标识 0标识空闲，1表示占用
	int index; // 块大小为 1<<index, 或者说该节点在 buddySystem[index]链表中
	MemoryBlock *prev; // 指向前一个内存块的指针, 这里是一个双向链表
	char space[INITIALSIZE]; // 空白区域（即本节点可用的内存块）

	MemoryBlock():next(this), prev(this), tag(0), index(m){}
} MemoryBlock, *BuddyNode;

BuddyNode buddySystem[m+1]; // 伙伴系统

inline int controlsize() // 控制信息
{
	return (sizeof(int)+sizeof(BuddyNode))<<1; // 2个int 2根指针
}

BuddyNode alloc(int n) // 申请n字节的内存, 返回相应的BuddyNode
{
	int k;
	n+=controlsize(); // 要加上控制信息（2个int，2根指针），换言之，哪怕请求1个字节的空间，也需要分配17个字节的空间给我, 而且这16个字节的控制信息是不能被申请者覆盖的, 不然的话，回收内存的时候会遇到问题的（这个和边界标识法是一样的）.
	for (k = 0;k<=m && ((1<<k) < n || !buddySystem[k]); k++); // 什么情况下k要++, 2^k比n+16(16是控制信息，2根指针，2个int,一共16字节, 但是和边界标识法相比比较好的地方在与这里是整块的分配内存)小, 或者当前伙伴系统的头结点为空
	if (k>m) return 0; // 没找到
	// 说明 n <= 1<<k, 我们要把 buddySystem[k]上的一个节点分配给请求, 但是因为 buddySystem[i]可能为null，所以1<<(k-1) < n未必成立
	BuddyNode head = buddySystem[k]; // buddySystem[k]链表的头结点
	if (head == head->next) buddySystem[k] = 0;// 如果只有一个头结点了
	else // 则取出头结点
	{
		head->prev->next = head->next;
		head->next->prev = head->prev;
		buddySystem[k] = head->next; // 移除head
	}
	// 找到了要分尸的节点head， 开始把它大卸八块了.  注意  n<=2^k
	int i = 1;
	while(1)
	{
		if (n>(1<<(k-i))) // 则 n 位于 (2^(k-i), 2^(k-i+1)]内, 则分配出去就行了
		{
			head->tag = 1; // 占用块了
			head->index = k-i+1;
			return head;
		}
		else // n<= (1<<(k-i))
		{
			BuddyNode split = (BuddyNode)((int)head + (1<<(k-i))); // 分裂出来的空闲块
			split->tag = 0;
			split->index = k-i;
			split->next = split->prev = split;
			if (buddySystem[k-i])
			{
				buddySystem[k-i]->prev->next = split;
				split->prev = buddySystem[k-i]->prev;
				split->next = buddySystem[k-i]->next;
				buddySystem[k-i]->next->prev = split;
			}
			else // 如果原本buddySystem[k-i]就是空链表, 则简单赋值即可
			{
				buddySystem[k-i] = split;
			}
			i++; // 进入下一轮
		}
	}

}

BuddyNode getBuddy(BuddyNode p, bool &flag) // 求出p地址的节点的伙伴, flag为true，表示buddy是p的左邻, 否则是右舍
{
	int dis = (int)p - (int)buddySystem; // p距离数组首位的距离(字节数)
	if (!(dis % (1<<(p->index+1))))
	{
		flag = false;
		return (BuddyNode)((int)p + (1<<p->index));
	}
	flag = true;
	return (BuddyNode)((int)p - (1<<p->index));
}

void recycle(BuddyNode p) // 回收内存p,p指向回收的内存块
{
	bool flag;
	BuddyNode buddy = getBuddy(p, flag); // 求出p的伙伴
	while(!buddy->tag) // 只要伙伴空闲
	{
		// 在buddy所在链表中移除buddy
		BuddyNode first = buddySystem[buddy->index];
		while(first!=buddy)first = first->next; // 找到buddy
		first->prev->next = first->next;
		first->next->prev = first->prev; // 在链表中移除buddy节点(即buddy指向的伙伴节点)
		// 合并buddy和p
		if (flag) // 如果buddy是p的左邻，则p并入buddy
		{
			buddy->index++;
			// 再将buddy头插入buddySystem[buddy->index]中去
			buddySystem[buddy->index]->prev->next = buddy;
			buddy->prev = buddySystem[buddy->index]->prev;
			buddy->next = buddySystem[buddy->index]->next;
			buddySystem[buddy->index]->prev = buddy;
			p = buddy; // p指向合并之后的空闲块(注意，buddy本身是空闲块)
		}
		else // buddy是p的右舍，buddy并入p
		{
			p->index++;
			p->tag = 0; // 空闲块了
			// 再将p头插入buddySystem[p->index]中去
			buddySystem[p->index]->prev->next = p;
			p->prev = buddySystem[p->index]->prev;
			p->next = buddySystem[p->index]->next;
			buddySystem[p->index]->prev = p;
		}
		buddy = getBuddy(p, flag); // 重新获取p的伙伴
	}
	// 最后buddy不再是空闲块, 则p就要插入了
	// 再将p头插入buddySystem[p->index]中去
	if (buddySystem[p->index]) // 如果原本不空, 则可以这样
	{
		buddySystem[p->index]->prev->next = p;
		p->prev = buddySystem[p->index]->prev;
		p->next = buddySystem[p->index]->next;
		buddySystem[p->index]->prev = p;
	}
	else
	{
		buddySystem[p->index] = p;
	}
	
}


int main()
{
	buddySystem[m] = new MemoryBlock(); // 初始化伙伴系统，伊始就是一块堆内存

	BuddyNode m1 =  alloc(16);
	if (!m1) puts("空间不足, 申请失败!");
	BuddyNode m2 = alloc(32);
	if (!m2) puts("空间不足, 申请失败!");
	BuddyNode m3 = alloc(37);
	if (!m3) puts("空间不足, 申请失败!");
	BuddyNode m4 = alloc(46);
	if (!m4) puts("空间不足, 申请失败!");
	BuddyNode m5 = alloc(117);
	if (!m5) puts("空间不足, 申请失败!");
	BuddyNode m6 = alloc(246);
	if (!m6) puts("空间不足, 申请失败!");
	BuddyNode m7 = alloc(1023);
	if (!m7) puts("空间不足, 申请失败!");
	BuddyNode m8 = alloc(3446);
	if (!m8) puts("空间不足, 申请失败!");
	BuddyNode m9 = alloc(777);
	if (!m9) puts("空间不足, 申请失败!");
	BuddyNode m10 = alloc(376);
	if (!m10) puts("空间不足, 申请失败!");
	BuddyNode m11 = alloc(2);
	if (!m11) puts("空间不足, 申请失败!");

	recycle(m4);

	recycle(m7);

	return 0;
}

参考

【1】https://yfsyfs.github.io/2019/06/12/%E5%8A%A8%E6%80%81%E5%AD%98%E5%82%A8%E7%AE%A1%E7%90%86%E4%B9%8B%E8%BE%B9%E7%95%8C%E6%A0%87%E8%AF%86%E6%B3%95/