页面置换算法模拟设计

1、页面置换算法模拟设计课程设计报告课程名称操作系统课题名称专业通信工程班级学号姓名指导教师2019年6月29日湖南工程学院课程设计任务书课程名称课题专业班级学生姓名学号指导老师审批任务书下达日期2019年6月23日任务完成日期2019年6月29日目录1 课题概述41.1 设计要求41.2理论分析42系统分析63程序实现84程序测试135心得体会156附录167评分表30课题：页面置换算法模拟设计1 课题概述1.1 设计要求计算并输出下述各种算法在不同内存容量下的命中率。A.FIFO先进先出的算法B.LRR最近最少使用算法D. LFR 最少访问页面算法C.OPT最佳淘汰算法（先淘汰最不常用的页地址

2、）E.NUR最近最不经常使用算法设计技术参数：（1）命中率=1-页面失效次数/页地址流长度（2）本实验中，页地址流长度为320，页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。（3）随机数产生方法，采用系统提供函数SRAND（和RAND（）来产生1.2理论分析在进程运行过程中，若其所要访问的页面不在内存所需把他们调入内存，但内存已无空闲时，为了保证进程能够正常运行，系统必须从内存中调入一页程序或数据送磁盘的对换区中。但应将那个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法。置换算法的好坏，将直接影响到系统的性能。一个好的页面置换算法，应具有较低的

3、页面更换频率。从理论上将讲，应将那些以后不再访问的页面换出，或把那些较长时间内不再访问的页面调出。目前存在着不同的算法，他们都试图更接近与理论上的目标。拥有页面交换机制的操作系统总是把当前进程中急需处理的部分页面换入到内存当中，而把更多暂时不需要处理的页面放置在外存当中。由于进程需要处理的页面顺序不同，因此必须要在内存与外存之间进行页面交换，页面置换算法也就应运而生。1.先进先出（FIFO）算法这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存停留时间最久的给予淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替代指针，使它

4、总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在incheng中，有些页面经常被访问，比如，含有全局变量，常用函数，例程等方面，FIFO算法并不能保证这些页面不被淘汰。当需要选择一个页面淘汰时，总是选择最先进入内存空间的那一个页面。只要在系统中建立一个FIFO队列，以反映页面的活动情况。被选择的页面总是处于队首的页面，而最近调入的页面永远存放在队列的尾部。2.最近最少使用（LRR算法FIFO置换算法的性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后不能反映页面的使用情况。最近最少使用（LRR）的页面置换算法，是根据页面调入内存后的使用情况进行决策的

5、。由于无法预测各个页面将来的使用情况，只能利用“最近的过去”，作为“最近的将来”的近似。该算法的基本思想是用最近的过去估计最近的将来。假定在内存中的某个页面，在最近一段时间内未被使用的时间最长，那么在最近的将来也可能不再被使用。3.理想页面置换（OPT算法（本次程序中作两个置换算法对比作用）最佳置换算法由Belady于1966年提出，这是一种理想情况下的页面置换算法，但实际上不可能实现。但人们目前把还无法预知一个进程在内的若干页面中，哪一个页面是未来最长时间内不再被访问，因而该算法无法实现。基本思想是内存中每个页都用该页面首次被访问前所要执行的指令数进行标记，标记最大的页应该被置换4.OPT最

6、佳淘汰算法（先淘汰最不常用的页地址）OPTimalreplacement（OPT）它是一种理想化的算法，性能最好，但在实际上难于实现。即选择那些永不使用的，或者是在最长时间内不再被访问的页面置换出去。但是要确定哪一个页面是未来最长时间内不再被访问的，目前来说是很难估计的，所以该算法通常用来评价其它算法5.NUR最近最不经常使用算法为每页设置一位访问位，当每页被访问时，其访问位置1.置换算法在替换页面时，只需要检查它的访问位，如果是0，就将该页换出，如果是1，则重新将它置为0，从而给该页第二次驻留内存的机会，再依次检查下一个页面。如果最后一个页面依然没有被换出，则到第一个页面去重新检查。2系统分

7、析1进入系统模块。进入登陆界面，输入内存页面数和实际页数2页面号打印模块。打印输入的页面号。3 菜单选择模块。选择相应的页面的置换方式，选择相应的字母，进入相应的功能。4 算法模块。选择相应的页面置换算法。5显现输出模块。显示页面被置换的情况。5 .缺页次数和缺页率模块。计算页面号输入的计算结果。6.退出系统模块。退出置换页面。如图2.1模块划分:图2.1模块划分之后进入系统模块如图2.2:图2.2系统流程图3 程序实现1. 首先贯穿全局的全局需要一系列的函数来实现本操作系统的各种功能。需要函数自带的文件stdio.h和stdlib.h.2.以下通过FIFO、OPTLRR三个进行举例：FIFO

8、页面置换和缺页次数及缺页率模块实现如下：voidFIFO()intmemery10=0;inttime10=0;inti,j,k,m;intmax=0;intcount=0;for(i=0;imemeryi=pagei;timei=i;for(j=0;jtempij=memeryj;for(i=mSIZE;ifor(j=0,k=0;jif(memeryj!=pagei)k+;if(k=mSIZE)count+;max=time0for(m=2;mif(timemmax=m;memerymax=pagei;timemax=i;for(j=0;jtempij=memeryj;elsefor(j=0

9、;jtempij=memeryj;LRR 页面置换和缺页次数及缺页率模块实现如下：voidLRR()intmemery10=0;intflag10=0;inti,j,k,m;intmax=0;intcount=0;for(i=0;imemeryi=pagei;flagi=i;for(j=0;jtempij=memeryj;compute();print(count);for(i=mSIZE;ifor(j=0,k=0;jif(memeryj!=pagei)k+;elseflagj=i;if(k=mSIZE)count+;max=flag0for(m=2;mif(flagmmax=m;memery

10、max=pagei;flagmax=i;for(j=0;jtempij=memeryj;elsefor(j=0;jtempij=memeryj;OPT 页面置换和缺页次数及缺页率模块实现如下（本代码在页面置换中：void OPT()compute();print(count);intmemery10=0;intnext10=0;inti,j,k,l,m;intmax;intcount=0;for(i=0;imemeryi=pagei;for(j=0;jtempij=memeryj;for(i=mSIZE;ifor(j=0,k=0;jif(memeryj!=pagei)k+;if(k=mSIZE

11、)count+;for(m=0;mmax=next0>=next1?0:1;for(l=i+1;lif(memerym=pagel)break;nextm=l;for(m=2;mif(nextm>nextmax)max=m;memerymax=pagei;for(j=0;jtempij=memeryj;elsefor(j=0;jtempij=memeryj;compute();print(count);4程序测试系统刚刚进入时，有一个自己手动输入的物理块，输入要置换的页面号等，如图：图4.1物理块如图可知：产生一组随机序列号，只要在主界面中选择我们需要的算法便可以算出我们需要的数据

12、。图4.2主界面当我们选择OPT算法时，等待几秒钟，便会出现各种数据信息，如图：图4.3OPT算法比较上述三种算法,以OPT算法的命中率最高，LRU算法次之,其次是FIFO算法5心得体会在这次课程设计的过程中，我了解到实践大于理论的意义，我们平时不仅要加强理论知识的积累，更要强化实践能力。对于操作系统，实践能力更是考验一个人的能力所在。其中也有不少汗水，但是收获大于付出。然其中也有不少幸酸，比如，看到别的学习能力强的同学一个个都完成了老师指定的任务，自己却什么都没完成的时候，心里无比的焦急，不知该如何是好。再比如，自己还是云里雾里的时候，内心在无数次的自责为什么自己没有别人一样好用的脑子，为什

13、么别人经过了老师的点拨之后就一点就通，而自己对于现学的知识却什么都还是稚嫩的孩童的时候。虽然这一切给了我打击，但是我想这不仅仅是给我在学习这条道路上给予动力，更是让我有求知欲的时候，这个时候我不会骄傲自大，我会虚心求学，我会不懂就问，我会知道自己的弱点所在。人无完人，世界之大，青出于蓝而胜于蓝的大有人在。所以，我遇到的困难并没有什么，关键在于我自己的心态，以及找到合适的方法去解决困难才是最重要的。总而言之，这次课程设计让我收获颇多。6 附录#include#includeintmSIZE;intpSIZE;staticintmemery10=0;staticintpage100=0;stati

14、cinttemp10010=0;voidFIFO();voidLRR();voidOPT();voidLFR();voidNUR();voidprint(unsignedintt);voiddownload();voidmDelay(unsignedintDelay);voidmain()inti,k,code;/designBy();printf("请按任意键进行初始化操作.printf("请输入");getchar();system("cls");printf("请输入物理块的个数(Mn");scanf("%d

15、",&mSIZE);printf("请输入页面号引用串的个数(Pputs("请依次输入页面号引用串(连续输入，无需隔开)：");for(i=0;iscanf("%1d",&pagei);download();system("cls");system("color0E");doputs("输入的页面号引用串为：");for(k=0;kprintf("%dn",pagei);elseprintf("%d",pagei);pr

16、intf(''* *n");最近printf("*请选择页面置换算法：printf("*1.先进先出(FIFO)printf("*2.最少使用(LRR)printf("*3.最佳淘汰(OPT)printf("*4.最少访问页面(LFR)printf("*5.最近最不经常使用(NUR)printf("*6.退出printf(* *n");printf("请选择操作：bb");*n");*n");*n");*n");*n")

17、;*n");*n");scanf("%d",&code);switch(code)case1:FIFO();getchar();break;case2:LRR();getchar();break;case3:OPT();getchar();break;case 4:LFR();getchar();break;case 5:NUR();getchar();break;case6:system("cls");system("color0A");printf("感谢您使用页面置换算法软件(庹雷制作)n&

18、quot;);exit(0);default:for(j=0;jprintf("输入错误，请重新输入：");printf("按任意键重新选择：>");getchar();system("cls");while(code!=4);getchar();voiddownload()inti;system("color0D");printf("请等待.n");printf("正在下载中.n");printf("for(i=0;iprintf("b"

19、);for(i=0;i");printf("nFinish.n请按任意键进入置换算法选择界面：>");getchar();voidmDelay(unsignedintDelay)unsignedinti;for(;Delay>0;Delay-)完成");for(i=0;iprintf("b");voidprint(unsignedintt)inti,j,k,l;intflag;for(k=0;kfor(i=20*k;(ifor(i=mSIZE+20*k;(iif(i+1)%20=0)|(i+1)%20)&&

20、(i=pSIZE-1)printf("%dn",pagei);elseprintf("%d",pagei);if(i>=j)printf("|%d|",tempij);elseprintf("|");for(flag=0,l=0;lvoidcompute()inti;printf("请等待计算结果：");for(i=1;ielseprintf(">");for(i=0;i+for(i=0;i+for(i=0;i+voidFIFO()memerymax=pagei;

21、inttime10=0;inti,j,k,m;intmax=0;intcount=0;for(i=0;imemeryi=pagei;timei=i;for(j=0;jtempij=memeryj;for(i=mSIZE;ifor(j=0,k=0;jif(memeryj!=pagei)k+;if(k=mSIZE)count+;max=time0for(m=2;mmax=m;timemax=i;for(j=0;jtempij=memeryj;elsefor(j=0;jtempij=memeryj;compute();print(count);voidLRR()intmemery10=0;intfl

22、ag10=0;inti,j,k,m;intmax=0;intcount=0;for(i=0;imemeryi=pagei;flagi=i;tempij=memeryj;tempij=memeryj;for(i=mSIZE;ifor(j=0,k=0;jif(memeryj!=pagei)k+;elseflagj=i;if(k=mSIZE)count+;max=flag0for(m=2;mmemerymax=pagei;flagmax=i;for(j=0;jtempij=memeryj;elsecompute();voidOPT()intmemery10=0;intnext10=0;inti,j,k,l,m;intmax;intcount=0;for(i=0;imemeryi=pagei;for(j=0;jtempij=memeryj;for(i=mSIZE;ifor(j=0,k=0;jif(memeryj!=pagei)k+;if(k=mSIZE)count+;for(m=0;mbreak;nextm=l;max=next0>=next1?0:1;fo