0
00:00:00,000 --> 00:00:08,800
    

1
00:00:08,920 --> 00:00:11,000
好 接下来我们讲一个

2
00:00:11,040 --> 00:00:15,400
连续内存分配的实例 伙伴系统

3
00:00:15,440 --> 00:00:17,280
伙伴系统实际上是一种

4
00:00:17,320 --> 00:00:18,280
我们刚才说的

5
00:00:18,320 --> 00:00:20,600
连续存储分配一种办法

6
00:00:20,640 --> 00:00:22,880
它在这里比较好地折中了

7
00:00:22,920 --> 00:00:25,440
分配和回收过程当中

8
00:00:25,480 --> 00:00:30,080
这种合并和分配块的位置 碎片的问题

9
00:00:30,120 --> 00:00:31,360
具体怎么做的呢

10
00:00:31,400 --> 00:00:32,800
我们在这会分成两部分

11
00:00:32,840 --> 00:00:35,200
一个是对它基本做法有个介绍

12
00:00:35,240 --> 00:00:38,320
第二个是说在我们uCore实验系统里

13
00:00:38,360 --> 00:00:43,040
它的伙伴系统是怎么实现的接口

14
00:00:43,080 --> 00:00:44,960
伙伴系统实际上是

15
00:00:45,000 --> 00:00:49,760
它是把整个你可以分配的分区的大小

16
00:00:49,800 --> 00:00:52,240
约定为必须是2的幂

17
00:00:52,280 --> 00:00:55,320
这样做之后 任何一块要分的时候

18
00:00:55,360 --> 00:00:57,200
只是把它从中间切开

19
00:00:57,240 --> 00:00:59,440
它不会以其它方式来切

20
00:00:59,480 --> 00:01:01,920
只是两个小块合在一起

21
00:01:01,960 --> 00:01:03,760
变成一个更大的

22
00:01:03,800 --> 00:01:06,640
在这里头如果说你在分配的时候

23
00:01:06,680 --> 00:01:08,560
你需要一块它的大小

24
00:01:08,600 --> 00:01:12,760
实际上可用的块

25
00:01:12,800 --> 00:01:16,080
如果它的大小比你需要大小的2倍还大的话

26
00:01:16,120 --> 00:01:17,320
我就把它切一半

27
00:01:17,360 --> 00:01:19,000
然后再跟你来做比较

28
00:01:19,040 --> 00:01:22,800
如果说在这里你比它1/2还大

29
00:01:22,840 --> 00:01:25,120
但是没到当前大小的话

30
00:01:25,160 --> 00:01:27,200
它就直接把这块给你

31
00:01:27,240 --> 00:01:29,200
具体说起来就是

32
00:01:29,240 --> 00:01:32,680
如果说它比你2倍还大

33
00:01:32,720 --> 00:01:34,360
那我就把它切半

34
00:01:34,400 --> 00:01:36,680
切半之后仍然比你2倍还大

35
00:01:36,720 --> 00:01:38,280
那这个时候我在继续切半

36
00:01:38,320 --> 00:01:40,960
一直切到某一个状态

37
00:01:41,000 --> 00:01:43,120
那再切你就比它大了

38
00:01:43,160 --> 00:01:47,160
而当前状态是比你的2倍小

39
00:01:47,200 --> 00:01:49,440
这个时候我把这块就分给你

40
00:01:49,480 --> 00:01:51,040
那这个时候我们形成内碎片

41
00:01:51,080 --> 00:01:52,760
最大可能是多少

42
00:01:52,800 --> 00:01:57,320
最大可能是你这个大小的1/2减1

43
00:01:57,360 --> 00:01:58,880
也就是说你正好需要1/2的时候

44
00:01:58,920 --> 00:02:00,080
我就可以把它分半

45
00:02:00,120 --> 00:02:01,080
你再多一个字节

46
00:02:01,120 --> 00:02:04,240
我有可能就给了你差不多一倍的大小

47
00:02:04,280 --> 00:02:08,440
这是Buddy System它的基本道理

48
00:02:08,480 --> 00:02:11,960
下面我们来看伴侣系统的实现

49
00:02:12,000 --> 00:02:14,640
首先我们来看在伴侣系统当中

50
00:02:14,680 --> 00:02:16,480
我们需要维护的数据结构

51
00:02:16,520 --> 00:02:18,600
在这里头我们空闲块

52
00:02:18,640 --> 00:02:20,880
维护的是一个二维数组

53
00:02:20,920 --> 00:02:22,800
这个二维数组第一维

54
00:02:22,840 --> 00:02:24,880
是空闲块的大小

55
00:02:24,920 --> 00:02:27,040
由小到大我排成第一维

56
00:02:27,080 --> 00:02:31,280
在相同大小这些空闲块里头

57
00:02:31,320 --> 00:02:34,120
我按照它的地址排序排成第二维

58
00:02:34,160 --> 00:02:36,600
这是我们这里的空闲块的二维数组

59
00:02:36,640 --> 00:02:38,520
然后在起头的时候

60
00:02:38,560 --> 00:02:41,440
整个系统里只有一块空闲块

61
00:02:41,480 --> 00:02:44,760
这是整个空闲内存区域

62
00:02:44,800 --> 00:02:46,600
在分配的时候是什么呢

63
00:02:46,640 --> 00:02:50,320
分配的时候我是由小到大去找

64
00:02:50,360 --> 00:02:55,240
比我需要大小更大的空闲块

65
00:02:55,280 --> 00:02:56,960
如果说在初始状态下

66
00:02:57,000 --> 00:02:59,120
我找到整个这是一块

67
00:02:59,160 --> 00:03:01,320
这个时候我就会有第二步

68
00:03:01,360 --> 00:03:03,360
找到之后我会看

69
00:03:03,400 --> 00:03:04,640
如果这块过大

70
00:03:04,680 --> 00:03:06,120
所谓过大是什么意思呢

71
00:03:06,160 --> 00:03:11,720
就是我需要大小的二倍比你给出这块还小

72
00:03:11,760 --> 00:03:13,480
我就把它切成一半

73
00:03:13,520 --> 00:03:16,000
变成2的u-1次幂

74
00:03:16,040 --> 00:03:19,600
然后再看 这个大小跟我需要块的大小

75
00:03:19,640 --> 00:03:21,520
是不是还比它大

76
00:03:21,560 --> 00:03:23,000
是不是比它2倍大

77
00:03:23,040 --> 00:03:25,560
如果比它2倍还大我就继续分

78
00:03:25,600 --> 00:03:28,040
分完之后变成两个空闲块

79
00:03:28,080 --> 00:03:33,280
把它放到空闲块列表里去

80
00:03:33,320 --> 00:03:34,200
二维数组里头

81
00:03:34,240 --> 00:03:36,600
然后这个时候一直到找到

82
00:03:36,640 --> 00:03:41,520
我需要大小是空闲块1/2还大

83
00:03:41,560 --> 00:03:43,040
但是又没它本身大的时候

84
00:03:43,080 --> 00:03:44,880
这个时候我就把这块分给它

85
00:03:44,920 --> 00:03:47,880
这是分配的过程

86
00:03:47,920 --> 00:03:49,960
然后在这 我们通过一组

87
00:03:50,000 --> 00:03:52,400
实际的例子来看分配流程

88
00:03:52,440 --> 00:03:54,280
假定我最开始的时候

89
00:03:54,320 --> 00:03:55,960
它的大小是的1M

90
00:03:56,000 --> 00:03:58,680
然后在这里头我们需要是100K

91
00:03:58,720 --> 00:04:01,920
100K的话1M切成一半512

92
00:04:01,960 --> 00:04:05,200
256 128 切到128的时候

93
00:04:05,240 --> 00:04:07,680
能够满足我的要求

94
00:04:07,720 --> 00:04:10,280
这个时候切完之后的情况

95
00:04:10,320 --> 00:04:13,360
切成一半 再切一半 然后再切一半

96
00:04:13,400 --> 00:04:15,440
128 然后这个时候它的大小

97
00:04:15,480 --> 00:04:18,760
比我需要100K要大

98
00:04:18,800 --> 00:04:23,120
但是比我需要的100K的2倍200K要小

99
00:04:23,160 --> 00:04:25,880
OK那我就把这块分配给它

100
00:04:25,920 --> 00:04:29,520
第二个分配请求是240K

101
00:04:29,560 --> 00:04:31,720
240K那我们从这里看

102
00:04:31,760 --> 00:04:37,640
比它大256K 256K是比它大

103
00:04:37,680 --> 00:04:39,520
但是比它2倍要小

104
00:04:39,560 --> 00:04:41,200
这个我们应该要分配到这

105
00:04:41,240 --> 00:04:43,320
分配下来的结果是这样的

106
00:04:43,360 --> 00:04:46,680
给它分配256K的空间

107
00:04:46,720 --> 00:04:50,040
第三个是给它分配64K

108
00:04:50,080 --> 00:04:54,440
64K我们看比128小

109
00:04:54,480 --> 00:04:59,800
那128的1/2是64正合适

110
00:04:59,840 --> 00:05:01,880
那这个时候我把它分了

111
00:05:01,920 --> 00:05:05,120
把128K分成两半 搁在那里去了

112
00:05:05,160 --> 00:05:08,400
再下一个是说我需要256

113
00:05:08,440 --> 00:05:12,160
那256我们在这里空闲的只有512比它大

114
00:05:12,200 --> 00:05:14,120
切成1/2

115
00:05:14,160 --> 00:05:17,560
这是分配之后的结果

116
00:05:17,600 --> 00:05:22,120
然后再往下我们是释放B

117
00:05:22,160 --> 00:05:23,200
释放完了之后

118
00:05:23,240 --> 00:05:26,960
按照我们原来连续分区的分配

119
00:05:27,000 --> 00:05:29,720
我有一个合并的问题

120
00:05:29,760 --> 00:05:32,560
我们说这块回来之后

121
00:05:32,600 --> 00:05:34,760
它没有办法跟64K合并

122
00:05:34,800 --> 00:05:36,200
因为合完之后的大小

123
00:05:36,240 --> 00:05:38,200
不是我们前面说正好是2倍

124
00:05:38,240 --> 00:05:42,440
也没办法放回到空闲分区的数组里去

125
00:05:42,480 --> 00:05:45,240
这个时候我就变成两个空闲分区

126
00:05:45,280 --> 00:05:49,760
然后我再释放A那128K还回去

127
00:05:49,800 --> 00:05:52,120
它也没有办法跟别人合并

128
00:05:52,160 --> 00:05:53,680
它是单独一个

129
00:05:53,720 --> 00:05:56,080
然后这个时候我申请一个75K

130
00:05:56,120 --> 00:05:58,280
75K仍然可以放到那儿

131
00:05:58,320 --> 00:06:03,400
这个时候换成75K 给了它128K

132
00:06:03,440 --> 00:06:05,200
这个时候我再看

133
00:06:05,240 --> 00:06:07,360
这个时候把C释放掉

134
00:06:07,400 --> 00:06:08,760
这个C释放掉的时候

135
00:06:08,800 --> 00:06:10,920
这个地方一个64

136
00:06:10,960 --> 00:06:13,320
和旁边64它两合起来的时候

137
00:06:13,360 --> 00:06:15,640
正好是原来128

138
00:06:15,680 --> 00:06:18,880
可以把它合在一起

139
00:06:18,920 --> 00:06:20,200
这个时候就变成128了

140
00:06:20,240 --> 00:06:22,000
128和这个能合吗

141
00:06:22,040 --> 00:06:24,360
不能合它不能构成2的幂

142
00:06:24,400 --> 00:06:28,440
即使的能构成2的幂 它也还会有问题

143
00:06:28,480 --> 00:06:30,800
然后这个时候我再释放E

144
00:06:30,840 --> 00:06:34,120
把这几个最后它们三个就会合在一起

145
00:06:34,160 --> 00:06:39,360
最后再还回D 整个过程结束

146
00:06:39,400 --> 00:06:41,800
那么这个时候它把整个合在一起

147
00:06:41,840 --> 00:06:42,880
在这个过程当中

148
00:06:42,920 --> 00:06:46,920
我们已经看到了它分配的时候情况

149
00:06:46,960 --> 00:06:49,800
我找一个比它大的 最小的空闲块

150
00:06:49,840 --> 00:06:51,640
然后看看是不是比它2倍大

151
00:06:51,680 --> 00:06:53,320
如果是 切半

152
00:06:53,360 --> 00:06:55,280
如果不是 OK就是它

153
00:06:55,320 --> 00:06:57,200
这样我们分配的过程就有了

154
00:06:57,240 --> 00:06:58,960
接下来我们把刚才说的

155
00:06:59,000 --> 00:07:02,000
合并的事再明确一下

156
00:07:02,040 --> 00:07:04,280
合并的时候我放到空闲块里头

157
00:07:04,320 --> 00:07:06,400
比如说我在这里分配任何一块

158
00:07:06,440 --> 00:07:08,680
合并的时候需要满足条件

159
00:07:08,720 --> 00:07:14,200
那满足条件是什么样呢

160
00:07:14,240 --> 00:07:16,000
大家看看 我在这里头

161
00:07:16,040 --> 00:07:17,720
如果这块还回去

162
00:07:17,760 --> 00:07:20,160
它可以和哪块合并

163
00:07:20,200 --> 00:07:22,280
和这块能合吗 大小不一样

164
00:07:22,320 --> 00:07:26,360
这是大小一样的 到底它和那块合

165
00:07:26,400 --> 00:07:29,040
我们在这里 第一个条件

166
00:07:29,080 --> 00:07:32,920
就是相邻的两块必须大小是一样的

167
00:07:32,960 --> 00:07:36,760
然后第二个 它必须是相邻的

168
00:07:36,800 --> 00:07:38,480
如果说你隔的话

169
00:07:38,520 --> 00:07:39,680
它是合不到一起的

170
00:07:39,720 --> 00:07:41,640
在这我们也没有移

171
00:07:41,680 --> 00:07:44,520
还有条件吗 

172
00:07:44,560 --> 00:07:48,320
还有就是比如这三块

173
00:07:48,360 --> 00:07:51,920
如果这块和这块合那是不行的

174
00:07:51,960 --> 00:07:54,680
原因在于它俩的起始位置搁完之后

175
00:07:54,720 --> 00:07:57,880
这同属于上面两个分支

176
00:07:57,920 --> 00:07:59,720
这种直观意思表达

177
00:07:59,760 --> 00:08:01,440
实际上形式化表达出来就是

178
00:08:01,480 --> 00:08:03,480
相邻的两块 低的地址

179
00:08:03,520 --> 00:08:05,480
必须是2的整数次幂

180
00:08:05,520 --> 00:08:07,080
如果像这个地方

181
00:08:07,120 --> 00:08:11,160
它没办法是它的整数次幂了

182
00:08:11,200 --> 00:08:14,520
这个时候我们第三个条件就是

183
00:08:14,560 --> 00:08:16,560
低地址的空闲块起始地址

184
00:08:16,600 --> 00:08:22,040
必须是块大小的2倍的整数倍

185
00:08:22,080 --> 00:08:23,040
有了这个之后

186
00:08:23,080 --> 00:08:25,480
那我们的伴侣系统就可以

187
00:08:25,520 --> 00:08:28,200
在实际系统当中来进行使用了

188
00:08:28,240 --> 00:08:31,120
目前在我们用到的Linux Unix

189
00:08:31,160 --> 00:08:33,880
都有Buddy System的实现

190
00:08:33,920 --> 00:08:38,080
它是用来做内核里的存储分配

191
00:08:38,120 --> 00:08:41,520
如果有同学想继续去了解它的实现

192
00:08:41,560 --> 00:08:43,480
在这有一些参考信息

193
00:08:43,520 --> 00:08:46,480
网上也有很详细一些实现

194
00:08:46,520 --> 00:08:48,040
大家可以去参考

195
00:08:48,080 --> 00:08:50,680
接下来我们说

196
00:08:50,720 --> 00:08:53,960
在我们用到uCore系统里头

197
00:08:54,000 --> 00:08:57,200
我的内存分配到底怎么做

198
00:08:57,240 --> 00:09:00,080
这个地方 把物理内存的管理

199
00:09:00,120 --> 00:09:02,200
提供了一个标准接口

200
00:09:02,240 --> 00:09:05,640
在这个接口里 实现了一组函数

201
00:09:05,680 --> 00:09:08,440
和相应的一些保存的信息

202
00:09:08,480 --> 00:09:11,120
第一个是管理算法的名字

203
00:09:11,160 --> 00:09:12,440
给了一个字符串做标识

204
00:09:12,480 --> 00:09:14,440
然后有一个初始化

205
00:09:14,560 --> 00:09:15,720
然后有一个检查

206
00:09:15,800 --> 00:09:17,840
这个基本上是辅助性的函数

207
00:09:17,960 --> 00:09:18,760
上来初始化的时候

208
00:09:18,840 --> 00:09:21,080
是我数据结构的起头

209
00:09:21,120 --> 00:09:23,200
检查是我在这个地方

210
00:09:23,240 --> 00:09:25,680
我函数写完了之后是不是好使

211
00:09:25,720 --> 00:09:27,720
我的一些测试就放在这个里头

212
00:09:27,760 --> 00:09:32,240
中间我们关心主要的函数是这两个

213
00:09:32,280 --> 00:09:34,360
是分配和回收

214
00:09:34,400 --> 00:09:37,120
当然在分配和回收分给一个进程之后

215
00:09:37,160 --> 00:09:38,280
我们在用的时候

216
00:09:38,320 --> 00:09:40,480
还得把它映射到进程的地址空间里

217
00:09:40,520 --> 00:09:42,080
所以会有上边这一个函数

218
00:09:42,120 --> 00:09:43,320
和底下这个函数

219
00:09:43,360 --> 00:09:44,840
底下这个函数是告诉你

220
00:09:44,880 --> 00:09:48,640
这个空闲分区里还有多大空间

221
00:09:48,680 --> 00:09:50,680
我们在这里要实现的时候

222
00:09:50,720 --> 00:09:52,920
实际上你就实现这两个函数就行了

223
00:09:52,960 --> 00:09:57,440
在我们uCore已经有Buddy System

224
00:09:57,480 --> 00:09:59,160
实现伴侣系统

225
00:09:59,200 --> 00:10:00,840
在这里实际上我们最后

226
00:10:00,880 --> 00:10:02,240
就把你函数写好之后

227
00:10:02,280 --> 00:10:03,920
只需要往这里一填

228
00:10:03,960 --> 00:10:05,240
把你函数名字填进去

229
00:10:05,280 --> 00:10:06,920
内核里的上层服务就可以

230
00:10:06,960 --> 00:10:11,400
用它来分配自己所需要存储空间了

231
00:10:11,440 --> 00:10:13,400
这个地方我们要填的

232
00:10:13,440 --> 00:10:16,040
从分配和回收的角度来讲

233
00:10:16,080 --> 00:10:18,160
主要填的是这两个函数

234
00:10:18,200 --> 00:10:21,640
具体的内容大家可以下去看代码

235
00:10:21,680 --> 00:10:23,080
好 到这个地方为止

236
00:10:23,120 --> 00:10:24,280
我们就说清楚了

237
00:10:24,320 --> 00:10:28,480
连续存储分配里头 它如何在做

238
00:10:28,520 --> 00:10:30,840
在这里要面临一些什么问题

239
00:10:30,880 --> 00:10:34,080
我们目前有一些什么样的解决方式

240
00:10:34,120 --> 00:10:38,200
这些解决方式都是从什么角度来考虑的

241
00:10:38,240 --> 00:10:40,680
今天的课就上到这里 下课

242
00:10:40,720 --> 00:10:41,040


243
00:10:41,080 --> 00:10:41,120