首页 > 编程语言 >3.1_4 动态分区分配算法

3.1_4 动态分区分配算法

时间:2024-03-13 11:34:15浏览次数:19  
标签:分区 地址 适应 算法 查找 3.1 空闲

3.1_4 动态分区分配算法

image-20240312203525357

  动态分区分配算法:在动态分区分配方式中,当很多个空闲分区都能满足需求时,应该选择哪个分区进行分配?

(一)首次适应算法

算法思想

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

如何实现

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

image-20240313084126736

  如图。按照首次适应算法的规则,如果此时有一个进程5(15MB),我们会从空闲分区链的链头开始依次查找,找到第一个能够满足大小的分区(分区号1),并分配给该进程。之后,再更新分区大小、分区起始地址等信息。如果之后又来一个进程6(8MB),则同理(分区号2)。

(二)最佳适应算法

算法思想

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

如何实现

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

image-20240313084913116

  如图。按照最佳适应算法的规则,如果此时有一个进程6(9MB),我们会从空闲分区链的链头开始依次查找,找到第一个能够满足大小的分区(分区号2),并更新分区大小、分区起始地址等信息。

  需要注意的是,“最佳适应算法”要求当前内存中的各个分区必须按照容量递增的次序排列,因此,在进程6(9MB)分配到分区2后,分区2的剩余空间变为1MB,所以,此时的空闲分区链(或空闲分区表)必须重新排列。

  后续进程同理。

image-20240313085251660

缺点

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

(三)最坏适应算法

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

算法思想

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

如何实现

  空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区。

  注:由于空闲分区是按容量递减的次序排列的,所以,只需看链头第一个空闲分区能满足要求,若满足要求就放入,否则后面的空闲分区更不可能满足。

image-20240313090427131

  如图。按照最坏适应算法的规则,如果此时有一个进程5(3MB),我们会从空闲分区链的链头开始依次查找,找到第一个能够满足大小的分区(分区号1),并更新分区大小、分区起始地址等信息。后续又来了进程6(9MB),则同理。

  需要注意的是,“最坏适应算法”要求当前内存中的各个分区必须按照容量递减的次序排列,因此,在某个进程被分配内存空间后,需要检查此时是否满足容量递减,若不满足,则需重新排列。

image-20240313090658960

缺点

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

(四)邻近适应算法

算法思想

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

如何实现

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

  注:“邻近适应算法”实际上和“首次适应算法”区别不大。

image-20240313091548422

  如图。按照邻近适应算法的规则,如果此时有一个进程5(5MB),我们会从空闲分区链的链头开始依次查找,找到第一个能够满足大小的分区(分区号2),并更新分区大小、分区起始地址等信息。

  需要注意的是,按照邻近适应算法的规则,我们只需要从上一次查找到的位置接着再往后查找就可以了。因此,若接着有进程6(5MB)到来,则接着从刚才的分区号2开始向后查找,找到第一个能够满足大小的分区(分区号3),并更新分区大小、分区起始地址等信息。

  可见,邻近适应算法与首次适应算法相比,不需要每次都从链头开始遍历,节省了查找次数。但也仅仅是从这一个角度来比的,综合来看,邻近适应算法并不一定优于首次适应算法。

算法评价

  首次适应算法每次都要从头查找,每次都需要检索低地址的小分区。但是这种规则也决定了当低地址部分有更小的分区可以满足需求时,会更有可能用到低地址部分的小分区,也会更有可能把高地址部分的大分区保留下来(这同时也是最佳适应算法的优点)。

  邻近适应算法的规则可能会导致无论低地址、高地址部分的空闲分区都有相同的概率被使用,也就导致了高地址部分的大分区更可能被使用,划分为小分区,最后导致无大分区可用(这同时也是最坏适应算法的缺点)。

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

总结

image-20240313092526050

标签:分区,地址,适应,算法,查找,3.1,空闲
From: https://blog.csdn.net/weixin_44421143/article/details/136670270

相关文章

  • 3.1_5 基本分页存储管理的概念
    文章目录3.1_5基本分页存储管理的概念(一)什么是分页存储(二)重要的数据结构——页表(三)逻辑地址结构总结3.1_5基本分页存储管理的概念  连续分配:为用户进程分配的必须是一个连续的内存空间。  非连续分配:为用户进程分配的可以是一些分散的内存空间。(一)什么是分......
  • 某数4代——某房地产为例扣算法
      提示:本文章仅供学习交流,严禁用于非法用途,如有不当可联系本人删除!文章于2024-3-13发布  网站:aHR0cDovL3d3dy5mYW5nZGkuY29tLmNuL25ld19ob3VzZS9uZXdfaG91c2UuaHRtbA==  过rs4的方法大致有两种,一种是补环境,另一种就是扣算法,我们这里以扣算法的方式来过rs4。一、rs4的响应......
  • 《算法竞赛入门经典 第2版》 数学题目集
    例题10-1巨大的斐波那契数!(ColossalFibonacciNumbers!,UVa11582)巨大的斐波那契数!ColossalFibonacciNumbers!-洛谷例题10-2不爽的裁判(DisgruntledJudge,NWERC2008,UVa12169)不爽的裁判DisgruntledJudge-洛谷NOI数学学习相关书籍及视频等资料(不包......
  • 经典算法掌握
    排序算法是对一组数据按照特定规则进行排序的算法。常见的排序算法有冒泡排序、插入排序、选择排序、快速排序和归并排序等。冒泡排序(BubbleSort):冒泡排序是通过不断比较相邻的两个元素并交换位置,让较大(或较小)的元素逐渐往后(或往前)移动,直到所有元素都排好序。冒泡排序的时间......
  • 【算法训练营】最长公共子序列,倒水问题,奶牛吃草(Python实现)
    最长公共子序列时间限制:1sec空间限制:256MB问题描述给定两个1到n的排列A,B(即长度为n的序列,其中[1,n]之间的所有数都出现了恰好一次)。求它们的最长公共子序列长度。输入格式第一行一个整数n,意义见题目描述。第二行n个用空格隔开的正整数A[1],…,......
  • 【算法训练营】邓老师书,子序列,前缀(python实现)
    邓老师数时间限制:1sec空间限制:256MB问题描述众所周知,大于1的自然数中,除了1与其本身外不再有其他因数的数称作质数(素数)。对于大于1的不是质数的自然数,我们又称作合数。参加了邓老师算法训练营的小Z突发奇想,定义了新的数:所有合数中,除了1与其本身外,其他因......
  • 2024基于协同过滤算法springboot微信订餐小程序项目
    项目介绍基于springboot开发的订餐小程序,用户在微信小程序里面进行注册登录,点餐,收藏,评论等,管理员在后台网页端进行对菜品,分类,订单,用户,角色,评论等进行管理,小程序界面通过协同过滤算法给用户推荐菜品技术栈后端:springboot+JPA+Mysql8+redis+maven+idea前端:后台:HTML+JS+CSS......
  • C#判断素数的方法:试除法 vs 优化的试除法 vs 米勒-拉宾素数检测算法
    目录1.素数也就质数2.试除法3.优化的试除法_14.优化的试除法_25.优化的试除法_36.米勒-拉宾素数检测算法1.素数也叫质数        一个质数是一个大于1的自然数,只有两个正因数:1和它自身。这意味着如果一个数只有两个正因数,那么它就是一个质数。例如,2、3、5、7......
  • 查重算法
    论文查重这个作业属于哪个课程软件工程2024这个作业要求在哪里论文查重这个作业的目标学习如何作为软件工程师开发项目仓库地址:Nacyoooooo......
  • 关于树莓派5(Ubnutu 23.10和树莓派5自带的系统通用)下载时出现error: externally-manage
    一.报错产生的原因  最近作者更新了这两个系统,在作者想去安装非 Debian的库的时候总是出现以下的报错:error:externally-managed-environment这是因为树莓派5升级了服务器系统,从Debian11到了Debian12,这个服务器系统对于外接库的限制还是比较严格的。作者也按照系......