操作系统页面置换算法课程设计论文.doc

操作系统课程设计任务书题目：常用页面置换算法模拟实验学生姓名： 学号： 班级： 题目类型：软件工程（R） 指导教师： 一、设计目的学生通过该题目的设计过程，掌握常用页面置换算法的原理、软件开发方法并提高解决实际问题的能力。二、设计任务1、了解UNIX的命令及使用格式，熟悉UNIX/LINUX的常用基本命令，练习并掌握UNIX提供的vi编辑器来编译C程序，学会利用gcc、gdb编译、调试C程序。2、设计一个虚拟存储区和内存工作区，并使用最佳淘汰算法（OPT）、先进先出算法（FIFO）、最近最久未使用算法（LRU）计算访问命中率。（命中率页面失效次数页地址流长度）三、设计要求1、 分析设计要求，给出解决方案（要说明设计实现所用的原理、采用的数据结构）。2、 设计合适的测试用例，对得到的运行结果要有分析。3、 设计中遇到的问题，设计的心得体会。4、文档：课程设计打印文档每个学生一份，并装在统一的资料袋中。 5、光盘：每个学生的文档和程序资料建在一个以自己学号和姓名命名的文件夹下，刻录一张光盘，装入资料袋中。四、 提交的成果1. 设计说明书一份，内容包括：1) 中文摘要100字；关键词3-5个；2) 设计思想；3）各模块的伪码算法；4）函数的调用关系图；5）测试结果；6）源程序（带注释）；7）设计总结；8) 参考文献、致谢等。2. 刻制光盘一张。五、 主要参考文献1. 汤子瀛，哲凤屏.计算机操作系统.西安电子科技大学学出版社.2. 王清，李光明.计算机操作系统.冶金工业出版社.3.孙钟秀等. 操作系统教程. 高等教育出版社4.曾明.  Linux操作系统应用教程. 陕西科学技术出版社. 5. 张丽芬，刘利雄.操作系统实验教程. 清华大学出版社.6. 孟静， 操作系统教程原理和实例分析. 高等教育出版社7. 周长林，计算机操作系统教程. 高等教育出版社8. 张尧学，计算机操作系统教程，清华大学出版社9. 任满杰，操作系统原理实用教程，电子工业出版社10.张坤.操作系统实验教程，清华大学出版社六、 各阶段时间安排（共2周）周次日期内容地点第1周星期一二教师讲解设计要求查找参考资料教室图书馆星期三五算法设计，编程实现教室第2周星期一三算法设计，编程实现教室星期四五检查程序，答辩教室 2013年12月9日摘 要操作系统是管理计算机系统的全部硬件资源包括软件资源及数据资源,控制程序运行改善人机界面,为其它应用软件提供支持等，使计算机系统所有资源最大限度地发挥作用，为用户提供方便的、有效的、友善的服务界面。操作系统是一个庞大的管理控制程序，大致包括5个方面的管理功能:进程与处理机管理、作业管理、存储管理、设备管理、文件管理。在地址映射过程中，若在页面中发现所要访问的页面不再内存中，则产生缺页中断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法（Page-Replacement Algorithms）。本次课程设计应用请求分页调度算法OPT、FIFO和LRU模拟页面调度算法，并提供性能比较分析功能。 关键词：操作系统；页面置换算法；LRU算法；OPT算法；FIFO算法目 录1 绪论11.1问题的提出11.2国内外研究的现状11.3设计思想12 伪码算法32.1先进先出页面置换算法32.2最近最久未使用置换算法42.3最佳置换算法63 函数调用关系图84 运行结果95 结论11参考文献12致 谢13附录141绪论1.1问题的提出 在存储器管理方式中，有一个特点，就是当要求作业全部装入内存才能运行。但是这样就存在两种情况：（1）有的作业很大，不能全部装入内存，致使作业无法进行。（2）有大量作业要求运行时，内存容量不足容纳所有作业，而虚拟内存技术正是在逻辑上扩充内存容量，将会解决以上两个问题。所以，可以当进程开始运行时，先将一部分程序装入内存，另一部分暂时留在外存；当要执行的指令不在内存时，由系统自动完成将它们从外存调入内存的工作；当没有足够的内存空间时系统自动选择部分内存空间，将其中原有的内容交换到磁盘上，并释放这些内存空间供其它进程使用。通常，把选择换出页面的算法称为页面置换算法，模拟页面置换算法用以客观解决内存不足的矛盾。 1.2国内外研究的现状 1961年英国曼彻斯特大学推出了“虚拟存储”管理技术，并在ATRAS计算机上实现这一技术，70年代以后，这一技术才真正广泛使用，目前许多大型计算机均采用此技术。虚拟存储管理技术的关键在于页面置换算法的选择。1966年Belady在理论上提出最优页面置换算法(Optimal Replacement Algorithm, OPT)，此外还有先进先出置换算法(first input first output, FIFO) ，最近最少使用页面置换算法(least recently used, LRU)，最少使用页面置换算法(least frequent used, LFU，或最不常用算法），时钟置换算法（clock，或称最近未使用页面置换算法(not used recently, NUR)），页面缓冲（page buffering）置换算法等。1.3设计思想选择置换算法，先输入所有页面号，为系统分配物理块，依次进行置换: 1.先进先出页面置换算法(FIFO)：这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序存入一个时间数组，并将其中时间值最大的页面进行淘汰，并替换入新的页面就可以实现。2.最近最久未使用页面置换算法(LRU)：算法的基本思想：当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。该算法的主要出发点是，如果某页被访问了，则它可能马上还被访问。或者反过来说，如果某页很长时间未被访问，则它在最近一段时间不会被访问。3.最佳页面置换置换算法(OPT)：其所选择的被淘汰页面，将是永不使用的，或者是在最长时间内不再被访问的页面。可保证获得最低的缺页率。但由于人们目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法也是无法实现的。但是可利用该算法去评价其它算法。2伪码算法2.1先进先出页面置换算法void FIFO() int memery10=0; int time10=0; /*记录进入物理块的时间*/ int i,j,k,m; int max=0; /*记录换出页*/ int count=0; /*记录置换次数*/*前mSIZE个数直接放入*/ for(i=0;i<mSIZE;i+) memeryi=pagei; timei=i; for(j=0;j<mSIZE;j+)tempij=memeryj; for(i=mSIZE;i<pSIZE;i+) /*判断新页面号是否在物理块中*/ for(j=0,k=0;j<mSIZE;j+) if(memeryj!=pagei) k+; if(k=mSIZE) /*如果不在物理块中*/ count+;/*计算换出页*/max=time0<time1?0:1;for(m=2;m<mSIZE;m+)if(timem<timemax)max=m; memerymax=pagei; timemax=i; /*记录该页进入物理块的时间*/ for(j=0;j<mSIZE;j+)tempij=memeryj; else for(j=0;j<mSIZE;j+)tempij=memeryj; compute();print(count);2.2最近最久未使用置换算法void LRU() int memery10=0; int flag10=0; /*记录页面的访问时间*/ int i,j,k,m; int max=0; /*记录换出页*/ int count=0; /*记录置换次数*/*前mSIZE个数直接放入*/ for(i=0;i<mSIZE;i+) memeryi=pagei; flagi=i; for(j=0;j<mSIZE;j+) tempij=memeryj; for(i=mSIZE;i<pSIZE;i+) /*判断新页面号是否在物理块中*/ for(j=0,k=0;j<mSIZE;j+) if(memeryj!=pagei) k+; else flagj=i; /*刷新该页的访问时间*/ if(k=mSIZE) /*如果不在物理块中*/ count+;/*计算换出页*/ max=flag0<flag1?0:1; for(m=2;m<mSIZE;m+) if(flagm<flagmax)max=m; memerymax=pagei; flagmax=i; /*记录该页的访问时间*/ for(j=0;j<mSIZE;j+) tempij=memeryj; else for(j=0;j<mSIZE;j+) tempij=memeryj; compute();print(count);2.3最佳置换算法void OPT() int memery10=0; int next10=0; /*记录下一次访问时间*/ int i,j,k,l,m; int max; /*记录换出页*/ int count=0; /*记录置换次数*/*前mSIZE个数直接放入*/ for(i=0;i<mSIZE;i+) memeryi=pagei; for(j=0;j<mSIZE;j+) tempij=memeryj; for(i=mSIZE;i<pSIZE;i+) /*判断新页面号是否在物理块中*/ for(j=0,k=0;j<mSIZE;j+) if(memeryj!=pagei) k+; if(k=mSIZE) /*如果不在物理块中*/ count+;/*得到物理快中各页下一次访问时间*/for(m=0;m<mSIZE;m+)for(l=i+1;l<pSIZE;l+)if(memerym=pagel)break;nextm=l;/*计算换出页*/max=next0>=next1?0:1;for(m=2;m<mSIZE;m+)if(nextm>nextmax)max=m;/*下一次访问时间都为pSIZE,则置换物理块中第一个*/memerymax=pagei;for(j=0;j<mSIZE;j+)tempij=memeryj; else for(j=0;j<mSIZE;j+) tempij=memeryj; compute();print(count);3函数调用关系图 页面置换算法流程图如下：开始载入页号序列，从第0号得到页号将页号放入物理块中，编号加1引用串编号大于物理块数？NYY页号在物理块?Y根据选择的置换算法完成置换Y页序列号载完？Y结束图3.1页面置换算法流程图4运行结果图4.1初始化操作图4.2数据载入图4.3选择界面图4.4 FIFO算法图4.5 LRU算法图4.6 OPT算法图4.7选择退出界面图4.8退出界面5结论页面置换算法是操作系统中对虚拟存储技术中必不可少的一种置换算法,由于本次设计中要求用先进先出（FIFO）、最近最久未使用页面置换（LRU）和最佳页面置换（OPT）算法来模拟，因此对其他的一些算法就没有涉及到，但是在学习操作系统的时候，都有涉及一些其他的算法，这是在完成课程同时需要掌握的内容。页面走向是根据用户输入页面走向长度和页表长度随机上的布局产生的，在编写程序的时候要确保自己把算法写对了，就要多次进行数据验证有时FIFO、LRU和OPT产生的缺页数和缺页率会相同，这都是可以存在的。本次设计中对于界面的设计点不是很漂亮，需要进一步的改进。 通过这次课程设计的实现操作，真切的感受到文件系统对一个操作系统的重要性，其作用领域几乎涵盖了操作系统的所有文件，所有属性等，对各种文件的操作都是基于文件系统来完成的，体现出了文件系统在目前任何操作系统的意义和重要性。 另外在本次课程设计的过程中，通过向指导老师请教，在网上以及图书馆搜索相关信息大大的加深了对操作系统文件管理的理解和认识，并对操作系统某些领域的产生了兴趣，为以后的继续深研操作系统打下了理论、实践和兴趣基础，收益很大！               参考文献1 严蔚敏，吴伟民.数据结构(C语言版).清华大学出版社. 2005.2 汤小丹，梁红兵，哲凤屏，汤子嬴.计算机操作系统（第三版）.西安电子科技大学出版社. 2007.3汤子瀛，哲凤屏.计算机操作系统.西安电子科技大学出版社.2005.4孟庆昌.牛欣源.Linux教程（第2版）.北京电子工业出版社.2007.3张琼.嵌入式Linux应用程序开发详解.北京人民邮电出版社.2005. 4 李岩等.计算机操作系统.北京中国电力出版社.2009.5 C#高级编程.李铭.清华大学出版社.2009.7 谭浩强.C语言程序设计.清华大学出版社.2005.8 于帆, 赵妮.程序设计基础(C语言版).清华大学出版社.2006.致 谢首先感谢学校为我们安排的这次课程设计，通过这次课程设计，我收获了很多，在很多方面得到了锻炼提高。例如，对于计算机是如何利用很小的内存空间运行很大的应用程序，以前对这个概念是懵懵懂懂，但要自己真正的描述出来肯定是摸不着头脑的，只知道是利用了虚拟存储技术。但是通过此次课程设计对虚拟存储技术的描绘，模拟，深深理解了它的方式方法及其所有优点、可行性，并通过不断地调试加深了印象。同时也要感谢教我们的辅导老师郭老师和贾老师，没有老师的悉心教导我是不可能顺利的完成此次课程设计；同时，还要感谢帮助过我的同学，其实在没有上机的时候我也在做课程设计，但此时也遇到一些问题不能及时请老师解决，所以我就请同学帮忙。我知道其他同学也很忙，也要做很多学习作业，但是他们还是很主动的帮助了我，真的很感谢他们，没有他们，我也不可能这么顺利地完成此次课程设计。附 录本程序的源代码如下所示（使用C语言）：#include <stdio.h>#include <stdlib.h>/*全局变量*/int mSIZE; /*物理块数*/int pSIZE; /*页面号引用串个数*/static int memery10=0; /*物理块中的页号*/static int page100=0; /*页面号引用串*/static int temp10010=0; /*辅助数组*/*置换算法函数*/void FIFO();void LRU();void OPT();/*辅助函数*/void print(unsigned int t);void designBy();void download();void mDelay(unsigned int Delay);/*主函数*/int main() int i,k,code;system("color 0A");designBy();printf("请按任意键进行初始化操作. n");printf("*n");printf(" >>>");void getch();system("cls");system("color 0B");printf("请输入物理块的个数(M<=10)：");scanf("%d",&mSIZE);printf("请输入页面号引用串的个数(P<=100)：");scanf("%d",&pSIZE);puts("请依次输入页面号引用串(连续输入，无需隔开)：");for(i=0;i<pSIZE;i+) scanf("%1d",&pagei);download();system("cls");system("color 0E"); do puts("输入的页面号引用串为：");for(k=0;k<=(pSIZE-1)/20;k+)for(i=20*k;(i<pSIZE)&&(i<20*(k+1);i+)if(i+1)%20=0)|(i+1)%20)&&(i=pSIZE-1)printf("%dn",pagei);elseprintf("%d ",pagei);printf("* * * * * * * * * * * * * * * * * * * * * * *n"); printf("* 请选择页面置换算法：ttt *n");printf("* - *n"); printf("* 1.先进先出(FIFO) 2.最近最久未使用(LRU) *n");printf("* 3.最佳(OPT) 4.退出 *n");printf("* * * * * * * * * * * * * * * * * * * * * * *n"); printf("请选择操作： bb"); scanf("%d",&code); switch(code) case 1: FIFO(); break; case 2: LRU(); break; case 3: OPT(); break; case 4: system("cls"); system("color 0A"); designBy(); /*显示设计者信息后退出*/printf("谢谢使用页面置换算法演示器! n");printf("*n"); exit(0);default:printf("输入错误，请重新输入："); printf("按任意键重新选择置换算法：>>>");void getch();system("cls"); while (code!=4); void getch();/*载入数据*/void download()int i;system("color 0D");printf("*n");printf("正在载入数据，请稍候 !n");printf("*n");printf("Loading.n");printf(" O");for(i=0;i<51;i+)printf("b");for(i=0;i<50;i+)mDelay(pSIZE+mSIZE)/2);printf(">");printf("nFinish.n载入成功，按任意键进入置换算法选择界面：>>>");void getch();/*设置延迟*/void mDelay(unsigned int Delay) unsigned int i; for(;Delay>0;Delay-) for(i=0;i<124;i+) printf(" b"); /*显示设计者信息*/ void designBy()printf("*n");printf(" 课题五：页面置换算法n");printf(" 学号：11730113 n");printf("姓名：liuqian <linux > n");printf("*n");void print(unsigned int t)int i,j,k,l;int flag;for(k=0;k<=(pSIZE-1)/20;k+)for(i=20*k;(i<pSIZE)&&(i<20*(k+1);i+)if(i+1)%20=0)|(i+1)%20)&&(i=pSIZE-1)printf("%dn",pagei);elseprintf("%d ",pagei);for(j=0;j<mSIZE;j+)for(i=20*k;(i<mSIZE+20*k)&&(i<pSIZE);i+)if(i>=j)printf(" |%d|",tempij);elseprintf(" | |");for(i=mSIZE+20*k;(i<pSIZE)&&(i<20*(k+1);i+)for(flag=0,l=0;l<mSIZE;l+)if(tempil=tempi-1l)flag+;if(flag=mSIZE)/*页面在物理块中*/printf(" ");elseprintf(" |%d|",tempij);/*每行显示20个*/if(i%20=0)continue;printf("n");printf("-n");printf("缺页次数：%dtt",t+mSIZE);printf("缺页率：%d/%dn",t+mSIZE,pSIZE);printf("置换次数：%dtt",t);printf("访问命中率：%d%n",(pSIZE-(t+mSIZE)*100/pSIZE);printf("-n");/*计算过程延迟*/void compute()int i;printf("正在进行相关计算，请稍候");for(i=1;i<20;i+)mDelay(15);if(i%4=0)printf("bbbbbb bbbbbb");elseprintf("");for(i=0;i+<30;printf("b");for(i=0;i+<30;printf(" ");for(i=0;i+<30;printf("b");/*先进先出页面置换算法*/void FIFO() int memery10=0; int time10=0; /*记录进入物理块的时间*/ int i,j,k,m; int max=0; /*记录换出页*/ int count=0; /*记录置换次数*/*前mSIZE个数直接放入*/ for(i=0;i<mSIZE;i+) memeryi=pagei; timei=i; for(j=0;j<mSIZE;j+) tempij=memeryj; for(i=mSIZE;i<pSIZE;i+) /*判断新页面号是否在物理块中*/ for(j=0,k=0;j<mSIZE;j+) if(memeryj!=pagei) k+; if(k=mSIZE) /*如果不在物理块中*/ count+;/*计算换出页*/ max=time0<time1?0:1;for(m=2;m<mSIZE;m+)if(timem<timemax)max=m; memerymax=pagei; timemax=i; /*记录该页进入物理块的时间*/ for(j=0;j<mSIZE;j+) tempij=memeryj; else for(j=0;j<mSIZE;j+) tempij=memeryj; compute();print(count);/*最近最久未使用置换算法*/void LRU() int memery10=0; int flag10=0; /*记录页面的访问时间*/ int i,j,k,m; int max=0; /*记录换出页*/ int count=0; /*记录置换次数*/*前mSIZE个数直接放入*/ for(i=0;i<mSIZE;i+) memeryi=pagei; flagi=i; for(j=0;j<mSIZE;j+) tempij=memeryj; for(i=mSIZE;i<pSIZE;i+) /*判断新页面号是否在物理块中*/ for(j=0,k=0;j<mSIZE;j+) if(memeryj!=pagei) k+; else flagj=i; /*刷新该页的访问时间*/ if(k=mSIZE) /*如果不在物理块中*/ count+;/*计算换出页*/ max=flag0<flag1?0:1;for(m=2;m<mSIZE;m+)if(flagm<flagmax)max=m; memerymax=pagei; flagmax=i; /*记录该页的访问时间*/ for(j=0;j<mSIZE;j+) tempij=memeryj; else for(j=0;j<mSIZE;j+) tempij=memeryj; compute();print(count);/*最佳置换算法*/void OPT() int memery10=0; int next10=0; /*记录下一次访问时间*/ int i,j,k,l,m; int max; /*记录换出页*/ int count=0; /*记录置换次数*/*前mSIZE个数直接放入*/ for(i=0;i<mSIZE;i+) memeryi=pagei; for(j=0;j<mSIZE;j+) tempij=memeryj; for(i=mSIZE;i<pSIZE;i+) /*判断新页面号是否在物理块中*/ for(j=0,k=0;j<mSIZE;j+) if(memeryj!=pagei) k+; if(k=mSIZE) /*如果不在物理块中*/ count+;/*得到物理快中各页下一次访问时间*/for(m=0;m<mSIZE;m+)for(l=i+1;l<pSIZE;l+)if(memerym=pagel)break;nextm=l;/*计算换出页*/max=next0>=next1?0:1;for(m=2;m<mSIZE;m+)if(nextm>nextmax)max=m;/*下一次访问时间都为pSIZE,则置换物理块中第一个*/memerymax=pagei;for(j=0;j<mSIZE;j+)tempij=memeryj; else for(j=0;j<mSIZE;j+) tempij=memeryj; compute();print(count);