文章目录
- 首次适应算法(First Fit)
- 最佳适应算法(Best Fit)
- 最坏适应算法(Worst Fit)
- 临近适应算法(Nest Fit)
首次适应算法(First Fit)
算法思想:每次都从低地址开始查找,找到第一个能满足大小的空闲分区。
如何实现:空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区。
空闲分区以地址递增的次序排列,1、2、3。
假设要分配为5大小的内存,首先从链头开始查找,第一个满足,分配,修改相应的内存,再分配一个为9大小的内存,从链头开始查找,第二个满足,分配。则:
最佳适应算法(Best Fit)
算法思想:由于动态分区分配是一种连续分配方式,为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间,可以尽可能多地留下大片的空闲区,即,优先使用更小的空闲区。
如何实现:空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区。
空闲分区按容量递增次序链接:
假设要分配7大小的内存,从链头开始查找,第一个满足分配,修改相应内存,再分配8大小的内存,从链头开始查找,第二个满足分配,修改相应内存。则:
最坏适应算法(Worst Fit)
又称 最大适应算法(Largest Fit)
算法思想:为了解决最佳适应算法的问题——即留下太多难以利用的小碎片,可以在每次分配时优先使用最大的连续空闲区,这样分配后剩余的空闲区就不会太小,更方便使用。
如何实现:空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区。
空闲分区按容量递减次序链接:
依次分配10、6大小的内存,都是从链头开始查找,修改相应内存后,则:
临近适应算法(Nest Fit)
算法思想:首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区,而每次分配查找时,都要经过这些分区,因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索,就能解决上述问题。
如何实现:空闲分区以地址递增的顺序排列(可排成一个循环链表)。每次分配内存时从上次查找结束的位置开始查找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区。
假设先要分配一个9大小的内存,从链头开始查找,第二个满足分配,修改相应内存,再分派一个7大小的内存,这时,从第二个开始查找,不是从链头(注意与首次适应算法区别),第三个满足,分配。
则:
【比较】
算法 | 算法思想 | 优点 | 缺点 |
---|---|---|---|
首次适应 | 从头到尾找适合的分区 | 综合看性能最好。算法开销小,回收分区后一般不需要对空闲分区队列重新排序 | |
最佳适应 | 优先使用更小的分区,以保留更多大分区 | 会有更多的大分区被保留下来,更能满足大进程需求 | 会产生很多太小的、难以利用的碎片;算法开销大,回收分区后可需要对空闲分区队列重新排序 |
最坏适应 | 优先使用更大的分区,以防止产生太小的不可用的碎片 | 可以减少难以利用的小碎片 | 大分区容易被用完,不利于大进程;算法开销大(原因同上) |
邻近适应 | 由首次适应演变而来,每次从上次查找结束位置开始查找 | 不用每次都从低地址的小分区开始检索。算法开销小(原因同首次适应算法) | 会使高地址的大分区也被用完 |
最后
以上就是淡然小天鹅最近收集整理的关于【操作系统】动态分区分配算法首次适应算法(First Fit)最佳适应算法(Best Fit)最坏适应算法(Worst Fit)临近适应算法(Nest Fit)的全部内容,更多相关【操作系统】动态分区分配算法首次适应算法(First内容请搜索靠谱客的其他文章。
发表评论 取消回复