3.1_4 动态分区分配算法
动态分区分配算法:在动态分区分配方式中,当很多个空闲分区都能满足需求时,应该选择哪个分区进行分配?
(一)首次适应算法
算法思想
每次都从低地址开始查找,找到第一个能满足大小的空闲分区。
如何实现
空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区。
如图。按照首次适应算法的规则,如果此时有一个进程5(15MB)
,我们会从空闲分区链的链头开始依次查找,找到第一个能够满足大小的分区(分区号1),并分配给该进程。之后,再更新分区大小、分区起始地址等信息。如果之后又来一个进程6(8MB)
,则同理(分区号2)。
(二)最佳适应算法
算法思想
由于动态分区分配是一种连续分配方式,为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间,可以尽可能多地留下大片的空闲区,即,优先使用更小的空闲区。
如何实现
空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区。
如图。按照最佳适应算法的规则,如果此时有一个进程6(9MB)
,我们会从空闲分区链的链头开始依次查找,找到第一个能够满足大小的分区(分区号2),并更新分区大小、分区起始地址等信息。
需要注意的是,“最佳适应算法”要求当前内存中的各个分区必须按照容量递增的次序排列,因此,在进程6(9MB)
分配到分区2后,分区2的剩余空间变为1MB,所以,此时的空闲分区链(或空闲分区表)必须重新排列。
后续进程同理。
缺点
每次都选最小的分区进行分配,会留下越来越多的、很小的、难以利用的内存块。因此这种方法会产生很多的外部碎片。
(三)最坏适应算法
又称最大适应算法(Largest Fit)。
算法思想
为了解决最佳适应算法的问题——即留下太多难以利用的小碎片,可以在每次分配时优先使用最大的连续空闲区,这样分配后剩余的空闲区就不会太小,更方便使用。
如何实现
空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区。
注:由于空闲分区是按容量递减的次序排列的,所以,只需看链头第一个空闲分区能满足要求,若满足要求就放入,否则后面的空闲分区更不可能满足。
如图。按照最坏适应算法的规则,如果此时有一个进程5(3MB)
,我们会从空闲分区链的链头开始依次查找,找到第一个能够满足大小的分区(分区号1),并更新分区大小、分区起始地址等信息。后续又来了进程6(9MB)
,则同理。
需要注意的是,“最坏适应算法”要求当前内存中的各个分区必须按照容量递减的次序排列,因此,在某个进程被分配内存空间后,需要检查此时是否满足容量递减,若不满足,则需重新排列。
缺点
每次都选最大的分区进行分配,虽然可以让分配后留下的空闲区更大、更可用,但是这种方式会导致较大的连续空闲区被迅速用完。如果之后有“大进程”到达,就没有内存分区可用了。
(四)邻近适应算法
算法思想
首次适应算法每次都从链头开始查找。这可能会导致低地址部分出现很多小的空闲分区,而每次分配查找时,都要经过这些分区,因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索,就能解决上述问题。
如何实现
空闲分区以地址递增的顺序排列(可排成一个循环链表)。每次分配内存时从上次查找结束的位置开始查找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区。
注:“邻近适应算法”实际上和“首次适应算法”区别不大。
如图。按照邻近适应算法的规则,如果此时有一个进程5(5MB)
,我们会从空闲分区链的链头开始依次查找,找到第一个能够满足大小的分区(分区号2),并更新分区大小、分区起始地址等信息。
需要注意的是,按照邻近适应算法的规则,我们只需要从上一次查找到的位置接着再往后查找就可以了。因此,若接着有进程6(5MB)
到来,则接着从刚才的分区号2
开始向后查找,找到第一个能够满足大小的分区(分区号3),并更新分区大小、分区起始地址等信息。
可见,邻近适应算法与首次适应算法相比,不需要每次都从链头开始遍历,节省了查找次数。但也仅仅是从这一个角度来比的,综合来看,邻近适应算法并不一定优于首次适应算法。
算法评价
首次适应算法每次都要从头查找,每次都需要检索低地址的小分区。但是这种规则也决定了当低地址部分有更小的分区可以满足需求时,会更有可能用到低地址部分的小分区,也会更有可能把高地址部分的大分区保留下来(这同时也是最佳适应算法的优点)。
邻近适应算法的规则可能会导致无论低地址、高地址部分的空闲分区都有相同的概率被使用,也就导致了高地址部分的大分区更可能被使用,划分为小分区,最后导致无大分区可用(这同时也是最坏适应算法的缺点)。
综合来看,四种算法中,首次适应算法的效果反而更好。