• 动态分区分配算法之首次适应算法,最佳适应算法,最坏适应算法以及邻近适应算法


    1.首次适应算法(First Fit)

    1.算法思想:

    每次都从低地址开始查找,找到第一个能满足大小的空闲分区。

    2.如何实现:

    空闲分区以地址递增的次序排列。
    每次分配内存时顺序查找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区。

    空闲分区表
    在这里插入图片描述
    空闲分区链:
    在这里插入图片描述

    2.最佳适应算法(Best Fit)

    1.算法思想:

    由于动态分区分配是一种连续分配方式,为各进程分配的空间必须是连续的一整片区域。
    因此为了保证当“大进程”到来时能有连续的大片空间,可以尽可能多地留下大片的空闲区,
    即,优先使用更小的空闲区。

    2.如何实现:

    空闲分区按容量递增次序链接。
    每次分配内存时顺序查找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区。
    在这里插入图片描述

    3.缺点:

    每次都选最小的分区进行分配,会留下越来越多的、很小的、难以利用的内存块。
    因此这种方法会产生很多的外部碎片。

    3.最坏适应算法(Worst Fit)

    又称最大适应算法(Largest Fit)

    1.算法思想:

    为了解决最佳适应算法的问题:即留下太多难以利用的小碎片,
    可以在每次分配时优先使用最大的连续空闲区,这样分配后剩余的空闲区就不会太小,更方便使用。

    2.如何实现:

    空闲分区按容量递减次序链接。
    每次分配内存时顺序查找空闲分区链(或空闲分区 ),找到大小能满足要求的第一个空闲分区。
    在这里插入图片描述

    3.缺点:

    每次都选最大的分区进行分配,虽然可以让分配后留下的空闲区更大,更可用,但是这种方式会导致较大的连续空闲区被迅速用完。
    如果之后有“大进程”到达,就没有内存分区可用了。

    4.邻近适应算法(Next Fit)

    1.算法思想:

    首次适应算法每次都从链头开始查找的。
    这可能会导致低地址部分出现很多小的空闲分区,而每次分配查找时,都要经过这些分区,因此也增加了查找的开销。
    如果每次都从上次找结束的位置开始检索,就能解决上述问题。

    2.如何实现:

    空闲分区以地址递增的顺序排列(可排成一个循环链表)。
    每次分配内存时从上次查找结束的位置开始查找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区。
    在这里插入图片描述

    1. 首次适应算法每次都要从头查找,每次都需要检索低地址的小分区。但是这种规则也决定了当低地址部分有更小的分区可以满足需求时,会更有可能用到低地址部分的小分区,也会更有可能把高地址部分的大分区保留下来(最佳适应算法的优点)
    2. 邻近适应算法的规则可能会导致无论低地址、高地址部分的空闲分区都有相同的概率被使用,也就导致了高地址部分的大分区更可能被使用,划分为小分区,最后导致无大分区可用(最大适应算法的缺点)

    综合来看,四种算法中,首次适应算法的效果反而更好.

    在这里插入图片描述

  • 相关阅读:
    【刷题之路 | Java & Python】两数之和(暴力枚举&哈希表)
    数据结构排序算法---八大排序复杂度及代码实现
    unity sdk -AppLovin MAX 广告聚合平台接入+Firebase统计
    CSDN每日一练 |『买苹果』『最长回文串』『查找整数』2023-10-20
    python 面试算法题
    uos桌面专业版下载多架构软件安装包
    读取 resources 目录下的文件路径的九种方式,你知道多少?
    VM 虚拟服务器 文件上传,VMWare虚拟机怎么和主机之间互传文件?
    在C# WinForms应用程序中安装,配置和使用MetroFramework
    java安装教程
  • 原文地址:https://blog.csdn.net/qq_61888137/article/details/133819327