操作系统“最佳适应算法”代码(c++)_中华文本库
第1页/共1页
文本预览：
3、最佳适应算法
#include struct kongkuai { }kongxq[6]={{10,20,1},{50,50,1},{150,100,1},{300,60,1},{400,150,1},{700,200,1}}; int allocate(int jobsize) { int t=0; for(i=0;ijobsize) { kongxq[i].startaddr+= kongxq[i].size-= t=1; return kongxq[i].startaddr- } else if(kongxq[i].flag==1&&kongxq[i].size==jobsize) { kongxq[i].flag=0; t=1; return kongxq[i]. } if(t==0) return 1; } circle() { int i,j;
for(i=0;i<6;i++) for(j=0;jkongxq[j+1].size) { temp.startaddr=kongxq[j]. temp.size=kongxq[j].
temp.flag=kongxq[j]. kongxq[j].startaddr=kongxq[j+1]. kongxq[j].size=kongxq[j+1]. kongxq[j].flag=kongxq[j+1]. kongxq[j+1].startaddr=temp. kongxq[j+1].size=temp. kongxq[j+1].flag=temp. } for(i=0;i<6;i++) for(j=0;j<6;j++) if(kongxq[j].flag==0&&kongxq[j+1].flag==1) { temp.startaddr=kongxq[j]. temp.size=kongxq[j]. temp.flag=kongxq[j]. kongxq[j].startaddr=kongxq[j+1]. kongxq[j].size=kongxq[j+1]. kongxq[j].flag=kongxq[j+1]. kongxq[j+1].startaddr=temp. kongxq[j+1].size=temp. kongxq[j+1].flag=temp. } return 1; } callback() { int s,len,t1=0,t2=0,t3=0,i,j; printf("请输入回收区的起始地址:\u005cn"); scanf("%d"&s); printf("请输入回收区的大小:\u005cn"); scanf("%d"&len); for(i=0;i<6;i++) { if((kongxq[i].startaddr==s+len)&&(kongxq[i].flag==1)) { len+=kongxq[i]. t1=1; for(j=0;j<6;j++) if((kongxq[j].startaddr+kongxq[j].size==s)&&(kongxq[j].flag==1)) { kongxq[i].flag=0; //kongxq[j].startaddr= kongxq[j].size=kongxq[j].size+
t2=1; } if(t2==0) { kongxq[i].startaddr=s; kongxq[i].size= } } } if(t1==0) { for(i=0;i<6;i++) { if((kongxq[i].startaddr+kongxq[i].size==s)&&(kongxq[i].flag==1)) { kongxq[i].size+= t3=1; } if(t3==0) for(j=0;j<6;j++) if(kongxq[j].flag==0) { kongxq[j].startaddr=s; kongxq[j].size= kongxq[j].flag=1; } } } return 1; } void print() { printf("\u005cn for(i=0;i<6;i++) { 起始地址 | 大小 | 标记 \u005cn\u005cn");
printf(" } printf("\u005cn"); } void main() { int jobsize,
kongxq[i].startaddr,kongxq[i].size,kongxq[i].flag);
printf("\u005cn 是否有作业请求空闲区？y or n:"); while((end=getchar())=='y') { printf("初始空闲区状态：\u005cn"); circle(); print(); printf("请输入请求空闲区的作业大小："); scanf("%d"&jobsize); start=allocate(jobsize); circle(); printf("分配后空闲区状态：\u005cn"); print(); if(!start) printf("没有适合的空闲区大小！\u005cn"); else printf("作业起始地址：%d\u005cn"start); printf("作业大小：%d\u005cn"jobsize); callback(); circle(); print(); printf("是否有其他的作业请求？ y or n:"); end=getchar(); } }
第1页/共1页
寻找更多 ""首次适应算法和最佳适应算法是动态存储分配解决方案研究的内容，所以本文对这两种..
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
转载 适应算法和最佳适应算法
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口1062人阅读
在内存管理中存在这两类算法：一类是内存分配算法，一类是页面置换算法
内存分配算法：是指怎么从连续的逻辑地址空间上分配内存地址给进程。
常见内存分配算法及优缺点如下：　　（1）首次适应算法。使用该算法进行内存分配时，从空闲分区链首开始查找，直至找到一个能满足其大小要求的空闲分区为止。然后再按照作业的大小，从该分区中划出一块内存分配给请求者，余下的空闲分区仍留在空闲分区链中。　 　该算法倾向于使用内存中低地址部分的空闲分区，在高地址部分的空闲分区很少被利用，从而保留了高地址部分的大空闲区。显然为以后到达的大作业分配大的内 存空间创造了条件。缺点在于低址部分不断被划分，留下许多难以利用、很小的空闲区，而每次查找又都从低址部分开始，这无疑会增加查找的开销。　　 （2）循环首次适应算法。该算法是由首次适应算法演变而成的。在为进程分配内存空间时，不再每次从链首开始查找，而是从上次找到的空闲分区开始查找，直至 找到一个能满足要求的空闲分区，并从中划出一块来分给作业。该算法能使空闲中的内存分区分布得更加均匀，但将会缺乏大的空闲分区。　　（3）最佳适应算法。该算法总是把既能满足要求，又是最小的空闲分区分配给作业。　 　为了加速查找，该算法要求将所有的空闲区按其大小排序后，以递增顺序形成一个空白链。这样每次找到的第一个满足要求的空闲区，必然是最优的。孤立地看， 该算法似乎是最优的，但事实上并不一定。因为每次分配后剩余的空间一定是最小的，在存储器中将留下许多难以利用的小空闲区。同时每次分配后必须重新排序， 这也带来了一定的开销。　　（4）最差适应算法。最差适应算法中，该算法按大小递减的顺序形成空闲区链，分配时直接从空闲区链的第一个空闲分区中 分配（不能满足需要则不分配）。很显然，如果第一个空闲分区不能满足，那么再没有空闲分区能满足需要。这种分配方法初看起来不太合理，但它也有很强的直观 吸引力：在大空闲区中放入程序后，剩下的空闲区常常也很大，于是还能装下一个较大的新程序。　　最坏适应算法与最佳适应算法的排序正好相反，它的队列指针总是指向最大的空闲区，在进行分配时，总是从最大的空闲区开始查寻。　　该算法克服了最佳适应算法留下的许多小的碎片的不足，但保留大的空闲区的可能性减小了，而且空闲区回收也和最佳适应算法一样复杂。
页面置换算法：是指线性地址转化为物理地址的过程中的算法，由于实际物理内存有限，一个进程的所有逻辑页page并不是都会被映射到实际的物理frame上，而是分配一定数量的物理frame，之后通过一定的页面置换算法把需要调入内存的逻辑页page调入内存。
评价一个算法的优劣,可通过在一个特定的存储访问序列（页面走向）上运行它，并计算缺页数量来实现。
1 先入先出法（FIFO）
最简单的页面置换算法是先入先出（FIFO）法。这种算法的实质是，总是选择在主存中停留时间最长（即最老）的一页置换，即先进入内存的页，先退出内存。理由是：最早调入内存的页，其不再被使用的可能性比刚调入内存的可能性大。建立一个FIFO队列，收容所有在内存中的页。被置换页面总是在队列头上进行。当一个页面被放入内存时，就把它插在队尾上。这种算法只是在按线性顺序访问地址空间时才是理想的，否则效率不高。因为那些常被访问的页，往往在主存中也停留得最久，结果它们因变&老&而不得不被置换出去。FIFO的另一个缺点是，它有一种异常现象，即在增加存储块的情况下，反而使缺页中断率增加了。当然，导致这种异常现象的页面走向实际上是很少见的。
2 最优置换算法（OPT）
最优置换（Optimal Replacement）是在理论上提出的一种算法。其实质是：当调入新的一页而必须预先置换某个老页时，所选择的老页应是将来不再被使用，或者是在最远的将来才被访问。采用这种页面置换算法，保证有最少的缺页率。但是最优页面置换算法的实现是困难的，因为它需要人们预先就知道一个进程整个运行过程中页面走向的全部情况。不过，这个算法可用来衡量（如通过模拟实验分析或理论分析）其他算法的优劣。
3 最久未使用算法（LRU）
FIFO算法和OPT算法之间的主要差别是，FIFO算法利用页面进入内存后的时间长短作为置换依据，而OPT算法的依据是将来使用页面的时间。如果以最近的过去作为不久将来的近似，那么就可以把过去最长一段时间里不曾被使用的页面置换掉。它的实质是，当需要置换一页时，选择在最近一段时间里最久没有使用过的页面予以置换。这种算法就称为最久未使用算法（Least Recently Used，LRU）。LRU算法是与每个页面最后使用的时间有关的。当必须置换一个页面时，LRU算法选择过去一段时间里最久未被使用的页面。LRU算法是经常采用的页面置换算法，并被认为是相当好的，但是存在如何实现它的问题。LRU算法需要实际硬件的支持。其问题是怎么确定最后使用时间的顺序，对此有两种可行的办法：（1）计数器。最简单的情况是使每个页表项对应一个使用时间字段，并给CPU增加一个逻辑时钟或计数器。每次存储访问，该时钟都加1。每当访问一个页面时，时钟寄存器的内容就被复制到相应页表项的使用时间字段中。这样我们就可以始终保留着每个页面最后访问的&时间&。在置换页面时，选择该时间值最小的页面。这样做，不仅要查页表，而且当页表改变时（因CPU调度）要维护这个页表中的时间，还要考虑到时钟值溢出的问题。（2）栈。用一个栈保留页号。每当访问一个页面时，就把它从栈中取出放在栈顶上。这样一来，栈顶总是放有目前使用最多的页，而栈底放着目前最少使用的页。由于要从栈的中间移走一项，所以要用具有头尾指针的双向链连起来。在最坏的情况下，移走一页并把它放在栈顶上需要改动6个指针。每次修改都要有开销，但需要置换哪个页面却可直接得到，用不着查找，因为尾指针指向栈底，其中有被置换页。因实现LRU算法必须有大量硬件支持，还需要一定的软件开销。所以实际实现的都是一种简单有效的LRU近似算法。一种LRU近似算法是最近未使用算法（Not Recently Used，NUR）。它在存储分块表的每一表项中增加一个引用位，操作系统定期地将它们置为0。当某一页被访问时，由硬件将该位置1。过一段时间后，通过检查这些位可以确定哪些页使用过，哪些页自上次置0后还未使用过。就可把该位是0的页淘汰出去，因为在最近一段时间里它未被访问过。
4 第二次机会算法（SCR）
第二次机会算法的基本思想是与FIFO相同的，但是有所改进，避免把经常使用的页面置换出去。当选择置换页面时，检查它的访问位。如果是0，就淘汰这页；如果访问位是1，就给它第二次机会，并选择下一个FIFO页面。当一个页面得到第二次机会时，它的访问位就清为0，它的到达时间就置为当前时间。如果该页在此期间被访问过，则访问位置1。这样给了第二次机会的页面将不被淘汰，直至所有其他页面被淘汰过（或者也给了第二次机会）。因此，如果一个页面经常使用，它的访问位总保持为1，它就从来不会被淘汰出去。第二次机会算法可视为一个环形队列。用一个指针指示哪一页是下面要淘汰的。当需要一个存储块时，指针就前进，直至找到访问位是0的页。随着指针的前进，把访问位就清为0。在最坏的情况下，所有的访问位都是1，指针要通过整个队列一周，每个页都给第二次机会。这时就退化成FIFO算法了。
页面置换算法还有很多变种，如考虑到被置换页是否修改过、按FIFO算法选中的页正在使用等情况，都需要硬件、软件协同实现。
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：225956次
积分：3343
积分：3343
排名：第4176名
原创：67篇
转载：254篇
评论：37条
(1)(2)(1)(3)(3)(3)(3)(6)(6)(5)(3)(3)(4)(8)(3)(1)(1)(3)(10)(11)(3)(7)(12)(4)(8)(5)(8)(12)(2)(4)(8)(17)(4)(1)(5)(3)(1)(6)(14)(12)(13)(5)(5)(8)(28)(34)(13)最佳适应算法
采用最佳适应算法，按从小到大的次序组成空闲区自由链，当用户作业或进程申请一个空闲区时，存储管理程序从表头开始查找，当找到第一个満足要求的空闲区时，停止查找。如果该空闲区大于请求表中的请求长度，将减去请求长度后的剩余空闲区部分留在可用表中。回收时，从作链中删去要回收的作业块，同时在空闲链中插入该作业大小的空闲区，并按顺序排列
09-05-14 &匿名提问 发布
提出一种基于自回归模型的自适应阈值检测算法用于监测液体火箭发动机地面试验的稳态过程，该算法由两个阶段组成。第一阶段的检测算法阈值由不同试车台次的稳态参数测量值的自回归模型的估计值、标准偏差和带宽系数计算，第二阶段的检测算法阈值由稳态过程的参数均值的自回归模型的估计值、标准偏差和带宽系数计算。用某大型液体火箭发动机的地面试验数据进行验证，结果表明该算法能有效可靠地监测发动机的运行状态。
请登录后再发表评论!
源代码请看
请登录后再发表评论!拆半记忆法对最佳适应算法的优化--《宜宾学院学报》2014年06期
拆半记忆法对最佳适应算法的优化
【摘要】：最佳适应算法(BF)是内存空闲块分配的一种常用算法,现行BF算法的空闲块查询方法不当从而导致工作效率低下.使用拆半法替代原有的BF算法在空闲块查询时所采用的线性顺序比较法,同时增加分配记忆功能,对BF算法进行优化并加强算法功能,从而直接改善内存的分配效率,对提高系统吞吐量起到积极的促进作用.
【作者单位】：
【关键词】：
【分类号】：TP301.6【正文快照】：
当前的多任务系统操作系统,进程的数量多,内存的使用频率高、各进程在内存中驻留时间长短不一,从而释放内存的时间先后不同,导致内存空闲块(以下简称空闲块)在内存中呈现出间隔不连续的状态因此,空闲块的分配算法旨在对进程的内存请求进行分配,使得进程能获得空闲块而运行,且
欢迎：、、)
支持CAJ、PDF文件格式，仅支持PDF格式
【相似文献】
中国期刊全文数据库
郑天宇;李力争;;[J];微计算机信息;2010年30期
王志辉;;[J];内蒙古科技与经济;2010年22期
肖济楷;[J];武汉科技大学学报(自然科学版);1995年02期
王海洋,蔡康颖,王文成,吴恩华;[J];计算机辅助设计与图形学学报;2005年08期
陈平;曾兴斌;何加铭;贾德祥;;[J];杭州电子科技大学学报;2010年05期
姜惠娟;;[J];甘肃高师学报;2011年02期
朱明;;[J];金融电子化;2001年03期
程有娥;;[J];太原城市职业技术学院学报;2005年05期
俞莉莹;赵雷;吕强;;[J];现代计算机;2006年04期
邹俊;吴京慧;;[J];现代计算机;2006年09期
中国重要会议论文全文数据库
陈平;曾兴斌;何加铭;贾德祥;;[A];浙江省电子学会2010学术年会论文集[C];2010年
郑捷;;[A];上海烟草系统2006年度优秀学术论文集[C];2006年
姚玉坤;乔彬;;[A];2009中国仪器仪表与测控技术大会论文集[C];2009年
王东滨;智慧;余翔湛;胡铭曾;;[A];全国网络与信息安全技术研讨会论文集（上册）[C];2007年
关强;王屹;单茂琪;;[A];第五次全国计算机安全技术交流会论文集[C];1990年
郑捷;;[A];中国烟草学会2006年学术年会论文集[C];2007年
王景彬;阎兆立;马龙华;程晓斌;陈孝良;;[A];运输噪声的预测与控制——2009全国环境声学学术会议论文集[C];2009年
韦鹏生;;[A];第四届全国结构工程学术会议论文集（下）[C];1995年
李周华;严毅;;[A];广西计算机学会2004年学术年会论文集[C];2004年
王海飞;蒋平;朱劲;董和刚;;[A];全国第二届嵌入式技术联合学术会议论文集[C];2007年
中国重要报纸全文数据库
阮煜君;[N];中国税务报;2007年
郝晓波;[N];中国计算机报;2003年
姚新;[N];计算机世界;2001年
项建新;[N];中华工商时报;2004年
李文;[N];中国计算机报;2004年
洪月宝;[N];中国电脑教育报;2003年
安徽 刘勇;[N];中国电脑教育报;2005年
;[N];网络世界;2008年
季振宇;[N];电脑报;2001年
高博;[N];电脑报;2004年
中国博士学位论文全文数据库
高超;[D];中国科学技术大学;2010年
李仁见;[D];国防科学技术大学;2011年
汤健彬;[D];浙江大学;2001年
徐光侠;[D];重庆大学;2011年
中国硕士学位论文全文数据库
陈涛;[D];华中师范大学;2012年
王海洋;[D];中国科学院研究生院（软件研究所）;2005年
陈平;[D];宁波大学;2011年
韩冬莹;[D];东北师范大学;2007年
高峰;[D];沈阳工业大学;2007年
于晓飞;[D];辽宁科技大学;2009年
杨梦梦;[D];国防科学技术大学;2004年
张巍;[D];天津大学;2004年
罗海林;[D];上海师范大学;2007年
陈金龙;[D];浙江大学;2008年
&快捷付款方式
&订购知网充值卡
400-819-9993
《中国学术期刊（光盘版）》电子杂志社有限公司
同方知网数字出版技术股份有限公司
地址：北京清华大学 84-48信箱 知识超市公司
出版物经营许可证 新出发京批字第直0595号
订购热线：400-819-82499
服务热线：010--
在线咨询：
传真：010-
京公网安备74号}