动态分区分配计算

简介: 动态分区分配计算

动态分区分配


内存连续分配管理分为:


单一连续分配

固定分区分配

动态分区分配(本篇所讲)


首次适应算法(First Fit,FF)


该算法又称最先适应算法,要求空闲分区按照首地址递增的顺序排列。


优点:优先使用低地址部分空闲分区,保留了高地址部分的大量空闲分区,有利于大程序或作业的装入。

缺点:内存的低地址区留下了许多难以利用的很小空闲分区,即内存“碎片”;算法每次都从低地址部分开始查找,这增加了查找可用空闲分区的开销。


注:外碎片是指由于空闲空间太小,以致于无法分配给程序或作业的内存空闲区域,如动态分区分配中存在外碎片; 内碎片是指已经被分配出去,却不能被充分利用的内存空间区域,如固定分区分配中存在内碎片。


循环首次适应算法(Next Fit,NF)


空闲分区按照首地址递增的顺序排列。每次内存分配时,不再从表头(或链首)开始查找,而是从上次分配的空闲分区的下一个空闲分区开始顺序查找。


优点:内存的空闲分区分布较均匀,减少查找空闲分区的开销。

缺点:经多次分配后,内存缺少较大的空闲分区,以分配给较大的程序或作业。


最佳适应算法(Best Fit,BF)


或称最优适应算法,该算法要求将空闲分区按从小到大的顺序排列。


优点:较大的空闲分区被尽量的保留下来,有利于大程序或作业的分配。

缺点:容易产生内存碎片;每次分配后需要更新空闲分区表(链),增加了系统开销;分割后小的空闲分区处于分区表(链)首,增加了查找空闲分区的时间。


最坏适应算法(Worst Fit,WF)


又称最差适应算法,该算法空闲分区按从大到小的顺序排列的。


优点:不会产生过多的碎片,有利于中、小程序或作业,且查找效率高。

缺点:影响大程序或作业的分配。此外,每次分配后需要更新空闲分区表(链),增加了系统开销。


四种算法比较


从搜索速度上看,FF具有最佳性能。


首次适应算法具有最佳性能;空间利用方面,首次适应算法比最佳适应算法好,最坏适应算法最差。


最佳适应算法找到的空闲分区是最佳的,但内存利用率不一定最优;


首次适应算法尽可能利用低地址空间,保证了高地址有较大空闲分区,以分配给较大的程序或作业;


最坏适应算法总是分割大的空闲分区,这有利于中、小程序或作业,但不利于较大的程序或作业。在实际系统中,首次适应算法使用较广泛。


例题

1.在可变分区存储管理下,按地址排列的内存空闲区为:10KB、4KB、20KB、18KB、7KB、9KB、12KB 和 15KB。对于下列连续存储区的请求:12KB、10KB、15KB、18KB,试问:使用首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法,哪个空闲区将被使用?


2cdcae423cac916c942a0701bc58098f_image-1653458857923.png


首次适应算法:


5348062871d1cb4060397171307c48ea_image-1653458917723.png


循环首次适应算法:


f3e60bcaad6004c303e819d91d24ddab_image-1653458959921.png


最佳适应算法:


fe64bfe9670fbfd7cbcac2797494f116_image-1653458991017.png


9ff8623867f9fb0311b2afcccc6d2155_image-1653459007038.png


最坏适应算法:


82d3a0c9361e5b7bb03b52d47baae9dd_image-1653459029171.png


2.某操作系统采用可变分区分配存储管理方法,用户区为512K且始址为0。若分配采用分配空闲区低地址部分的方案,对下述申请序列:

申请310K,申请100K,释放310K,申请150K,申请40K,申请30K。

分别采用首次适应算法、最佳适应算法,回答下列问题:

(1)给出每一步的已分配空间、空闲分区(给出始址,大小)?

(2)若再申请120K,还能分配这120K存储空间吗?


58262accc34b9926ba7dab7ff05f473d_image-20230226163614372.png


1605425133469a29434f3ea531363161_image-20230221143940256.png


 

相关文章
|
网络协议 Python
在Python中进行UDP(User Datagram Protocol)网络编程
在Python中进行UDP(User Datagram Protocol)网络编程
350 3
|
8月前
|
运维 数据挖掘 Windows
服务器数据恢复—服务器硬盘指示灯亮黄灯的数据恢复案例
服务器硬盘指示灯闪烁黄灯是一种警示,意味着服务器硬盘出现故障即将下线。发现这种情况建议及时更换硬盘。 一旦服务器上有大量数据频繁读写,硬盘指示灯会快速闪烁。服务器上某个硬盘的指示灯只有黄灯亮着,而其他颜色的灯没有亮的话,通常表示这块硬盘出现故障,这时候更换新硬盘同步数据即可。 如果没有及时发现硬盘损坏或者更换硬盘失败导致服务器崩溃,应该如何恢复数据呢?下面通过一个真实案例讲解一下服务器硬盘指示灯亮黄色的数据恢复案例。
|
7月前
|
Swift
DeepSeek开源Janus-Pro多模态理解生成模型,魔搭社区推理、微调最佳实践
Janus-Pro是DeepSeek最新开源的多模态模型,是一种新颖的自回归框架,统一了多模态理解和生成。
786 19
DeepSeek开源Janus-Pro多模态理解生成模型,魔搭社区推理、微调最佳实践
|
存储 算法 Java
某操纵系统采用可变分区分配存储管理方法,用户区为512K且始址为0,用空闲分区表管理空闲分区。若分配是采用分配空闲区低地址部分的方案,且初始时用户区的512K空间空闲,对下述申请序列:申请300K,申
某操纵系统采用可变分区分配存储管理方法,用户区为512K且始址为0,用空闲分区表管理空闲分区。若分配是采用分配空闲区低地址部分的方案,且初始时用户区的512K空间空闲,对下述申请序列:申请300K,申
285 0
数据库系统工程师考点笔记
数据库系统工程师考点笔记
1304 0
|
机器学习/深度学习 Python
线性回归 最小二乘法的求解推导与基于Python的底层代码实现
作为最常见的方法之一,线性回归仍可视为有监督机器学习的方法之一,同时也是一种广泛应用统计学和数据分析的基本技术。它是一种用于估计两个或多个变量之间线性关系的方法,其中一个变量是自变量,另一个变量是因变量。线性回归假设这两个变量之间存在线性关系,并试图找到一条最佳拟合直线,使预测值与实际值之间的误差最小化。
|
存储 缓存 JSON
详解HTTP四种请求:POST、GET、DELETE、PUT
【4月更文挑战第3天】
66309 3
详解HTTP四种请求:POST、GET、DELETE、PUT
|
JavaScript Java 测试技术
基于SpringBoot+Vue的医院门诊信息管理系统的详细设计和实现
基于SpringBoot+Vue的医院门诊信息管理系统的详细设计和实现
183 0
|
算法
存储器管理-动态分区分配算法
存储器管理-动态分区分配算法
441 0