目前常用的分区分配算法有以下几种:
首次适应算法
循环首次适应算法
最佳适应算法
最坏适应算法
首次适应算法
首次适应算法又称最先适应算法,该算法要求空闲分区按地址递增的次序排列。
在进行内存分配时,从空闲分区表(或空闲分区链)首开始顺序查找,直到找到第一个能满足其大小要求的空闲分区为止。
然后,再按照作业大小,从该分区中划出一块内存空间分配给请求者,余下的空闲分区仍然留在空闲分区表(或空闲分区链)中。
首次适应算法的特点
特点:优先利用内存低地址端,高地址端有大空闲区,但低地址端有许多小空闲分区时会增加查找开销。
循环首次适应算法
循环首次适应算法又称下次适应算法,它是首次适应算法的变形。
该算法在为进程分配内存空间时,从上次找到的空闲分区的下一个空闲分区开始查找,直到找到第一个能满足其大小要求的空闲分区为止。
然后,再按照作业大小,从该分区中划出一块内存空间分配给请求者,余下的空闲分区仍然留在空闲分区表(或空闲分区链)中。
循环首次适应算法的特点
特点:使存储空间的利用更加均衡,但会使系统缺乏大的空闲分区。
最佳适应算法
最佳适应算法要求空闲分区按容量大小递增的次序排列。
在进行内存分配时,从空闲分区表(或空闲分区链)首开始顺序查找,直到找到第一个能满足其大小要求的空闲分区为止。
如果该空闲分区大于作业的大小,则从该分区中划出一块内存空间分配给请求者,将剩余空闲区仍然留在空闲分区表(或空闲分区链)中。
最佳适应算法的特点
按最佳适应算法为作业分配内存,就能把既满足作业要求又与作业大小最接近的空闲分区分配给作业。
特点:保留了大的空闲区。但分割后的剩余空闲区很小。
最坏适应算法
最坏适应算法要求空闲分区按容量大小递减的次序排列。
在进行内存分配时,先检查空闲分区表(或空闲分区链)中的第一个空闲分区,若第一个空闲分区小于作业要求的大小,则分配失败;
否则从该空闲分区中划出与作业大小相等的一块内存空间分配给请求者,余下的空闲分区仍然留在空闲分区表(或空闲分区链)中。
最坏适应算法的特点
特点:剩下的空闲区比较小,但当大作业到来时,其存储空间的申请往往得不到满足。
如何衡量分配算法的好坏
对于某一个作业序列来说,若某种分配算法能将该作业序列中所有作业安置完毕,则称该分配算法对这一作业序列合适,否则称为不合适。
例
下表给出了某系统的空闲分区表,系统采用可变式分区存储管理策略。现有以下作业序列:96K、20K、200K。若用首次适应算法和最佳适应算法来处理这些作业序列,试问哪一种算法可以满足该作业序列的请求?
例--采用最佳适应算法分配1
申请96K,
选中5号分区,5号分区大小与申请空间大小一致,应从空闲分区表中删去该表项;
例--采用最佳适应算法分配2
申请20K,
选中1号分区,分配后1号分区还剩下12K;
例--采用最佳适应算法分配3
申请200K,
选中4号分区,分配后剩下18K。
例--采用首次适应算法分配1
申请96K,
选中4号分区,进行分配后4号分区还剩下122K;