接下来我们介绍连续内存分配
我们说 在分配内存空间的时候
我们首先第一个
在没有其它的技术支持的情况下
分配给一个进程的地址空间必须是连续的
为了提高利用效率
那我希望分的位置有适度的选择
这些动态分配算法
实际上就是你在去选择的做法
而选择完之后
你用每一个进程可能用的时间长短不一样
有的进程先结束
有的进程后结束
这个时候 有可能先结束的会留出一些空
后面一个在分配的时候又会再去找
这个过程的执行
就会在中间留下一些碎片
这些碎片对于我们后续的分配是会有影响的
我们就从如何去找你要用的空闲分区
和如何来处理不能利用的这些
小的空闲分区的两个角度来看
连续内存分配算法
连续内存分配 是指给进程分配一块
不小于指定大小的
物理连续的一块内存区域
这个地方是一个图示
说我进程不断的分配回收
分配了三个 进程二就释放掉了
这个时候是我内存分配时候的状态
每一个进程的地址空间里头
我们可能存放的是代码 数据
堆栈 这些内容
那在这些中间
我们就会有一些区域没办法利用了
比如说像这里头
这有一块 这有一小块
中间如果你要分配四块的话
这小块也没法用了
对于这些没法利用的区域
我们就称之为是碎片
这些碎片它是没办法利用的
这个没办法利用 是相对而言的
如果说你要得小块
其中这块还是可以利用的
但是有一些你是无论如何用不起来的
这些碎片 我们把它分成两种情况
一个是叫外碎片
外碎片是两块之间的这一块
实际上它也是一个小的空闲块
只是由于它过小
而其它进程申请的区域的大小都大于它
而导致这块没法利用
另一种情况是内碎片
内碎片是分配给进程的区域内部的
一些没法利用的区域
什么情况下会出现这种（情况）呢
如果说我分配的时候
并不是说我可以准确地分配你所指定的大小
比如说 你想分配510字节
但是实际上我们在分配的时候
只能是以512字节这种
2的整数幂为单位的大小
那剩下的几个字节你就没办法利用了
像这些我们称之为叫内碎片
对于我这来讲
P1和P3上边剩的这段就是这种情况
那是由于它要取整所导致的
那我们在分配的时候
希望尽可能减少这种碎片的出现
从而使得我在利用的时候
比如说这种情况
我想分配一个六块的
那么这两个在这里头是没办法利用的
如果它两个是在一起的
这个事就是行的
我们来看动态分区分配
动态分区分配实际上是说
我在分配的时候
我可以指定大小
并且这个大小是用户指定的时候可变的
那我们分配出来结果
称之为叫一个分区
也可能叫内存块 也可能叫块
分配出来的地址是连续的
对于这边是一个例子
第一个进程 分配
第二个进程 接着来
刚开始的时候我可以顺序地分配
这事比较容易
在用的过程当中
某些进程就会结束
那结束掉就还回来了
对于这种情况
现在我要想再分配的话
我就必须知道我哪些内存区域
已经分配给了进程
哪些内存区域还是空闲的
实际上在这时候
我们操作系统就要
维护这样两个数据结构
一个是已分配的分区
我们就需要知道
哪些是已经分配出去的
它分配给了谁
第二个是空闲分区
我需要知道空闲分区的位置和大小
对于我不同的找法
这两个数据结构的组织形式
是会有一些变化的
在不同组织形式下
你在找分区或者说把分区释放的时候
放回到分区列表里的时候
它的开销是会不一样的
这是我们在这需要考虑的问题
对于找分区的不同
我们在这就有这样几种
动态分区的分配策略
大家通常想要是说我要分配一块区域
我给你指定大小
这个个时候你去分你去找
你可能会碰到一个我就找一个
这就是我们这里的第一种情况 最先匹配
你找着哪一个
碰到哪一个就是那个
我也可以是说我找最佳的
叫最佳匹配
它是什么意思
我把所有这些空闲的我全看一遍
看看这里头 哪一个是比我大
但是又是大的最少那个
如果说 你是这些空闲分区
你是按地址顺序排的
那你就把整个全部找一遍
如果说我在这里
是按照它的大小排的
那我就是从小往上找
找到第一个就行了
这是你空闲分区排序办法的不同
我找的时候开销是不一样的
还一种是最差匹配
我去找
每次用的时候我用的是最大的
用最大就相当于实际上我是按照由大到小排序
我的第一个肯定就是它了
这是几种基本分区的分配策略
下面我们具体来看
第一种 最先匹配策略
在这里 它的思路很简单
你要分配多少字节
我就从空闲分区列表里
去找第一个可以找着比它大的
比如说在这里头我是按照地址顺序排的
这个时候我在这我去找
我这个黄颜色是我空闲的
我这给了一个例子
说我想找一个400字节的
我上来看 这个地方是1K
OK 它就是比我想要的大
那就是它了
分配完了之后变成什么呢
分配完了之后
一块被你申请的进程所占用
我把它放到已分配分区的列表去
并且注明它是哪一个进程占用的
然后这个时候还剩一点
剩一点我又把它描述成另外一个
小个的空闲分区
接着把它放到空闲分区列表里头去
在这里头如果按照地址排的话
那我就是在哪
这个思路就是这样的
那我们再看你在这里做的时候
它实现办法是什么
我的空闲分区是按照地址顺序排的
然后分配的时候怎么做
分配的时候从前往后找
找第一个所谓的合适
就是大于我指定的大小就可以了
释放的时候 我在还回来的时候我放回去
按照地址把它插到里面去了
并且看它前后是否有临近的空闲分区
这个时候我把它合并到一起
这个时候找和合并的开销都是比较小的
但是它在这里头
因为我们每一次都是从头找
这样的话你都在前面能找到的时候
它就不会往后找
所以这样一来
它的另外一个好处是
在高地址的区域里头
它会留下一些比较大块的分区
你在后续要申请大块的时候
我是能找着的
如果我大块都切成了小块
那这你就找不着了
这是它的优点
它的缺点是说我会有外碎片
我每一次切的时候
如果大小不合适我都会切成俩
这个时候就会留下一个小的空闲分区
如果这个小个空闲分区多到一定程度
这时候你在后面往下分配大块的时候
它就得从前往后找
也就相当于前面很长一段你找不到
由于你找不到 你就只能往后找
那这个时候往后找的这个过程
开销就会越来越大
也就相当于越往后
你在前面搜索的时间就会越长
这是第一种算法最先匹配
它的好处和缺点
那么第二种方法是最佳匹配
也就是说它找到一个比它大
并且是最小的空闲分区
如果说在这里头
像在这里这个例子
我们要想分配400个字节
那1K 2K 500字节
这三个比较起来
这个是比它大并且是大的最少的
那我们在这来分配
分配完的结果变成什么样子
我前两个不动
第三个把它切成两个
留下一个小的100字节的空闲分区
另外一个作为已分配的
对它做相应的标识
告诉它分配给了哪个进程
那这个事就算搞定了
我们看在这里头
我需要维护的数据结构是什么样子的
首先第一个
空闲分区我怎么来排序
因为我是找比它大最小的一个
我找的时候是从小往大找
所以我的空闲分区
如果是从小往大排序
我开始是比它小的
第一个比它大的
OK这就是我想要找的
如果前面比它小的数目比较少
我很快就能找着
分配的时候 我是从前往后找
释放的时候
我就看 跟它临近的进行合并
这个时候就有一个问题
临近的话我就是需要去找它地址临近的
并不是大小临近的
正是因为这样一来
按地址排序的 你合并的时候
它的算法就会复杂一些
花的时间就会长一些
这种做法它的好处是我可以把较大的块
如果说我分配块的尺度
都是比较小的时候
这个时候它的效果是比较好的
如果说你分配大的
那这个时候它后边剩的就会少了
这个时候它会有什么好处呢
避免大的分区被拆分
因为你找的是比它大的最小的那个
然后它可以减少外碎片的尺寸
也就是说剩下那块
一定是我能找的这一块里
剩下的最小那块
然后相对来说它比较简单
缺点是说你剩的那块边角料是小了
但剩的越小这块边角料它越没法利用
所以它有外碎片
并且是释放分区的时候它会比较复杂
然后剩下那些小碎片基本上也就没用了
这是最佳匹配
然后还有一种做法我们是最差匹配
它的做法我找最大的
有可能是说我找最大
也不满足我的要求
这是找不到了
那这里头我们找了一个最大的
比如说在这里这个例子
我要分配400字节
那这个时候找哪个呢
最大的这是2K
我把它切成两块
在这里 这块标记已分配
剩下这一块还有1K多比这块还大
它可以被利用的机会就会更多
这是最差匹配它所带来的好处
具体做法是
这个地方空闲分区排序要怎么排
这个时候由大到小排
我每次找的时候
只要第一个满足要求
那就是我要找的
第一个不满足要求 我就没有了
这时候分配的时候就是找最大的一个
也是找第一个 找的速度是最快的
然后释放的时候 我要去找它临近的
由于我排序不是按地址排的
你找临近就需要去顺序找了
找着临近的 然后把它合在一起
放回到空闲分区列表时候
我还要去找放的位置
因为你原来是按大小排序的
现在你仍然需要按照原来大小的去排
要不然下次找的时候就不对了
这个时候它有什么好处
如果说你的中等尺度的分配比较多
这个时候效果是比较好的
因为我用掉那块不是很大
然后剩的那块多的时候还能利用起来
相当于我剩的小块就比较少了
剩的那块我还可以找到用处
实际上这个时候关键是
剩的那块能给它找什么样的用处
它的缺点是释放的过程比较慢
因为释放之后的合并是要进行搜索的
它排序跟我这个合并没有关系
然后也会有外部碎片
如果说你在这头由于我每次都是最大的
你在后边你想分配大分区的时候
这事就变的比较困难了
这是我们在这里说到连续存储分配
它的几种做法
这几种做法主要出发点
就是我那个空闲分区的列表
它是按什么来排
然后我们需要去考虑的是
在分配的时候它的查找开销
和在释放的时候它合并的开销
和把这个合并完的结果
放回到空闲分区列表里的时候
找合适位置的开销