操作系统常用页面置换算法课程设计.doc
《操作系统常用页面置换算法课程设计.doc》由会员分享,可在线阅读,更多相关《操作系统常用页面置换算法课程设计.doc(36页珍藏版)》请在咨信网上搜索。
1、。摘 要 在linux中,为了提高内存利用率,提供了内外存进程对换机制,内存空间的分配和回收均以页为单位进行,一个进程只需要将其一部分调入内存便可运行;当操作系统发生缺页中断时,必须在内存选择一个页面将其移出内存,以便为即将调入的页面让出空间。因而引入一种用来选择淘汰哪一页的算法页面置换算法。页面置换算法是操作系统中虚拟存储管理的一个重要部分。页面置换算法在具有层次结构存储器的计算机中,为用户提供一个比主存储器容量大得多的可随机访问的地。常见的页面置换算法有先来先服务算法(FIFO),最近最久未使用算法(LRU)和最佳适应算法(OPT)。关键字:操作系统;FIFO;LRU;OPT;Linux-
2、可编辑修改-目 录1 绪论11.1 设计任务11.2设计思想11.3设计特点11.4基础知识21.4.1 先进先出置换算法(FIFO)21.4.2 最近最久未使用算法(LRU)31.4.3最佳置换算法(OPT)32 各模块伪代码算法42.1伪代码概念42.2伪代码算法42.2.1主函数伪代码算法42.2.2延迟时间函数伪代码算法62.2.3 FIFO算法的伪代码72.2.4 LRU算法的伪代码72.2.5 OPT算法的伪代码103 函数调用关系图123.1函数声明123.1.1主要算法函数123.1.2辅助函数123.2程序函数调用关系图134 测试结果144.1数据初始化144.2页面调度算
3、法144.2.1先进先出算法154.2.2最近最久未使用LRU154.2.3最佳置换算法OPT175 源程序186 设计总结30参考文献31致 谢321 绪论1.1 设计任务 1、了解UNIX的命令及使用格式,熟悉UNIX/LINUX的常用基本命令,练习并掌握UNIX提供的vi编辑器来编译C程序,学会利用gcc、gdb编译、调试C程序。 2、设计一个虚拟存储区和内存工作区,并使用最佳淘汰算法(OPT)、先进先出算法(FIFO)、最近最久未使用算法(LRU)计算访问命中率。(命中率页面失效次数页地址流长度=1-缺页率)1.2设计思想 在进程运行过程中,若期所有要访问的页面不在内存,而需把它们调入
4、内存,但内存已无空闲空间时,为了保证进程正常进行,系统必须从内存中调出一页程序或数据送到磁盘的对换区中。但应将哪个页面调出,须根据一定的算法来确定。通常,把选择换出页面的算法称为页面置换算法。置换算法的好坏将直接影响到系统的性能。 不适当的算法可能会导致进程发生“抖动”,即刚被换出的页很快又要被访问,需要将它重新调入,此时又需要再选一页调出;而此刚被调出的页很快又被访问,有需将它调入,如此频繁地更换页面,以致一个进程在运行中把大部分的时间都花费在页面置换工作上。通过模拟实现请求页式存储管理的几种基本页面置换算法,了解虚拟存储技术的特点,掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思
5、想和实现过程,并比较它们的效率。改进页面置换算法,可以降低页面失败率,从而有效地提高系统性能。从理论上讲,应将那些以后不再会访问的页面置换出来,或把那些在较长时间内不会再访问的页面调出。目前已有多种置换算法,它们都试图更接近于理论上的目标。1.3设计特点 本设计作品主要用C语言编写而成,结构简单,语言易懂,条理清晰。本作品兼容性也非常的高,可以在各种可以编译C语言的编译软件上运行,并能够在cygwin中运行,经多次调试,暂时未发现有何不足。本程序的另一个优点是,程序可以计算大数量数据。如,本程序可以计算的最大物理块个数达到了10000个,用户输入的页面引用串个数也能达到10000个以上。但是,
6、实际生活中系统的物理块个数一般不会达到10000个。因此,我们在提示用户输入页面引用串个数是,只提示最大输入100个。但是代码不足在于使用到了较多的static全局变量使得整个代码质量不是很好,而且也只是简单的根据算法设计来模拟实现整个过程。我通过先查找该页面是否在页帧中存在,若不存在则需要页面置换,通过刷新每个页帧的time值来得到每次的最小值来进行页面的置换,最小值即代表着最近最少使用的页面。 经过测试,这个系统已经达到了题目中的全部要求。这个程序有很多优点有一个是界面简明,简洁明了的程序菜单;一个是智能化的模块设计,减少了许多人工操作,如功能模块操作结束后,均会返回主菜单进行下一模板的运
7、行,并提示是否再进行类似的操作,这样给用户带来了操作的方便,大大提高了学生选课的效率还有就是提示语言既简洁又明确,层次分明等等;当然也有缺点如程序仍然存在不合理的地方,例如程序某些部分输入错误不能立刻返回改正;信息表达方式不丰富,比较单一,缺少图片、音乐等元化表达方式。 FIFO算法总是选择在内存驻留时间最长的一页将其淘汰。这种算法基于CPU按线性顺序访问地址空间的这个假设上,许多时候,CPU不是按吸纳型顺序访问地址空间的。所以,那些在内存中停留时间最长的页往往被访问到。这就造成FIFO算法的缺页率不太理想。并且,FIFO还有一个缺点就是Belady奇异现象。实现FIFO算法无需硬件提供新的帮
8、助,只采用循环数组管理驻留集即可。OPT算法被誉为“最佳算法”,因为他淘汰下次访问距当前最远的那些页中序号最小的一页。所以,OPT算法得出的缺页率是最小的。但是,OPT算法在使用前必须先得知整个访问串,这很难实现。因此,OPT算法知识一种概念中的算法。LRU算法的实现耗费较高,并且需要硬件的支持,但是效果较好。就缺页率而言,OPT算法最佳,FIFO算法最差。1.4基础知识1.4.1 先进先出置换算法(FIFO) FIFO算法是最早出现的算法。该算法总是淘汰最先进入内存的页面,即选择在内存驻留时间最久的页面予以淘汰。该算法实现简单,只需要把一个进程已调入内存的页面按先来后次序链接成一个队列,并设
9、置一个指针,称为替换指针,使它总是指向最老的页面。但是该算法与进程实际运行的规律不相符合,因为在进程中,有些页面经常被访问。1.4.2 最近最久未使用算法(LRU) 选择最近一段时间最长时间没有被访问过的页面予以淘汰。LRU算法是根据页面调入内存后的使用情况进行决策。由于无法预测各页面将来的使用情况,采取“最近的过去”作为“最近的将来”的近似。选择最近最久未使用的页面予以淘汰。实现:赋予每个页面一个方位字段,用来记录一个页面自上次被访问以来所经历的时间T,当要淘汰一个页面的,选择现有页面中其T值最大的,即最近最久未使用的页面予以淘汰。1.4.3最佳置换算法(OPT)最佳置换算法所选择的被淘汰掉
10、的页面,将是以后永久不再使用的,或许是在最长(未来)时间内不再被访问的页面。采用最佳置算法,通常可保证获得最低的缺页率。本模拟算法中,最佳页面置换算法实现所采用的思想是:循环读入每个页表项,若该页表在内存中,则读取下一个页表项。若页表不存在内存中:一种情况是内存不满,则将页表放入内存中;若内存块已满,刚分别计算内存中各个页表再次被使用的时间,并将最久不被访问的调出,放入当前读入页表项。-可编辑修改-2 各模块伪代码算法 根据程序提示,用户先将需要计算的页面号引用串,物理块数量和引用串个数输入到文件流中。待程序加载数据完成后,用户继续选择页面置换算法的类型,程序根据用户输入的信息来判断采用哪一种
11、算法进行计算。结构如图2.1所示。图 2.1 总体结构图2.1伪代码概念 伪代码(英语:pseudocode),又称为虚拟代码,是高层次描述算法的一种方法。使用伪代码的目的是让被描述的算法可以容易地以任何一种编程语言(Pascal,C,Java,etc)实现。因此,伪代码必须结构清晰、代码简单、可读性好,介于自然语言与编程语言之间。以编程语言的书写形式指明算法职能。使用伪代码,不用拘泥于具体实现。它是半角式化、不标准的语言。可以把整个算法运行过程的结构用接近自然语言的形式(可以使用任何一种你熟悉的文字,关键是把程序的意思表达出来)描述出来。2.2伪代码算法2.2.1主函数伪代码算法 该程序是按
12、自上而下,自顶向下的设计思想进行设计的。程序各个功能的实现之间的联系采用函数调用与函数嵌套。main()函数是整个程序的入口,程序的开始就是从这里开始的,然后通过main()函数调用其他函数来实现各个功能。具体流程如图2.2所示。图2.2 主函数流程图Begin /*算法开始*/调用designBy()显示出设计者信息Scanf mSIZE,pSIZE,page100 /*mSIZE表示物理块,pSIZE表示页面号引用串个数,page100表示一个引用串的页面号*/do Printf pageiScanf code /*code是一个标记,用来判断用户输入是否符合要求*/Switch(code
13、)case 1: FIFO() /*先进先出算法*/case 2: LRU() /*最近最久未使用算法*/case 3: OPT() /*最佳置换算法*/case 4: exit(0) /*退出程序*/default: 重新输入while(code!=4)Getch(用户输入)End2.2.2延迟时间函数伪代码算法begin变量定义while delay0while i124退格end图2.3 延迟时间函数流程图 延迟时间函数主要由两个for循环构成。延迟时间函数在程序中主要起延迟时间的作用,相当于一个定时器,给程序数据加载,数据处理等提供时间保证。使程序能够正常的进行。其具体流程如图2.3所
14、示。2.2.3 FIFO算法的伪代码 begin 定义变量 while imSIZEpagei0memeryi, itimeiwhile jmSIZEmemeryjtempij while ipSIZEwhile jmSIZEif 新页面号不在物理块中k+if k=mSIZE 则,计算换出页,记录该页进入物理块的时间否则,tempij=memeryjprint 置换次数End FIFO算法是操作系统中最简单最容易实现的一种页面置换算法,它的实现主要运用了两个循环结构。第一个循环的功能是将页面串中的前mSIZE页面直接放入物理块中;第二个循环主要判断当前页面是否在物理块中,若在物理块中,则继续读
15、取下一个页面。否则,将最先进入物理块的页面写入到物理块中。其主要执行流程如图2.4所示。2.2.4 LRU算法的伪代码 LRU算法是将最近进入物理块且未使用的页面首先换出物理块。LRU函数主要也运用了两个循环来实现其算法,首先将前mSIZE个页面置换到物理块中,然后再按具体算法进行置换页面。其执行流程如图2.5所示。图2.4 FIFO流程图 begin 定义变量 while imSIZE pageimemeryi, itimeiwhile jmSIZEmemeryjtempij while imSIZE前mSIZE个数直接放入while ipSIZE while jmSIZEif 新页面号不在
16、物理块中k+判断新页面号是否在物理块中if k=mSIZE 则,计算换出页,记录该页进入物理块的时间否则,max=flag0flag1?0:1memeryjtempij调用 print(置换次数)End图2.5 LRU流程图2.2.5 OPT算法的伪代码 begin 定义变量 while imSIZEpageimemeryi, itimeiwhile jmSIZEmemeryjtempij 前mSIZE个数直接放入 while ipSIZEwhile jmSIZEif memeryj!=pagei判断新页面号是否在物理块中k+if k=mSIZE 则,计算换出页,记录该页进入物理块的时间否则,
17、max=flag0flag1?0:1tempij=memeryj得到物理块中各页下一次访问时间if memerym=page1退出循环nextm=1调用 print(置换次数)End OPT算法是将内存中最长时间内不会用的页面置换出去,这种算法的优点是系统利用率,内存利用率都非常的高。但是这种算法目前无法实现,因为实际中,系统根本无法预知哪一个页面最先执行,哪一个页面最后执行,各个页面的执行顺序都无法确定根本就不能确定页面换出的次序。OPT算法主要用于对其他算法效率的评估。OPT函数的执行情况如图2.6所示。图2.6 OPT流程图3 函数调用关系图3.1函数声明3.1.1主要算法函数主要算法函
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 操作系统 常用 页面 置换 算法 课程设计
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【a199****6536】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【a199****6536】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。