操作系统课设-LRU-OPT.doc

Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date操作系统课设-LRU-OPT操作系统课设-LRU-OPT学 号： 01209103401课 程 设 计题 目请求页式管理缺页中断模拟设计-LRU、OPT学 院计算机科学与技术学院专 业计算机科学与技术专业班 级计算机0901班姓 名指导教师王红霞2012年1月11日课程设计任务书学生姓名： 专业班级： 计算机0901班 指导教师： 王红霞 工作单位： 计算机科学与技术学院 题 目: 请求页式管理缺页中断模拟设计- LRU、OPT初始条件：1预备内容：阅读操作系统的内存管理章节内容，了解有关虚拟存储器、页式存储管理等概念，并体会和了解缺页和页面置换的具体实施方法。2实践准备：掌握一种计算机高级语言的使用。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1实现指定淘汰算法。能够处理以下的情形： 能够输入给作业分配的内存块数； 能够输入给定的页面，并计算发生缺页的次数以及缺页率； 缺页时，如果发生页面置换，输出淘汰的页号。2设计报告内容应说明： 课程设计目的与功能； 需求分析，数据结构或模块说明(功能与框图)； 源程序的主要部分； 测试用例，运行结果与运行情况分析； 自我评价与总结：i）你认为你完成的设计哪些地方做得比较好或比较出色；ii）什么地方做得不太好，以后如何改正；iii）从本设计得到的收获（在编写，调试，执行过程中的经验和教训）；iv）完成本题是否有其他的其他方法（如果有，简要说明该方法）；v）对实验题的评价和改进意见，请你推荐设计题目。时间安排：设计安排一周：周1、周2：完成程序分析及设计。周2、周3：完成程序调试及测试。周4、周5：验收，撰写课程设计报告。（注意事项：严禁抄袭，一旦发现，抄与被抄的一律按0分记）指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日请求页式管理缺页中断模拟设计 -LRU、OPT1 设计目的与功能1.1 设计目的巩固并加深对虚拟存储器、请求页式存储管理等概念的理解，掌握请求页式管理中的置换算法的基本思想。并针对LRU(最近最久未使用页面置换算法)，以及OPT(理想型淘汰算法)两种算法，利用高级语言，设计出相应的模拟程序。结合设计的程序，在理论联系实际的基础上，分析各个页面置换算法的优缺点。以及在对课程的整体把握上，提升对操作系统这门课程的全面认识。1.2 设计功能本次课程设计需要实现LRU和OPT两种置换算法。能够实现以下功能：1） 能够输入给作业分配的内存块数；2） 能够输入给定的页面，并计算发生缺页的次数以及缺页率； 3） 缺页时，如果发生页面置换，输出淘汰的页号。在实现以上功能的前提下，程序也应该达到正确性、可读性、健壮性、效率与地存储量要求等算法的5个特性。2 设计需求分析2.1 需求分析2.1.1 请求页式管理的实现请求页式管理是在静态页式管理的基础上发展起来的，它允许只装入部分页面的程序和数据，便启动运行。此后，再通过调页功能和页面置换功能，陆续把即将要运行的页面调入内存，同时把暂时不运行的页面换出到外存上，置换时以页面为单位。为了能实现请求调页和置换功能，系统必须提供必要的硬件支持和相应的软件。其中硬件支持包括：1） 请求分页的页表机制，它是在纯分页的页表机制上增加若干项而形成的，作为请求分页的数据结构；2） 缺页中断机构，当要访问的页面尚未调入内存时，便产生一缺页中断，以请求OS将所缺的页调入内存；3） 地址变换机构，它同样是在纯分页地址变换机构的基础上形成的。2.1.2 置换算法分析请求页式管理中的置换算法在内存中没有空闲页时被调用，它的目的是选出一个被淘汰的页面。如果内存中有足够的空闲页面存放调入的页，则不必使用置换算法。本次设计使用最近最久未使用页面置换算法(least recently used，LRU)和理想型淘汰算法(optional replacement algorithm，OPT)。2.1.2.1 LRU置换算法最近最久未使用页面置换算法(least recently used，LRU)，该算法的基本思想是：当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。该算法的主要出发点是，如果某页被访问了，则它可能马上还要被访问，或者如果某页很长时间未被访问，则它在最近一段时间也不会被访问。2.1.2.2 OPT置换算法理想型淘汰算法(optional replacement algorithm，OPT)，该算法淘汰在访问串中将来再也不出现的或者是在离当前最远的位置上出现的页，这样淘汰掉该页将不会造成因需要访问该页又立即把它调入的现象。这种算法难以实现，因为它要求必须预先知道每一个进程的访问串。请求页式管理的具体实现过程如图1所示。2.2 数据结构及功能框图2.2.1 数据结构程序是以基本的变量和结构体实现，在两种算法中有大量的代码重用，故采用宏定义(#define LO(wname)等，使代码更加简化。/- - - - - - - - - - - 基本数据变量说明- - - - - - - - - - - - - int input; /输入的页面数int num; /内存块允许装入页面数int *in; /准备调入的页面序列 int *memory; /用来记录进入内存的页面信息struct pageint Pnumber; /页面的页号int Mnumber; /在内存中对应的块号int stayin; /是否在内存中;page PtotalN; /对N个页面进行操作开始结束请求页面序列是否结束页面是否在内存中内存块是否已满选择要调入页面放入未被占用的内存块中,修改页表利用算法,选择应该替换的页面并修改YYYNNN图1 请求页式管理实现过程/- - - - - - - - - - - 基本操作的函数原型说明- - - - - - - - - - - - - void LRU(); /实现LRU算法的函数void OPT(); /实现OPT算法的函数int getLRU(int page); /LRU中页面置换函数，对给定的页page,替换页框中的页int getOPT(int page); /OPT中页面置换函数，对给定的页page,替换页框中的页#define LO(wname); /对LRU和OPT中的前num个页的公操作处理#define get(smblx,smbly,smblz); /页面置换过程的公操作，用smblx等变量替换 2.2.2 程序功能框图程序中首先输入页面的数目存入input中，输入页框的数目存入num中，在按次序输入页面号码，存入in数组中。程序给出选择，当进行LRU模块时，LRU模块对页面进行分配，当出现缺页调用getLRU()进行缺页处理，而OPT模块与之类似。程序功能框图如图2。Main()getOPT (int page)getLRU(int page)OPT()LRU()图2 程序功能框图3 源程序的主要部分3.1 源程序简介本次设计中LRU以及OPT算法中页面置换的思想，分别对照页框的内容，向前查找最久未被使用的页面号和向后查找最后被使用的页面号，将其替换之。在设计的思想上可以转化为以当前即将调入的页面为中心，LRU为向前查找离中心最远的页号，而OPT为向后查找离中心最远的页号。这样在方法上有了共同之处，以此可以通过对相同的代码进行宏定义。3.2 源程序核心代码3.2.1 main函数代码main函数实现对各输入数据及待数据结构的初始化，以及通过选择来调用LRU或OPT算法。伪代码如下：int main() /页号、块号、页面顺序的输入，以及初始化等工作。while(true) /部分全局变量的初始化工作，每次循环需重新开始 char chose;cout<<"请您选择：1、LRU算法"<<endl;cout<<" 2、OPT算法"<<endl;cout<<" 3、退出"<<endl; cout<<"*"<<endl;cin>>chose;if(chose!='1'&&chose!='2')break;switch(chose)case '1':LRU();break;case '2':OPT();break; cout<<"*"<<endl;3.2.2 LRU及OPT函数代码LRU和OPT的主要思想有许多共同之处，所以通过宏定义，来实现程序的共同功能。程序中都是通过LO宏来实现的，区别在于传递的参数不同，即LRU函数调用getLRU()子函数。而OPT函数调用getOPT()函数。void LRU() cout<<"LRU替换算法过程如下:"<<endl; LO(LRU); /通过LO宏，传递LRU给get#wname(int page)，即getLRU(int page)void OPT() cout<<"OPT替换算法过程如下:"<<endl; LO(OPT); /通过LO宏，传递OPT给get#wname(int page)，即getOPT(int page)3.2.3 LO（wname）宏的代码LO宏是用来对LRU和OPT的置换进行公处理的，即在内存块未满，或者不需要发生置换时两者的代码是相同的，而唯一不同在于缺页中断处理函数，getLRU(int page)或者getOPT(int page)。所以，通过宏定义，把不同的代码作为参数传递，来实现不同函数的功能。伪代码如下：#define LO(wname)int i,missTime=0,replace=0,full=0,page=0; /i 为循环控制变量，missTime为缺页次数/replace代表置换的页框号full为控制变量，page为页面数do /实现块未满时的页面分配，LRU和OPT相同while(full!=num);for( i=page;i<input;i+)if(Ptotalini.stayin =1) cout<<ini<<"号页已在页框中，"<<endl;elsemissTime+;replace=get#wname(i); /根据传递的参数不同，调度不同的函数，返回页框号 /进行页面替换cout<<endl<<"经统计：缺页次数："<<missTime<<"次"<<"缺页率"<<double(missTime)/input*100<<"%"<<endl; /对缺页率进行输出3.2.4 getLRU和getOPT函数代码getLRU和getOPT函数是一种搜索算法，返回将要被替换的页框号，页框中的内容即为被替换的页号。两个函数有一定的相似处，即getLRU函数为向前搜索，而getOPT为向后搜索，所以程序中用到get(symlx,symbly,symblz)宏，伪代码如下：int getLRU(int page) get(-,>=0,<); /get宏，传递的参数为-,>=0,<等 return getNum; /返回页框号 int getOPT(int page) get(+,<input,>); /get宏，传递的参数为+,<input,>等 return getNum; /返回页框号3.2.5 get(smblx,smbly,smblz)宏的代码getLRU和getOPT的搜索算法在思想上相似，即前者向前搜索页第一次出现的申请序号，而后者是向后搜索接下来第一次出现的申请序号，所以用get宏来对相同代码进行公操作，伪代码如下：#define get(smblx,smbly,smblz) for(i=0;i<num;i+)for(int j=0;j<10;j+)if(Ptotalj.Mnumber=i)for(int t=page#smblx 1;t#smbly;t#smblx#smblx) /宏填充部分，填充内容如上 /向前或后找出该页第一次申请的序号for(i=0;i<num;i+)if(geti#smblz getgetNum) /返回将要被置换的页号，存入到getNUM中getNum=i; 4 测试4.1测试用例设计请求分页管理系统中，有一用户作业，它一次要访问的页的序列是：2 3 2 1 5 2 4 5 3 2 5 2 共12页，若分配给作业可以使用的主存空间供3个物理块，则LRU和OPT的置换算法的页面分配如表1和表2。表1 LRU页面置换算法LRU2 32152453252页1222222223333页233355555555页3111444222判断×××××××共产生7次缺页中断，淘汰页号分别为：3， 1 ，2， 4 缺页率：58.33%表2 OPT页面置换算法OPT2 32152453252页1222222444222页233333333333页3155555555判断××××××共产生6次缺页中断，淘汰页号分别为： 1 ，2 ，4 缺页率：50%4.2 运行结果及情况分析根据测试用例，对结果进行测试分析，以下为程序的分析过程。1) 程序首先需要输入页面数、页框数，然后给出页面请求序列，最后可以对页面置换算法进行选择（LRU和OPT的选择），在每执行完一次后，程序会继续给出选择界面，方面两种算法过程和结果的对照。程序的输入界面如图3所示；图3 输入界面 2) 在输入界面中输入1，则程序调用LRU页面替换算法，则程序的页面分配过程，缺页率，缺页次数会被一一列出，从过程可以看出，页面替换的顺序为3,1,2,4，这与用例的正确结果吻合，达到了算法的目的，具体情况如图4所示：图4 LRU替换算法过程和结果3）当输入2时，程序调用OPT算法，程序的页面分配情况，缺页次数及缺页率如图5所示，从图中可以看出，程序中被替换掉的页面分别为1,2,4，这也和用例吻合，得出了正确的结果，OPT算法的缺页次数为6，缺页率为50%。图5 OPT替换算法过程和结果小结：从程序的运行结果和输出情况可以看出，程序有良好的交互界面，有正确的结果，并且有一定的健壮性，如对于用例中的2 3 2，程序在没有在未用完页框的情况下直接给第三次请求的2号页分配一个新页框，这说明程序有严谨的逻辑步骤。5 评价和总结5.1 自我评价本次课程设计用时用高级语言模拟系统中的页面置换算法，从整体上达到了设计的目的和要求。我的设计思路是首先，要对问题有一个整体而全面的认识，抓住问题的核心所在；其次，要针对问题，主要是核心症结，给出设计思想，这时可以查阅书籍或搜寻网上资料，辅助自己对的问题理解，以确保设计思想的正确性；再次，解决核心问题，在此基础之上，为设计丰满羽翼，达到算法所要求的5个特性：正确性、可读性、健壮性、效率与地存储量要求；最后，对程序反复调试，尽己所能把算法精简改进。就设计优点来谈，首先程序的思想与计算机操作系统页面置换算法（LRU,OPT）的思想吻合，这样确保了程序的正确性和可读性，并且从本质上体会到页面置换算法思想的精髓所在；其次，程序中的大部分的数据结构仅仅为简单的变量和结构体数组，没有冗杂的指针和链表，使程序用尽量简单的方法实现了尽量多的功能；最后，针对LRU和OPT算法中思想的相似处，我采用了宏定义，不仅大大优化了代码使最后的代码大量的减少，而且使两种算法的区别明显的体现出来，易于对两种置换算法的仔细斟酌、比较。本次课程设计的缺点为实验的平台仍是控制台程序（DOS环境），所以在以后的设计中，将尝试VC界面程序。5.2 收获和改进本次课设的收获分为两点：在对课程内容上，从模拟缺页中断页面置换算法中进一步理解了操作系统原理，对这门课程有了更深的认识，并且激起了想进一步了解如windows操作系统(windows核心编程)的兴趣；在对编程技巧方面，从了解MFC后，对MFC中的宏定义有了一定的了解和认识，发现宏定义也是一种巧妙的封装方法。本程序中两次使用了宏定义，程序在编译的过程会将代码插入到宏调用处，但在程序的读者看来，程序会更加的精简、明了，易于对比。程序从设计技巧来说还有许多其他的方法，如对于LRU算法可以用队列来记录页面置换的顺序，而与之对应的OPT算法则可以栈来记录接下来要调入页面的次序。在记录LRU（最近最久未使用）时，也可以用NUM*NUM的二阶数组来记录等。5.3 评价和意见本次课程设计是对操作系统这门课程理论知识的映射，不同的题目是对不同知识模块进行模拟，在实践的基础上加深了对操作系统理论的认识，在某种程度上得到了提高。对本次课程设计的意见如下：因为操作系统这门课程中并没有直接涉及到某个操作系统（Windows、Linux等）的设计过程的讲解，课程内容过于理论化，而在课程设计的过程中题目过于细节化，从而对操作系统失去总体观念。希望课程设计中题目应当为两个不同的知识点，在一定程度上加深难度，也扩充了理解的知识面。6 参考文献1 张尧学，计算机操作系统教程，清华大学出版社，2005年6月2 闵联营，c+程序设计教程武汉理工大学出版社，2005年7月3 王艳平，Windows 程序设计（第二版），人民邮电出版社，2010年2月附：源代码-#include<iostream>#include<stdlib.h>using namespace std;int input,num,*in,*memory; struct pageint Pnumber;int Mnumber;int stayin;page Ptotal10; void LRU();void OPT();int getLRU(int page);int getOPT(int page);int main()cout<<"*"<<endl; cout<<"请输入准备调入页面的数目:"<<endl;cin>>input; cout<<"请输入物理块数目"<<endl;cin>>num;in= new intinput; memory=new intnum; cout<<"请依次输入"<<input<<"个页面号(0-9)"<<endl; int i,temp; for( i=0;i<input;i+) cin>>temp;ini=temp; cout<<"*"<<endl;while(true) for(int n=0;n<10;n+) Ptotaln.Pnumber=n;Ptotaln.Mnumber=-1;Ptotaln.stayin =0;for(i=0;i<num;i+) memoryi=-1; char chose;cout<<endl;cout<<"请您选择：1、LRU算法"<<endl;cout<<" 2、OPT算法"<<endl;cout<<" 3、退出"<<endl; cout<<"*"<<endl;cin>>chose;if(chose!='1'&&chose!='2')break;switch(chose)case '1':LRU();break;case '2':OPT();break; cout<<"*"<<endl;delete in;delete memory;return 0;#define LO(wname)int i,missTime=0,replace=0,full=0,page=0;do if(Ptotalinpage.stayin =1)cout<<inpage<<"号页已在页框中，"<<endl;page+;if(page=input)break;else continue;elsemissTime+;cout<<inpage<<"号页不在页框中，将其调入"<<full<<"号页框中，"<<endl;memoryfull=inpage;for(int j=0;j<10;j+)if( Ptotalj.Mnumber= full) Ptotalj.Mnumber=-1; Ptotalj.stayin=0;break;Ptotalinpage.stayin=1;Ptotalinpage.Mnumber=full; full+;page+;if(page=input) break;while(full!=num);for( i=page;i<input;i+)if(Ptotalini.stayin =1)cout<<ini<<"号页已在页框中，"<<endl;elsemissTime+;replace=get#wname(i);for(int j=0;j<10;j+)if( Ptotalj.Mnumber=replace)cout<<ini<<"号页不在页框中,替换掉"<<j<<"号页，"<<endl;Ptotalj.Mnumber=-1;Ptotalj.stayin=0;break;memoryreplace=ini;Ptotalini.stayin=1;Ptotalini.Mnumber=replace;cout<<endl<<"经统计：缺页次数："<<missTime<<"次"<<" 缺页率： "<<double(missTime)/input*100<<"%"<<endl;#define get(smblx,smbly,smblz)int *get=new intnum;for(int m=0;m<num;m+)getm=0;int i; for(i=0;i<num;i+)for(int j=0;j<10;j+)if(Ptotalj.Mnumber=i)for(int t=page#smblx 1;t#smbly;t#smblx#smblx)if(j=int)geti=t;break;if(geti=0)geti=input;break;int getNum=0;for(i=0;i<num;i+)if(geti#smblz getgetNum)getNum=i;int getLRU(int page) get(-,>=0,<); return getNum; int getOPT(int page) get(+,<input,>); return getNum; void LRU() cout<<"LRU替换算法过程如下:"<<endl; LO(LRU);void OPT() cout<<"OPT替换算法过程如下:"<<endl; LO(OPT);本科生课程设计成绩评定表班级：计算机0901班 姓名：学号：01209103401序号评分项目满分实得分1学习态度认真、遵守纪律102设计分析合理性103设计方案正确性、可行性、创造性204设计结果正确性405设计报告的规范性106设计验收10总得分/等级评语：注：最终成绩以五级分制记。优（90-100分）、良（80-89分）、中（70-79分）、及格（60-69分）、60分以下为不及格指导教师签名：20 年月日