操作系统课程设计 LRU算法的实现.doc

《操作系统原理》 课程设计报告 姓 名： 黄崧岳 班 级： BX1010 学 号： 5 指导老师： 苏庆刚 二〇一二年 十二 月十四日 目 录 一、《操作系统原理》课程设计的目的与要求 1 1目的 1 2要求 1 二、简述课程设计内容、主要功能和实现环境 1 1课程设计内容 1 2主要功能 1 3实现环境 2 三、任务的分析、设计、实现和讨论 2 1任务的分析 2 2任务的设计与实现 3 4思考题的解答和讨论 10 四、 《操作系统》课程设计小结 14 五、参考文献 14 附录 14 一、《操作系统原理》课程设计的目的与要求 1目的 近年来，由于大规模集成电路（LSI）和超大规模集成电路（VLSI）技术的发展，使存储器的容量不断扩大，价格大幅度下降。但从使用角度看，存储器的容量和成本总受到一定的限制。所以，提高存储器的效率始终是操作系统研究的重要课题之一。虚拟存储技术是用来扩大内存容量的一种重要方法。学生应独立地用高级语言编写几个常用的存储分配算法，并设计一个存储管理的模拟程序，对各种算法进行分析比较，评测其性能优劣，从而加深对这些算法的了解。 2要求 任务四采用最近最少使用页淘汰算法(LRU)实现。为了比较真实地模拟存储管理，可预先生成一个大致符合实际情况的指令地址流。然后模拟这样一种指令序列的执行来计算和分析各种算法的访问命中率。 二、简述课程设计内容、主要功能和实现环境 1课程设计内容 最近最少使用页淘汰算法(LRU)，这是一种经常使用的方法。有各种不同的实施方案，这里采用的是不断调整页表链的方法，即总是淘汰页表链链首的页，而把新访问的页插入链尾。如果当前调用页已在页表内，则把它再次调整到链尾。这样就能保证最近使用的页，总是处于靠近链尾部分，而不常使用的页就移到链首，逐个被淘汰，在页表较大时，调整页表链的代价也是不小的。 2主要功能 菜单函数int menu_select()：用于显示主菜单，可在其中选择1.自定义进程数和块数；2.显示显示用户自定义的进程数和块数；3.进行LRU算法4.退出程序。 最近最久未使用算法函数void LRU()：此函数是将随机产生的页面进行最近未使用便置换的函数，也是本程序的主要部分。 自定义进程数和块数函数void Zidingyi()：此函数是主菜单中的第一个选项，即用户可以自定义所需的进程数和块数。 显示用户自定义的进程数和块数函数void ShowCustomer()：此函数是用于显示用户自定义的进程数和块数的情况。 修改块数函数void Xiugaikuaishu()：此函数是在进行LRU算法后，可以在原来的进程数的基础上，修改块数并重新生成一组LRU算法的过程。 显示每次换页后的结果函数void ShowResult()：此函数是显示在LRU算法的执行过程中每次换页的情况。 显示一定不用换页的函数void ShowNot()：此函数是显示最近使用过的页面，即不用换页的结果。 3实现环境 本次课程设计结合算法的特点，采用Windows操作系统平台。开发工具为Microsoft Visual C++6.0。 三、任务的分析、设计、实现和讨论 1任务的分析 本示例是采用页式分配存储管理方案，并通过分析计算不同页面淘汰算法情况下的访问命中率来比较各种算法的优劣。另外也考虑到改变页面大小和实际存储器容量对计算结果的影响，从而可为算则好的算法、合适的页面尺寸和实存容量提供依据。 本程序是按下述原则生成指令序列的： 50%的指令是顺序执行的。 25%的指令均匀散布在前地址部分。 25%的指令均匀散布在后地址部分。 示例中选用最佳淘汰算法（OPT）和最近最少使用页面淘汰算法（LRU）计算页面命中率。公式为 假定虚存容量为32K，页面尺寸从1K至8K，实存容量从4页至32页。 2任务的设计与实现 2.1 main( )函数流程图： 2.2 主菜单流程图： 2.3 LRU函数流程图： 2.4 Zidingyi( )函数流程图： 2.5 ShowCustomer( )函数流程图： 2.6 ShowNot( )函数流程图： 2.7 ShowResult( )函数流程图： 3操作过程和结果分析 按1进入自定义进程数和块数 按2显示进程数，块数和随机分配页号 按3实现LRU算法，输出命中率 按1修改物理块数，重新实现LRU算法并输出命中率 按4退出程序 FIFO算法 该算法总是淘汰最先进入内存的页面，既选择内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需要把一个进程已调