请求页式管理缺页中断模拟设计--lru、opt

学号课程设计题目请求页式管理缺页中断模拟设计LRU、OPT学院计算机科学与技术学院专业班级姓名指导教师课程设计任务书学生姓名指导教师工作单位计算机科学与技术学院题目请求页式管理缺页中断模拟设计LRU、OPT初始条件1预备内容阅读操作系统的内存管理章节内容，了解有关虚拟存储器、页式存储管理等概念，并体会和了解缺页和页面置换的具体实施方法。2实践准备掌握一种计算机高级语言的使用。要求完成的主要任务（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1实现指定淘汰算法。能够处理以下的情形能够输入给作业分配的内存块数；能够输入给定的页面，并计算发生缺页的次数以及缺页率；缺页时，如果发生页面置换，输出淘汰的页号。2设计报告内容应说明需求分析；功能设计（数据结构及模块说明）；开发平台及源程序的主要部分；测试用例，运行结果与运行情况分析；自我评价与总结I）你认为你完成的设计哪些地方做得比较好或比较出色；II）什么地方做得不太好，以后如何改正；III）从本设计得到的收获（在编写，调试，执行过程中的经验和教训）；IV）完成本题是否有其他方法（如果有，简要说明该方法）；时间安排设计安排一周周1、周2完成程序分析及设计。周2、周3完成程序调试及测试。周4、周5验收、撰写课程设计报告。（注意事项严禁抄袭，一旦发现，一律按0分记）指导教师签名年月日系主任（或责任教师）签名年月日请求页式管理缺页中断模拟设计LRU、OPT1设计目的与功能11设计目的巩固并加深对虚拟存储器、请求页式存储管理等概念的理解，掌握请求页式管理中的置换算法的基本思想。并针对LRU最近最久未使用页面置换算法，以及OPT理想型淘汰算法两种算法，利用高级语言，设计出相应的模拟程序。结合设计的程序，在理论联系实际的基础上，分析各个页面置换算法的优缺点。以及在对课程的整体把握上，提升对操作系统这门课程的全面认识。12设计功能本次课程设计需要实现LRU和OPT两种置换算法。能够实现以下功能1）能够输入给作业分配的内存块数；2）能够输入给定的页面，并计算发生缺页的次数以及缺页率；3）缺页时，如果发生页面置换，输出淘汰的页号。2设计需求分析21需求分析211请求页式管理的实现请求页式管理是在静态页式管理的基础上发展起来的，它允许只装入部分页面的程序和数据，便启动运行。此后，再通过调页功能和页面置换功能，陆续把即将要运行的页面调入内存，同时把暂时不运行的页面换出到外存上，置换时以页面为单位。为了能实现请求调页和置换功能，系统必须提供必要的硬件支持和相应的软件。其中硬件支持包括1）请求分页的页表机制，它是在纯分页的页表机制上增加若干项而形成的，作为请求分页的数据结构；2）缺页中断机构，当要访问的页面尚未调入内存时，便产生一缺页中断，以请求OS将所缺的页调入内存；3）地址变换机构，它同样是在纯分页地址变换机构的基础上形成的。212置换算法分析请求页式管理中的置换算法在内存中没有空闲页时被调用，它的目的是选出一个被淘汰的页面。如果内存中有足够的空闲页面存放调入的页，则不必使用置换算法。本次设计使用最近最久未使用页面置换算法LEASTRECENTLYUSED，LRU和理想型淘汰算法OPTIONALREPLACEMENTALGORITHM，OPT。LRU置换算法最近最久未使用页面置换算法LEASTRECENTLYUSED，LRU，该算法的基本思想是当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。该算法的主要出发点是，如果某页被访问了，则它可能马上还要被访问，或者如果某页很长时间未被访问，则它在最近一段时间也不会被访问。OPT置换算法理想型淘汰算法OPTIONALREPLACEMENTALGORITHM，OPT，该算法淘汰在访问串中将来再也不出现的或者是在离当前最远的位置上出现的页，这样淘汰掉该页将不会造成因需要访问该页又立即把它调入的现象。这种算法难以实现，因为它要求必须预先知道每一个进程的访问串。22数据结构及功能框图基本数据变量说明INTINPUT/输入的页面数INTNUM/内存块允许装入页面数INTIN/准备调入的页面序列INTMEMORY/用来记录进入内存的页面信息STRUCTPAGEINTPNUMBER/页面的页号INTMNUMBER/在内存中对应的块号INTSTAYIN/是否在内存中PAGEPTOTALN/对N个页面进行操作基本操作的函数原型说明VOIDLRU/实现LRU算法的函数VOIDOPT/实现OPT算法的函数请求页式管理实现过程3源程序的主要部分31源程序简介本次设计中LRU以及OPT算法中页面置换的思想，分别对照页框的内容，向前查找最久未被使用的页面号和向后查找最后被使用的页面号，将其替换之。在设计的思想上可以转化为以当前即将调入的页面为中心，LRU为向前查找离中心最远的页号，而OPT为向后查找离中心最远的页号。32源程序核心代码开始结束请求页面序列是否结束页面是否在内存中内存块是否已满选择要调入页面放入未被占用的内存块中,修改页表利用算法,选择应该替换的页面并修改YYYNNN321MAIN函数代码MAIN函数实现对各输入数据及待数据结构的初始化，以及通过选择来调用LRU或OPT算法。伪代码如下INTMAIN/页号、块号、页面顺序的输入，以及初始化等工作。WHILETRUE/部分全局变量的初始化工作，每次循环需重新开始CHARCHOSECOUTCHOSEIFCHOSE1SWITCHCHOSECASE1LRUBREAKCASE2OPTBREAKCOUT0,0,/GET宏，传递的参数为,等RETURNGETNUM/返回页框号325GETSMBLX,SMBLY,SMBLZ宏的代码GETLRU和GETOPT的搜索算法在思想上相似，即前者向前搜索页第一次出现的申请序号，而后者是向后搜索接下来第一次出现的申请序号，所以用GET宏来对相同代码进行公操作，伪代码如下DEFINEGETSMBLX,SMBLY,SMBLZFORI0IINCLUDEUSINGNAMESPACESTDINTINPUT,NUM,IN,MEMORYSTRUCTPAGEINTPNUMBERINTMNUMBERINTSTAYINPAGEPTOTAL10VOIDLRUVOIDOPTINTGETLRUINTPAGEINTGETOPTINTPAGEINTMAINCOUTINPUTCOUTNUMINNEWINTINPUTMEMORYNEWINTNUMCOUTTEMPINITEMPCOUTCHOSEIFCHOSE1SWITCHCHOSECASE1LRUBREAKCASE2OPTBREAKCOUT0,RETURNGETNUMVOIDLRUCOUT“LRU替换算法过程如下“ENDLLOLRUVOIDOPTCOUT“OPT替换算法过程如下“ENDLLOOPT本科生课程设计成绩评定表序号评分项目满分实