好 接下来我们讲一个
连续内存分配的实例 伙伴系统
伙伴系统实际上是一种
我们刚才说的
连续存储分配一种办法
它在这里比较好地折中了
分配和回收过程当中
这种合并和分配块的位置 碎片的问题
具体怎么做的呢
我们在这会分成两部分
一个是对它基本做法有个介绍
第二个是说在我们uCore实验系统里
它的伙伴系统是怎么实现的接口
伙伴系统实际上是
它是把整个你可以分配的分区的大小
约定为必须是2的幂
这样做之后 任何一块要分的时候
只是把它从中间切开
它不会以其它方式来切
只是两个小块合在一起
变成一个更大的
在这里头如果说你在分配的时候
你需要一块它的大小
实际上可用的块
如果它的大小比你需要大小的2倍还大的话
我就把它切一半
然后再跟你来做比较
如果说在这里你比它1/2还大
但是没到当前大小的话
它就直接把这块给你
具体说起来就是
如果说它比你2倍还大
那我就把它切半
切半之后仍然比你2倍还大
那这个时候我在继续切半
一直切到某一个状态
那再切你就比它大了
而当前状态是比你的2倍小
这个时候我把这块就分给你
那这个时候我们形成内碎片
最大可能是多少
最大可能是你这个大小的1/2减1
也就是说你正好需要1/2的时候
我就可以把它分半
你再多一个字节
我有可能就给了你差不多一倍的大小
这是Buddy System它的基本道理
下面我们来看伴侣系统的实现
首先我们来看在伴侣系统当中
我们需要维护的数据结构
在这里头我们空闲块
维护的是一个二维数组
这个二维数组第一维
是空闲块的大小
由小到大我排成第一维
在相同大小这些空闲块里头
我按照它的地址排序排成第二维
这是我们这里的空闲块的二维数组
然后在起头的时候
整个系统里只有一块空闲块
这是整个空闲内存区域
在分配的时候是什么呢
分配的时候我是由小到大去找
比我需要大小更大的空闲块
如果说在初始状态下
我找到整个这是一块
这个时候我就会有第二步
找到之后我会看
如果这块过大
所谓过大是什么意思呢
就是我需要大小的二倍比你给出这块还小
我就把它切成一半
变成2的u-1次幂
然后再看 这个大小跟我需要块的大小
是不是还比它大
是不是比它2倍大
如果比它2倍还大我就继续分
分完之后变成两个空闲块
把它放到空闲块列表里去
二维数组里头
然后这个时候一直到找到
我需要大小是空闲块1/2还大
但是又没它本身大的时候
这个时候我就把这块分给它
这是分配的过程
然后在这 我们通过一组
实际的例子来看分配流程
假定我最开始的时候
它的大小是的1M
然后在这里头我们需要是100K
100K的话1M切成一半512
256 128 切到128的时候
能够满足我的要求
这个时候切完之后的情况
切成一半 再切一半 然后再切一半
128 然后这个时候它的大小
比我需要100K要大
但是比我需要的100K的2倍200K要小
OK那我就把这块分配给它
第二个分配请求是240K
240K那我们从这里看
比它大256K 256K是比它大
但是比它2倍要小
这个我们应该要分配到这
分配下来的结果是这样的
给它分配256K的空间
第三个是给它分配64K
64K我们看比128小
那128的1/2是64正合适
那这个时候我把它分了
把128K分成两半 搁在那里去了
再下一个是说我需要256
那256我们在这里空闲的只有512比它大
切成1/2
这是分配之后的结果
然后再往下我们是释放B
释放完了之后
按照我们原来连续分区的分配
我有一个合并的问题
我们说这块回来之后
它没有办法跟64K合并
因为合完之后的大小
不是我们前面说正好是2倍
也没办法放回到空闲分区的数组里去
这个时候我就变成两个空闲分区
然后我再释放A那128K还回去
它也没有办法跟别人合并
它是单独一个
然后这个时候我申请一个75K
75K仍然可以放到那儿
这个时候换成75K 给了它128K
这个时候我再看
这个时候把C释放掉
这个C释放掉的时候
这个地方一个64
和旁边64它两合起来的时候
正好是原来128
可以把它合在一起
这个时候就变成128了
128和这个能合吗
不能合它不能构成2的幂
即使的能构成2的幂 它也还会有问题
然后这个时候我再释放E
把这几个最后它们三个就会合在一起
最后再还回D 整个过程结束
那么这个时候它把整个合在一起
在这个过程当中
我们已经看到了它分配的时候情况
我找一个比它大的 最小的空闲块
然后看看是不是比它2倍大
如果是 切半
如果不是 OK就是它
这样我们分配的过程就有了
接下来我们把刚才说的
合并的事再明确一下
合并的时候我放到空闲块里头
比如说我在这里分配任何一块
合并的时候需要满足条件
那满足条件是什么样呢
大家看看 我在这里头
如果这块还回去
它可以和哪块合并
和这块能合吗 大小不一样
这是大小一样的 到底它和那块合
我们在这里 第一个条件
就是相邻的两块必须大小是一样的
然后第二个 它必须是相邻的
如果说你隔的话
它是合不到一起的
在这我们也没有移
还有条件吗
还有就是比如这三块
如果这块和这块合那是不行的
原因在于它俩的起始位置搁完之后
这同属于上面两个分支
这种直观意思表达
实际上形式化表达出来就是
相邻的两块 低的地址
必须是2的整数次幂
如果像这个地方
它没办法是它的整数次幂了
这个时候我们第三个条件就是
低地址的空闲块起始地址
必须是块大小的2倍的整数倍
有了这个之后
那我们的伴侣系统就可以
在实际系统当中来进行使用了
目前在我们用到的Linux Unix
都有Buddy System的实现
它是用来做内核里的存储分配
如果有同学想继续去了解它的实现
在这有一些参考信息
网上也有很详细一些实现
大家可以去参考
接下来我们说
在我们用到uCore系统里头
我的内存分配到底怎么做
这个地方 把物理内存的管理
提供了一个标准接口
在这个接口里 实现了一组函数
和相应的一些保存的信息
第一个是管理算法的名字
给了一个字符串做标识
然后有一个初始化
然后有一个检查
这个基本上是辅助性的函数
上来初始化的时候
是我数据结构的起头
检查是我在这个地方
我函数写完了之后是不是好使
我的一些测试就放在这个里头
中间我们关心主要的函数是这两个
是分配和回收
当然在分配和回收分给一个进程之后
我们在用的时候
还得把它映射到进程的地址空间里
所以会有上边这一个函数
和底下这个函数
底下这个函数是告诉你
这个空闲分区里还有多大空间
我们在这里要实现的时候
实际上你就实现这两个函数就行了
在我们uCore已经有Buddy System
实现伴侣系统
在这里实际上我们最后
就把你函数写好之后
只需要往这里一填
把你函数名字填进去
内核里的上层服务就可以
用它来分配自己所需要存储空间了
这个地方我们要填的
从分配和回收的角度来讲
主要填的是这两个函数
具体的内容大家可以下去看代码
好 到这个地方为止
我们就说清楚了
连续存储分配里头 它如何在做
在这里要面临一些什么问题
我们目前有一些什么样的解决方式
这些解决方式都是从什么角度来考虑的
今天的课就上到这里 下课