操作系统课程设计报告书-设计一个虚拟存储区和内存工作区.doc

课程设计任务书学生姓名： 专业班级： 计网2093班 指导教师： 工作单位： 信息工程系 设计题目：设计一个虚拟存储区和内存工作区初始条件：linux操作系统，gcc编译环境要求完成的主要任务 主要任务：通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。1、 最佳淘汰算法（opt） 2、先进先出的算法（fifo） 3、最近最久未使用算法（lru）设计程序时先用srand()和rand()函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。设计报告撰写格式要求：1设计题目与要求 2 设计思想 3系统结构 4 数据结构的说明和模块的算法流程图 5 使用说明书（即用户手册）：内容包含如何登录、退出、读、写等操作说明6 运行结果和结果分析（其中包括实验的检查结果、程序的运行情况）7 自我评价与总结8 附录：程序清单，注意加注释（包括关键字、方法、变量等），在每个模块前加注释； 时间安排 6月 20日 布置课程设计任务；分配题目后，查阅资料、 准备程序； 6月 21 6月23 日上机调试程序、书写课程设计报告；6月24 日 提交课程设计报告及相关文档。指 导 教 师 签 名： 2011年 6月 18日系 主 任 签 名： 2011年6月 19日课程设计报告书一设计题目：设计一个虚拟存储区和内存工作区二设计要求： 1、设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。 最佳淘汰算法（opt） 先进先出的算法（fifo） 最近最久未使用算法（lru）设计程序时先用srand()和rand()函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。 2、所编辑的程序能够在linux系统中gcc环境下正常运行。三设计思想：先建立三种算法的基本结构，再在主程序中调用，并实现其功能。1、 最近最久未使用（lru）置换算法的思路 最近最久未使用置换算法的实质是当需要置换一页时，选择最长时间未被使用的那一页淘汰。为了能检测出那一页长时间未被使用我们可以设置一个计数器oldest2()，把每一次放入固定内存内的序列数做一个统计，通过选择将计数最少的数淘汰出去。2、 最佳淘汰（opt）置换算法的思路 最佳算法是当调入一新页而必须先淘汰一旧页，所淘汰的那一页应是以后不再使用的，或者是在最长时间段之后才会用到的页。这就需要我们先要知道所要放入页的内容，然后逐一判断那些页应该在放入内存后可以被淘汰。这个我用oldest()这个函数实现这一筛选功能，先用两个循环对内存中的数与随机序列对比，看有没有相等的数，然后利用计数器oldest2()返回未来最长时间不使用的页面位置。3、 先进先出（fifo）置换算法的思路 先进先出算法实际上是选择在主存中居留最久的一页淘汰，即先进入主存的页。可以利用一个查询函数isinbuf()来判断所要置换的页面与内存中的页面是否有重复，重复不置换，不重复就利用一个赋值语句将旧页置换出来，这里最重要的是页号的操作，可以利用一个控制语句old=(old+1)%(int)b来进行页面的转换。最佳淘汰算法（opt）模块先进先出的算法（fifo）模块最近最久未使用算法（lru）模块四系统结构： 主程序模块使用最近最久未使用算法（lru）的命中率使用最佳淘汰算法（opt）的命中率 使用先进先出的算法（fifo）的命中率程序系统结构图 五数据结构的说明和模块的算法流程图1.数据结构的说明 作业的页面走向（执行过程中对页面的访问顺序）用数组，页面走向的长度控制以-1为终结符。 页框（作业分得的物理块）在不同置换算法执行之前长度由不同的置换算法其数据结构不同但原则式尽可能使程序的时间复杂度最低。fifo，采用队列，对于lru堆栈。2.模块的算法流程图 2.1 fifo算法的流程开始 中断页数change=0；循环控变量i=0；利用循环将buf中的值全置-1（过程略）；真假判断bufold=-1输出空字符判断in输出置换页bufold判断是否置换标志： j=-1将新的序列装入内存中bufold=listi重置置换标志：old=(old+1)%(int)b真假中断次数change+;i+;真输出空字符;i+;假j=isinbuf(buf,listi;结束输出算法命中率:1-(float)change/39;图2.2 lru算法的流程图开始 中断页数change=0；循环控变量i=0；利用循环将buf中的值全置-1（过程略）；判断inj=isinbuf(buf,listi;确定置换页:old=oldest2(f);判断是否置换标志： j=-1输出置换页bufold将新的序列装入内存中bufold=listi将内存固定序列数计数数组清零：fold=0;中断次数change+;i+;将位置换内存技术数组清零：fj=0;输出空字符;i+;输出算法命中率:1-(float)change/39;结束真真假假2.3opt算法的流程图开始 中断页数change=0；循环控变量i=0；利用循环将buf中的值全置-1（过程略）；判断inj=isinbuf(buf,listi;判断是否置换标志： j=-1求出要置换的位置：old=oldest(list,buf,f,i);输出置换页bufold将新的序列装入内存中bufold=listi将内存固定序列数计数数组清零：fold=0;中断次数change+;i+;输出空字符;i+;输出算法命中率:1-(float)change/39;结束真真假假六使用说明：1.登录linux系统的终端使用一下指令1. 1 cd 目录名（进入你存程序的文件夹）1.2 gedit 文件名 &（打开linux系统内置的编译器并把文件导入文本区）1.3回到终端输入gcc 文件名（编译源程序）1.4再次输入./a.out(运行源程序并得出结果）1.5得出结果键入exit(退出所有操作）2. 使用microsoft visual c+ 6.0编译运行2.1直接将编好的文件导入到编译器中2.2 如图按钮执行编译运行操作2.3退出直接关闭编译器即可七运行结果及分析1运行结果1.1 fifo算法与lru算法命中率一样的情况1.2 fifo算法命中率最低的情况1.3 fifo算法比lru算法命中率高的情况2.运行结果分析 三种结果告诉我们opt算法的命中率最高，淘汰页面最少，而fifo算法和lru算法在不同的情况下略有不同，但是淘汰的页面却有很大不同。在理论上来说，lru算法优于fifo算法。八自我评价与总结通过这次课程设计，不仅让我了解了页面置换算法，而且使我对操作系统这门课程有了更进一步的认识和了解，要想学好它要重在实践。在有充分的理论基础的情况下要通过不断的上级操作才能更好地学习它。在编好程序后，我一开始就一味的进行调试，急切的想侥幸调试出来，但由于没有进行深入的考虑，我调试了很久都没有成功，我仔细的分析题目，分析材料，在原有基础上我进行了改正，经过了一番努力，最后还是调试成功了。同时在编程阶段，我发现自己在逻辑思维的设计上还存在一定的缺陷，一些c语言的基础知识还未掌握到位，对于函数的形参与实参之间的转化还不是很清楚。虽然在学习课本知识的时候感觉老师讲起来很好懂，但是一旦要运用到实际当中却不知道怎么转换，出现了对知识结构的空洞状态。三种置换算法，特别是在fifo算法与lru算法的设计上出现了混乱状态，通过对运行结果的一次又一次的检查还有在老师的帮助下我才慢慢的洞察到自己到底哪里出现了问题，在设置置换标志与判断是否置换的条件设计上出现了考虑不周全的情况。在找空闲物理块的时候，起初我比较物理块是否等于，若为，则直接把页面放入，后来发现不论什么时候都是把替换出去，才恍然大悟，既然页面序列数有就不能用来表示空闲物理块，后来换成问题就解决了。总而言之，虽然程序不是很完美，但是付出了汗水，也收获了结果，今后对于此类问题的设计可以有一个很好的借鉴意义。希望能有下一次的实践机会，争取在程序设计的界面和逻辑上更加美观、自然。附录：程序清单#include #include#include#define n 39 /*随即数列的长度*/#define b 4 /*内存的页面数*/*-函数名： isinbuf()功 能：返回某个数x有没有在缓冲区buf中，若在，返回其位置；若不在，则返回-1-*/int isinbuf(int buf,int x) int i,j=-1; for(i=0;ib;i+) if(bufi=x) j=i;break; else if(bufi=-1) bufi=x;j=i;break; return j;/*-函数名：oldest()功 能：返回最近最久未使用的页面的位置-*/int oldest(int list,int buf,int f,int start) int i,j; for(i=0;ib;i+) for(j=start;jn;j+) if(bufi=listj) break; fi=j; return oldest2(f);/*-函数名：oldest2()功 能：返回未来最长时间不使用的页面的位置-*/int oldest2(int f) int i,j=0,max=-1; for(i=0;imax) max=fi;j=i; fi+; return j;/*-函数名：main()功 能：-*/main() int listn; int bufb,fb,i,j,k,max,min; int old=0; int change=0; printf(本程序假设内存为程序分配的内存块数是4!n); /*生成一系列随机数并初始化环境*/srand(int)time(null);for(i=0;ib;i+) bufi=fi=-1;printf(n产生的随机数列为:n);for(i=0;in;i+) listi=(int) rand()%10; /产生随机数列 printf(%2d,listi); printf(n); /*显示opt淘汰页面的序列*/printf(nopt淘汰页面的序列为：n);change=0;for(i=0;ib;i+) bufi=fi=-1;for(i=0;in;i+) j=isinbuf(buf,listi); if(j=-1) old=oldest(list,buf,f,i); printf(%2d,bufold); bufold=listi; fold=0; change+; else printf(); /*输出opt算法的命中率*/printf(nopt算法的命中率为:%fn,1-(float)change/39); /*显示fifo淘汰页面的序列*/printf(nfifo淘汰页面的序列为：n);change=0;for(i=0;ib;i+) bufi=-1;for(i=0;in;i+) j=isinbuf(buf,listi); if(j=-1) if(bufold=-1)printf(); else printf(%2d,bufold); bufold=listi; old=(old+1)%(int)b; change+; else printf();/*输出fifo算法的命中率*/printf(nfifo算法的命中率为:%fn,1-(float)change/39);/*显示lru淘汰页面的序列*/printf(nlru淘汰页面的序列为：n);change=0;for(i=0;ib;i+) bufi=fi=-1;for(i=0;in;i+) j=isinbuf(buf,listi); old=oldest2(f); if(j=-1) printf(%2d,bufold); bufold=listi; fold=0; change+; else fj=0; printf(); /*输出lru算法的命中率*/printf(nlru算法的命中率为:%fn,1-(float)change/39);设计过程中质疑（或答辩）记载：1. 页面置换算法最主要的有哪几种？答：主要有最佳算法（opt算法）、先进先出算法（