还剩18页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
计算机科学与技术学院操作系统课程设计报告课题模拟页式存储管理评阅意见评定成绩指导老师签名年月日目录TOC\o1-2\h\z\u
一、目的和要求
21、设计目的
22、设计要求2
二、设计思路及过程
21、概要设计
22、过程设计3
三、数据定义5
四、核心代码5
五、运行截图8
六、小结10
七、参考文献11附录12
一、目的和要求
1、设计目的通过请求页式存储管理中页面置换算法模拟设计,了解虚拟存储技术的特点,掌握请求页式存储管理的页面置换算法
2、设计要求根据模拟的页式管理设计,掌握在页式存储管理中最基本的三种页面调度算法FIFO、LRU以及OPT但在三种算法中均要求在调度程序中产生的页面序列是随机产生的,而不是人为的输入,在执行时只需改变页面的大小及内存容量就可以得到不同的页面序列,另外还需要说明随机的性能和其性能可能对算法的影响,并对随机性要有一定的参数控制能力此外,计算并输出FIFO、LRU以及OPT算法在不同内存容量下的命中率根据方法的执行过程,编写一个解决上述问题的程序,显示访问每个值页面中的值具体参数访问串的长度,访问串,页面个数分别用3种不同的方法实现页面的置换,并输出相关信息
二、设计思路及过程
1、概要设计
1.1问题概述根据三种不同的置换算法,依据其不同的算法方式,分别计算该算法在不同情况下的命中率,并显示各页面的变化情况
1.2内容分析对于该课程设计中模拟的页式存储管理的页面置换过程,只要掌握其中最基本的三种算法,包括FIFO、LRU及OPT但最重要的一点就是要求产生随机序列,所以在编写程序时要采用控制产生随机值的种子数函数,如此能产生随机的访问序列另外,不能在执行完一次操作后就只能进行另外一种算法的操作,必须还要有更加详细的操作,比如是否要重新得到新序列?还是要不改变访问序列而只改变访问串的内存容量?抑或是不操作就退出该算法以进行下一种调度算法?因此,在执行完每次操作后都必须要有提示语,看是否进入更细节的操作,还是退出本次算法的操作以进入下一种算法的调度
2、过程设计
2.1模块设计在下图的主模块设计图中,只注重描绘了页式存储管理的三种主要算法,未描绘出细节部分其中,在执行每种算法时都会要求输入你所需要的访问串长度、随机值以及同一种算法的不同内存容量,如此就可以得出不同的命中率另外,在执行完该操作后又会出现三条提示语,是重新得到新序列?还是不改变访问序列只改变访问串的内存容量?抑或是不操作退出以进行下一种调度算法?这些在下图中都未一一实现图
2.1页式存储管理的主模块设计图
2.2算法原理分析要学成功实现算法,首先要知道各个方法是怎么做的,即原理是怎样的,下面是三种算法的原理FIFO算法是先进先出,当当前内存中没有正要访问的页面时,置换出最先进来的页面LRU算法是最近最久未使用,当当前内存中没有正要访问的页面时,置换出在当前页面中最近最久没有使用的页面OPT算法是未来最远出现,当当前内存中没有正要访问的页面时,置换出当前页面中在未来的访问页中再也不出现的页面或最远出现的页面
2.3程序流程图本次课程设计的主要流程是3种置换算法的流程图,我负责opt算法的流程图,流程图如下所示图
2.2opt算法流程图
三、数据定义intlengthnum_pagecountseed;//length记录访问串的长度,num_page页面数,count记录缺页次数intresult
[20]
[30]order
[30]a
[10];//result记录结果order存储访问串a存储当前页面中的值intpos1flag1flag2;//pos1位置变量,flag1等为标志变量charresult1
[30];//记录缺页数组
四、核心代码三种置换算法中只列出我负责部分(opt算法),具体代码及注释如下voidopt//理想型{intipos
[10]flag
[10];while1{count=0;flag1=flag2=0;fori=0;ilength;i++{if!searchorder[i]{count++;result1[i]=*;ifa[num_page-1]!=-1//表示当前页面已满要淘汰一个{memsetpos-1sizeofpos;memsetflag0sizeofflag;intjk;forj=i;jlength;j++//找出当前页中的值在将来访问串中对应的最近位置{fork=0;knum_page;k++{iforder[j]==a[k]flag[k]==0{pos[k]=j;flag[k]=1;}}}coutendl;intmax=-10max_pos;fork=0;knum_page;k++//找出位置最远的那个值{ifpos[k]==-1//未出现则跳出,替换该值{max_pos=k;break;}elseifmaxpos[k]{max=pos[k];max_pos=k;}}a[max_pos]=order[i];}else//还有空页{forintj=0;jnum_page;j++{ifa[j]==-1{a[j]=order[i];break;}}}}elseresult1[i]=;forintj=0;jnum_page;j++{result[j][i]=a[j];}}again;//再操作ifflag1==0flag2==0break;}}其中的查询函数search()具体代码如下:boolsearchintn//查找当前内存中是否已存在该页{inti;fori=0;inum_page;i++{ifa[i]==nreturntrue;}returnfalse;}其中的再操作函数again(),具体代码如下voidagain//用于再输入{print;intnumpagem;printf**************************************\n;printf
1.重新输入新序列.\n;printf
2.不改变访问序列只改变页面数.\n;printf
0.不操作退出.\n;printf**************************************\n;printf选择所要操作:;scanf%dm;ifm==1{flag1=1;//重新输入init;}elseifm==2{flag2=1;cout输入新页面数;cinnumpage;num_page=numpage;memseta-1sizeofa;}elsereturn;
五、运行截图主菜单根据不同的分工,限于纸张只列出部分截图,以下是对opt调度算法的实验截图图
5.1相同的内存容量下不同的访问串序列1图
5.2相同的内存容量下不同的访问串序列2依上图
5.1和
5.2来看,opt调度算法在访问串长度一致,随机值不同以致产生不同的访问串序列时,但页面数不相同的情况下,所得到的命中率也不同图
5.3 不同的内存容量下相同的访问串序列在上图
5.3中就是对同一访问串序列进行opt调度,只是改变其页面的大小,得到了不同的命中率
六、小结本次课程设计目的是通过请求页式管理中页面置换算法模拟设计,了解虚拟存储技术的特点,掌握请求页式存储管理的页面置换算法要求设计随机页面产生程序,并说明随机的性能和其性能可能对算法的影响,对随机性要有一定的参数控制能力;计算并输出FIFO及LRUOPT算法在不同内存容量下的命中率由于上学期做过页面置换的实验,内容包括先进先出算法(FIFO)、最近最久未使用页面置换算法(LRU)和理想淘汰算法(OPT),3种算法思想简单明确,选好数据结构,思路清晰便基本没问题了所以相对来说,这次操作系统的课程设计容易许多,只是在之前实验基础上,要附加设计随机页面产生程序,对随机性要有一定的参数控制能力对于随机页面产生程序,我们之前没做过,在网上查阅资料,使用了库函数srand()和rand(),实现了简单的随机页面产生程序,功能基本完成我们知识所限,没有使用漂亮可视化界面编程实现功能,用简单的C语言编程实现的不管怎么样,最终还是实现的本次课程设计要求的做了这么多次课程设计了,大致的过程都熟悉了,每次的动手实践,调动了我们主动学习的积极性并引导我们根据实际编程要求训练自己实际分析问题的能力及编程能力并养成良好的编程习惯通过详细的实例循序渐进地启发我们完成设计课程设计将要求从拿到题目到完成整个编程,从理论到实践可以学到很多很多的东西,同时不仅可以巩固了以前所学过的知识,而且学到了很多在书本上所没有学到过的知识通过这次课程设计使我懂得了理论与实际相结合是很重要的,只有理论知识是远远不够的,只有把所学的理论知识与实践相结合起来,从理论中得出结论,才能真正为社会服务,从而提高自己的实际动手能力和独立思考的能力知识的获得是无止境的,只要你想学,只要你行动,就一定会有所收获的回首这两个星期的课程设计,尽管很是头痛,很多都不会,但经过努力,我们还是学了不少知识的这期间,老师给了我们许多帮助,非常感谢!
七、参考文献【1】张尧学史美林.计算机操作系统教程第2版习题解答与实验指导.北京:清华大学出版社2000【2】谭浩强张基温.C语言程序设计教程.高等教育出版社1991【3】张尧学史美林.计算机操作系统教程第2版.北京:清华大学出版社2000附录所有源程序代码如下#includeiostream#includestdlib.husingnamespacestd;intlengthnum_pagecountseed;intresult
[20]
[30]order
[30]a
[10];intpos1flag1flag2;charresult1
[30];voidinit{memseta-1sizeofa;inti;cout输入访问串的长度:;cinlength;cout输入种子数控制产生的随机值;cinseed;srandseed;cout产生的随机访问串:;fori=0;ilength;i++{//cinorder[i];order[i]=rand%10;coutorder[i];}coutendl;cout输入页面的个数;cinnum_page;}voidprint{intij;cout*表示缺页endl;coutendl;forj=0;jlength;j++printf%2dorder[j];coutendl;fori=0;inum_page;i++{forj=0;jlength;j++{ifresult[i][j]==-1{printf;}elseprintf%2dresult[i][j];}coutendl;}forj=0;jlength;j++{printf%2cresult1[j];}coutendl;cout命中率length-count/length;printf=%.1lflength*
1.0-count*
1.0/length*
1.0*100;cout%endl;}boolsearchintn//查找当期内存是否已存在{inti;fori=0;inum_page;i++{ifa[i]==nreturntrue;}returnfalse;}voidagain//用于再输入{print;intnumpagem;printf**************************************\n;printf
1.重新输入新序列.\n;printf
2.不改变访问序列只改变页面数.\n;printf
0.不操作退出.\n;printf**************************************\n;printf选择所要操作:;scanf%dm;ifm==1{flag1=1;//重新输入init;}elseifm==2{flag2=1;cout输入新页面数;cinnumpage;num_page=numpage;memseta-1sizeofa;}elsereturn;}voidfifo//先进先出{intithisn=0;while1{count=0;flag1=flag2=0;fori=pos1;ilength;i++{if!searchorder[i]{count++;result1[i]=*;ifa[num_page-1]!=-1//表示当前页面已满要淘汰一个{a[thisn]=order[i];thisn++;ifthisn=num_pagethisn=0;}else{forintj=0;jnum_page;j++{ifa[j]==-1{a[j]=order[i];break;}}}}elseresult1[i]=;forintj=0;jnum_page;j++{result[j][i]=a[j];}}again;//再操作ifflag1==0flag2==0break;}}voidlru//最久最近没使用{intipos
[10];while1{count=0;flag1=flag2=0;memsetpos-1sizeofpos;fori=pos1;ilength;i++{if!searchorder[i]{count++;result1[i]=*;ifa[num_page-1]!=-1//表示当前页面已满要淘汰一个{intjk;forj=0;ji;j++//查找当前页中的值对应的最近位置{fork=0;knum_page;k++{iforder[j]==a[k]{pos[k]=j;}}}intmin=pos
[0]min_pos=0;fork=1;knum_page;k++//找出位置最远的那个{ifminpos[k]{min=pos[k];min_pos=k;}}a[min_pos]=order[i];}else//还有空页{forintj=0;jnum_page;j++{ifa[j]==-1{a[j]=order[i];break;}}}}elseresult1[i]=;forintj=0;jnum_page;j++{result[j][i]=a[j];}}again;//再操作ifflag1==0flag2==0break;}}voidopt//理想型{intipos
[10]flag
[10];while1{count=0;flag1=flag2=0;fori=0;ilength;i++{if!searchorder[i]{count++;result1[i]=*;ifa[num_page-1]!=-1//表示当前页面已满要淘汰一个{memsetpos-1sizeofpos;memsetflag0sizeofflag;intjk;forj=i;jlength;j++//找出当前页中的值在将来访问串中对应的最近位置{fork=0;knum_page;k++{iforder[j]==a[k]flag[k]==0{pos[k]=j;flag[k]=1;}}}coutendl;intmax=-10max_pos;fork=0;knum_page;k++//找出位置最远的那个值{ifpos[k]==-1//未出现则跳出,替换该值{max_pos=k;break;}elseifmaxpos[k]{max=pos[k];max_pos=k;}}a[max_pos]=order[i];}else//还有空页{forintj=0;jnum_page;j++{ifa[j]==-1{a[j]=order[i];break;}}}}elseresult1[i]=;forintj=0;jnum_page;j++{result[j][i]=a[j];}}again;//再操作ifflag1==0flag2==0break;}}voidmune{intm;printf\n**************************************\n\n;printf动态分配分区方法演示\n;printf\n**************************************\n\n;printf
1.先进先出算法.\n\n;printf
2.最久最近未使用页面置换算法.\n\n;printf
3.理想型淘汰算法.\n\n;printf
0.退出程序.\n;printf\n**************************************\n;printf\n选择所要操作:;scanf%dm;switchm{case1:init;fifo;mune;break;case2:init;lru;mune;break;case3:init;opt;mune;break;case0:break;default:printf选择错误重新选择.;mune;}}voidmain//主函数{mune;}页式存储管理先进先出算法fifo最近最久未使用算法lru理想型淘汰算法opt输入内存中分配页数据第一个访问页初始化第一列值直接复制前一列内容内存中是否已存在?开始还有请求访问页?内存有空页?替换内存中将来不出现或离当前最远的页直接插入结束。