当前位置: 首页 > article >正文

内存分配算法实现---首次适应、循环首次适应、最好、最坏分配算法

本次实现均是基于顺序搜索的动态分区分配算法,为实现动态分配,通常将系统中的空闲分区链接成一个链,所谓顺序搜索是指一次搜索空闲分区链上的空闲分区,去寻找一个其大小能满足要求的分区。基于顺序搜索的动态分区分配算法有如下四种:

目录

1.首次适应算法(first Fit,FF)

流程图:

2.循环首次适用算法(next fit ,NF)

流程图:

3.最佳适应算法(best fit ,BF)

流程图:

4.最坏适应算法(worst fit,WF)

流程图:

代码实现:内存分配算法代码实现


1.首次适应算法(first Fit,FF)

 FF算法是以空闲链的首地址递增顺序组织起来,当提出分配需求时,遍历组织好的空白链,找到第一个空间大于等于分配需求的空白分配块分配。若遍历一遍都未找到满足需求的空白块,则分配失败。

优点:该算法倾向于优先利用地址部分的空闲块,从而保留了高地址部分的空闲块,则高地址部分就有可能留有大容量的内存块,为大需求的作业创造了条件

缺点:该算法每次都是从低地址找起,导致其低地址留下了许多无法使用的外部碎片,降低了后续查找效率

流程图:

2.循环首次适用算法(next fit ,NF)

NF算法在FF算法的基础上,针对其查找效率降低的缺点进行改进,不改变空白链的组织方式,只改变你查找方式,每次查找的起始位置是从上次查找位置的下一个位置开始,而不是从头查找,当循环查找一遍之后仍未找到满足需求的空白内存块时分配失败!这样就避免了对外部碎片的查找浪费。

优点:使内存分配在内存中更加均匀,相对于首次适应算法来说查找效率更高。

缺点:由于分配均匀,使得内存中缺乏大的空闲内存块,当后续出现大内存需求的作业时无法满足。

流程图:

3.最佳适应算法(best fit ,BF)

“最佳”指的是大小合适,最接近。空白链以容量大小的顺序组织,每次遍历空白链查找第一个能满足需求的空白块进行分配,这样就一定程度减少了外部碎片的大小。也避免了“大材小用

优点:每次分割剩余的空间总是最小的,减少了外部碎片产生的大小。

缺点:空间利用率来看,NF算法确实是物尽其用,但是每次分割留下的都是难以利用的外部碎片,又降低了查找效率

流程图:

4.最坏适应算法(worst fit,WF)

最坏适应算法和最佳使用算法的空白块选择策略刚好相反,它在扫描整个空表链时,总是挑选一个最大空闲块,从中分割需求的内存块,实际上,这样的算法未必是最坏的

优点:可使剩下的空闲区不至于太小,产生外部碎片的可能性更小,对中小作业有利。查找效率高,只找最大的,若最大不满足,就直接失败。

缺点:可能会导致空白存储链中缺少大容量的空白内存块,当大容量作业进入时无法满足。

流程图:

代码实现:

参数G: 其中由于在分配过程中会产生各种容量极小,无法利用,但其存在又会增加查找效率。于是系统设定一个定值参数G,当某次分配后该内存块剩余的内存容量小于参数G,为避免产生外部碎片降低查找效率,于是将该内存块剩余所有空间全部分配给该进程。

内部碎片:内部碎片是分配给进程,但进程未使用到的空闲内存;但不会再分配给其他进程

外部碎片:内存分配后剩余的空闲内存块,由于容量太小而无法使用,成为外部碎片。

http://www.lryc.cn/news/2416678.html

相关文章:

  • 配色色卡资源整理
  • 堡垒机的作用与选型经验
  • 超全的常用串口调试软件,串口调试助手,串口助手
  • oracle恢复
  • 聚类 监督聚类 k-means聚类
  • 看了这篇之后,别再和我说搞不懂递归!!!
  • Iframe高度自适应
  • 获取(拦截)IE数据包的工具Winsock Expert
  • AdjustTokenPrivileges启用权限
  • ARP欺骗断网攻击与中间人欺骗攻击详解
  • Blocked by CC firewall
  • GeoServer发布高清电子地图
  • BigPipe 应用:新浪微博
  • Java3D安装(idea版)
  • VBA:VBA常用小代码合集
  • 电脑系统提示找不到ddraw.dll文件如何解决?
  • pcAnywhere在局域网内的使用图解
  • 中文网站人气排行
  • 实验四 存储器实验
  • Linux中安装MySQL以及报错解决(错误:GPG 检查失败)
  • Android应用Preference相关及源码浅析(Preference组件家族篇)
  • vb相关网站
  • 珍藏多年的各类资源网站分享给大家
  • 目录切换命令
  • Android开发技术栈总结,技巧经验分享
  • CVE-2019-1388 UAC提权 (nt authority\system)
  • InlineHook和API HOOK从原理开始,一次性掌握劫持技术
  • 软件体系结构设计|描述与架构风格
  • handleMessage的使用
  • Windows的窗口刷新机制