请求页式管理缺页中断模拟设计--LRU、随机淘汰算法.doc

此文档收集于网络，如有侵权，请联系网站删除学 号： 课 程 设 计题 目请求页式管理缺页中断模拟设计- LRU、随机淘汰算法学 院计算机学院专 业班 级姓 名指导教师 课程设计任务书学生姓名： 指导教师： 工作单位： 计算机科学与技术学院 题 目:请求页式管理缺页中断模拟设计- LRU、随机淘汰算法初始条件：1预备内容：阅读操作系统的内存管理章节内容，了解有关虚拟存储器、页式存储管理等概念，并体会和了解缺页和页面置换的具体实施方法。2实践准备：掌握一种计算机高级语言的使用。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1实现指定淘汰算法。能够处理以下的情形： 能够输入给作业分配的内存块数； 能够输入给定的页面，并计算发生缺页的次数以及缺页率； 缺页时，如果发生页面置换，输出淘汰的页号。2设计报告内容应说明： 需求分析； 功能设计（数据结构及模块说明）； 开发平台及源程序的主要部分； 测试用例，运行结果与运行情况分析； 自我评价与总结：i）你认为你完成的设计哪些地方做得比较好或比较出色；ii）什么地方做得不太好，以后如何改正；iii）从本设计得到的收获（在编写，调试，执行过程中的经验和教训）；iv）完成本题是否有其他方法（如果有，简要说明该方法）；时间安排：设计安排一周：周1、周2：完成程序分析及设计。周2、周3：完成程序调试及测试。周4、周5：验收、撰写课程设计报告。（注意事项：严禁抄袭，一旦发现，一律按0分记）指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日 请求页式管理缺页中段模拟设计 LRU、随机淘汰算法1概述1.1原理页式存储管理把内存分割成大小相等位置固定的若干区域，叫内存页面，内存的分配以“页”为单位，一个程序可以占用不连续的页面，逻辑页面的大小和内存页面的大小相同，内外存的交换也以页为单位进行，页面交换时，先查询快表，若快表中找不到所需页面再去查询页表，若页表中仍未找到说明发生了缺页中断，需先将所需页面调入内存再进行存取。1.2 目的通过分析、设计和实现页式虚拟存储管理缺页中断的模拟系统，熟悉和掌握请求分页式存储管理的实现过程，重点掌握当请求页面不在内存而内存块已经全部被占用时的替换算法，熟悉常见替换算法的原理和实现过程，并利用替换算法的评价指标缺页次数和缺页率，来对各种替换算法进行评价比较。2需求分析用一种计算机高级语言来实现请求页式管理缺页中段模拟设计的LRU和随机淘汰算法，设计要求如下：（1）能够输入给作业分配的内存块数；（2）能够输入给定的页面调用次序； （3）缺页时，如果发生页面置换，输出淘汰的页号。 （4）能统计页面调用缺页次数和缺页率请求分页流程图： 2功能设计 2.1数据结构 （1）用结构体定义页表表项： struct Pageint blockID;/块号int status;/状态，-1为空闲,1为占用;（2）用结构体定义内存块表项struct Blockint pageID;/块内存放页号int status;/是否空闲,-1为空闲,1为占用; (2)算法中涉及到的主要变量：#define MAX_BLOCK 50#define MAX_PAGE 100int pageMAX_PAGE; /记录页的走向bool insideMAX_PAGE; /记录是否缺页，缺-falseint replaceMAX_PAGE; /记录替换次序,无替换为-1，有替换为被替换页号Block blockMAX_BLOCK; /记录物理块Page pageTableMAX_PAGE;/记录页表int pageNum;/页面个数int pageSum; /实际页调用次数int blockSum; /实际块数int lackSum;/缺页次数float lackRate;/缺页率int resultTableMAX_PAGEMAX_BLOCK; /用于存放程序执行过程状态表 2.2模块说明 (3)LRU淘汰算法 void LRU()1、 查看当前页面是否在内存中，如果是则记录当前页面调用状态，将相应的值赋给记录状态数组，返回2、 当前页面不在内存中，判断内存中是否存在空闲块，如果有空闲块，将当前页面调入内存中，并更新页表、块表，以及记录状态数组中返回3、 如果当前内存块满，且当前页面不在内存中。使用最久最近未使用算法，在当前内存块内的页中向前查找，最久未使用的权值最大，将权值最大的页面号和所在内存号返回使用当前页面替换权值最大的页面，并更新页表和块表以及记录状态数组，返回 (4)随机淘汰算法 void Random()1、 查看当前页面是否在内存中，如果是则记录当前页面调用状态，将相应的值赋给记录状态数组，返回2、 当前页面不在内存中，判断内存中是否存在空闲块，如果有空闲块，将当前页面调入内存中，并更新页表、块表，以及记录状态数组中返回3、 如果当前内存块满，且当前页面不在内存中。使用随机算法，随机选择一个内存块，将所选择的内存块内页面的的页面号和所在内存号返回使用当前页面替换权值最大的页面，并更新页表和块表以及记录状态数组，返回 3开发平台及源程序主要部分 3.1开发平台 （1）使用系统：Windows 7 （2）使用语言：C+ （3）开发工具：Visual Studio 2010 3.2源程序主要部分 最近最久未使用算法： void LRU()/最近最久未使用int p;for(p=0;ppageSum;p+)/首先查找是否缺页if(pageTablepagep.status != -1)/在内存块内,不缺页insidep=true;replacep=-1;getStatus(p);continue;/缺页/查找空闲页int b;for(b=0;bblockSum;b+)if(blockb.status=-1)break;if(bblockSum)/存在空闲页pageTablepagep.blockID=b;pageTablepagep.status=1;blockb.pageID=pagep;blockb.status=1;replacep=-1;insidep=false;getStatus(p);continue;else/无空闲页int replacePageNum,replaceBlockNum;/计算权值getWeight_LRU(p,replacePageNum,replaceBlockNum);/替换/修改页表pageTablepagep.blockID=replaceBlockNum;pageTablepagep.status=1;pageTablereplacePageNum.blockID=-1;pageTablereplacePageNum.status=-1;/修改块表blockreplaceBlockNum.pageID=pagep;blockreplaceBlockNum.status=1;/记录状态replacep=replacePageNum;insidep=false;getStatus(p);continue;void getWeight_LRU(int pageNow,int &replacePageNum,int &replaceBlockNum) /获得权值最大页，返回页号和所在物理块号int weightMax,weight;weight=999;weightMax=999;int b,p;for(b=0;b=0;p-)if(blockb.pageID=pagep)weight=p;break;if(weightweightMax)/局当前页面越远，（即page越小）weight越大weightMax=weight;replacePageNum=pagep;replaceBlockNum=b;随机淘汰算法：void Random()/随机算法int p;for(p=0;ppageSum;p+)/首先查找是否缺页if(pageTablepagep.status != -1)/在内存块内,不缺页insidep=true;replacep=-1;getStatus(p);continue;/缺页/查找空闲页int b;for(b=0;bblockSum;b+)if(blockb.status=-1)break;if(bblockSum)/存在空闲页pageTablepagep.blockID=b;pageTablepagep.status=1;blockb.pageID=pagep;blockb.status=1;replacep=-1;insidep=false;getStatus(p);continue;else/无空闲页int replacePageNum,replaceBlockNum;/计算权值getWeight_Random(p,replacePageNum,replaceBlockNum);/计算权值/替换/修改页表pageTablepagep.blockID=replaceBlockNum;pageTablepagep.status=1;pageTablereplacePageNum.blockID=-1;pageTablereplacePageNum.status=-1;/修改块表blockreplaceBlockNum.pageID=pagep;blockreplaceBlockNum.status=1;/记录状态replacep=replacePageNum;insidep=false;getStatus(p);continue;void getWeight_Random(int p,int &replacePageNum,int &replaceBlockNum)srand(unsigned)time(NULL);int blockNum=rand()%blockSum;replacePageNum=blockblockNum.pageID;replaceBlockNum=blockNum;main()函数：int main()int flag;while(1)cout模拟请求页式调度算法：LRU、随机endl;InitSystem();cout1-LRU or 0-Randomflag;if(flag=1)LRU();result(lackSum,lackRate);printTable();else if(flag=0)Random();result(lackSum,lackRate);printTable();elsecout输入错误！endl;cout1-继续 or 0-退出flag;if(flag=0)break;return 0;4调试报告 4.1测试用例 给定内存物理块数为3给定页面数为5 输入的页面号序列为：1 2 3 4 1 2 5 1 2 3 4 5 4.2运行结果及分析 最近最久未使用淘汰算法的运行结果如下： 随机淘汰算法的运行结果如下： 5总结在本次操作系统课程设计，我使用C+实现请求页式管理缺页中断模拟设计的随机和LRU淘汰算法。在了解了虚拟存储器和页式存储管理的有关内容的基础上，掌握了随机和LRU淘汰算法的核心思想及算法的执行流程。然后结合所掌握的C+编程方法和技巧，编写正确的算法，模拟出请求页式缺页中断的随机和LRU淘汰算法。算法的设计主要是要把请求页式管理的执行步骤理解清晰，然后根据请求页式管理的结构，设计出符合实际的数据结构，如页表和块表以及记录状态使用的数组等，然后根据执行流程模拟出各个算法。LRU算法的执行过程还是比较清晰的，我通过对内存中内存块的页，按照当前的页面顺序向前查找，记录此页上次执行的顺序号。遍历所有内存块后，执行顺序号最小的即为权值最大的，将此页的页号和所在内存块号返回，替换。随机算法比较简单，使用随机算法，在内存块中随机选择块号，替换出内存。 本次的课程设计让我巩固了操作系统的相关知识，加深了对课本上理论知识的理解深度，特别是对请求式页式管理的理解。在编写程序之前，我查阅了有关请求页式管理的相关资料，对请求页式管理的数据结构有了更加清晰的认识，这直接关系到程序编写的正确性，因为程序的运行结果正确并不代表程序完全正确，只用在使用了正确的数据结构的基础上运行结果正确才算是正确的程序。但是在编写的过程中还是遇到了类似的问题，由于对页表的理解不够深入，最开始编写的程序虽然能够得到正确的结果，但是没有正确的页表，就不算是模拟了请求页式管理。后来我又修改了数据结构，增加了页表，这使得我的程序更加的完善了。在修改程序的时候，我发现虽然修改了数据结构，但是并未对其他部分的程序有太大的影响，这得益于程序功能的模块划分。在编写程序的时候，我尽量将程序细化，划分成小的模块，比如我将程序划分为初始化数据结构、页式管理算法执行、总程序流程控制三个模块，其中算法执行模块中，我又分了算法基本流程、计算权值、打印状态转移表三个