(流程图)页面置换算法课程设计

1操作系统课程设计报告题目：页面置换算法模拟程序学院名称:专业班级：学生姓名：指导教师：成绩：2目录一、设计目的………………………………………………………3二、设计题目…………………………………………………………32.1设计内容………………………………………………………………………32.2设计要求………………………………………………………………………3三、设计过程…………………………………………………………43.1FIFO（先进先出）……………………………………………………………43.2LRU（最近最久未使用）………………………………………………………53.3OPT（最佳置换算法）…………………………………………………………63.4随机数发生器……………………………………………………………………7四、完整代码……………………………………………………………7五、运行结果演示………………………………………………………13六、设计心得……………………………………………………………16七、参考文献……………………………………………………………163一、设计目的操作系统是计算机教学中最重要的环节之一，也是计算机专业学生的一门重要的专业课程。操作系统质量的好坏，直接影响整个计算机系统的性能和用户对计算机的使用。一个精心设计的操作系统能极大地扩充计算机系统的功能，充分发挥系统中各种设备的使用效率，提高系统工作的可靠性。由于操作系统涉及计算机系统中各种软硬件资源的管理，内容比较繁琐，具有很强的实践性。要学好这门课程，必须把理论与实践紧密结合，才能取得较好的学习效果。本课程设计是学生学习完《计算机操作系统》课程后，进行的一次全面的综合训练，通过课程设计，让学生更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。熟悉页面置换算法及其实现，引入计算机系统性能评价方法的概念。二、设计题目：页面置换算法模拟程序2.1设计内容编制页面置换算法的模拟程序。2.2设计要求1).用随机数方法产生页面走向，页面走向长度为L(15=L=20),L由控制台输入。2).根据页面走向，分别采用Optinal、FIFO、LRU算法进行页面置换，统计缺页率。3).假定可用内存块为m(3=m=5)，m由控制台输入，初始时，作业页面都不在内存。4).要求写出一份详细的设计报告。课程设计报告内容包括：设计目的、设计内容、设计原理、算法实现、流程图、源程序、运行示例及结果分析、心得体会、参考资料等。4三．设计过程3.1FIFO（先进先出）设计原理：需要进行页面置换，即把内存中装入最早的那个页面淘汰，换入当前的页面。算法流程图：开始页面走向存入数组p[]中，内存块用page[]表示初始化为0当前p[]中第i个元素是否已在内存中Page[]是否有空把page[]中最先装入的页面置换出去.i++把p[i]的内容直接装入最上面一个空内存块，i++输出当前内存块状态NNYYi++53.2LRU（最近最久未使用）设计原理：当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。该算法的主要出发点是，如果某页被访问了，则它可能马上还要被访问。或者反过来说，如果某页很长时间未被访问，则它在最近一段时间也不会被访问。算法流程图：结束开始页面走向存入数组p[]中，内存块用page[]表示初始化为0当前p[]中第i个元素是否已在内存Page[]是否有空把p[i]的内容直接装入最上面一个空内存块，i++把page[]中最近最久未使用的页面置换出去.i++i++输出当前内存块状态结束NNYY63.3OPT（最佳置换算法）设计原理：需要进行页面置换，把内存中以后一段时间都不使用或是使用时间离现在最远的页面换出。流程图开始页面走向存入数组p[]中，内存块用page[]表示初始化为0当前p[]中第i个元素是否已在内存Page[]是否有空把p[i]的内容直接装入最上面一个空内存块，i++把page[]中以后一段时间都不使用或是使用时间离现在最远的换出.i++输出当前内存块状态结束NNi++YY73.4随机数发生器#includestdlib.h#includetime.h//准备用时钟函数调用库函数t=time(NULL);//取时钟时间并存入t调用库函数srand(t);//用时间t初始化随机数发生器调用库函数x=rand()%10+1;//返回一个1~10之间的随机数四．完整代码#includeiostream.h#includestdlib.h#includetime.h#includestdio.h#defineL20//页面走向长度最大为20intM;//内存块structPro//定义一个结构体{intnum,time;};Input(intm,Prop[L])//打印页面走向状态{cout请输入实际页面走向长度L(15=L=20)：;do{cinm;if(m20||m15)cout实际页面长度须在15～20之间;请重新输入L：;elsebreak;}while(1);inti,j;j=time(NULL);//取时钟时间srand(j);//以时钟时间x为种子，初始化随机数发生器cout输出随机数:;for(i=0;im;i++){p[i].num=rand()%10+1;//产生1到10之间的随即数放到数组p中p[i].time=0;coutp[i].num;}coutendl;returnm;}8voidprint(Pro*page1)//打印当前的页面{Pro*page=newPro[M];page=page1;for(inti=0;iM;i++)coutpage[i].num;coutendl;}intSearch(inte,Pro*page1)//寻找内存块中与e相同的块号{Pro*page=newPro[M];page=page1;for(inti=0;iM;i++)if(e==page[i].num)returni;//返回i值return-1;}intMax(Pro*page1)//寻找最近最长未使用的页面{Pro*page=newPro[M];page=page1;inte=page[0].time,i=0;while(iM)//找出离现在时间最长的页面{if(epage[i].time)e=page[i].time;i++;}for(i=0;iM;i++)if(e==page[i].time)returni;//找到离现在时间最长的页面返回其块号return-1;}intCount(Pro*page1,inti,intt,Prop[L])//记录当前内存块中页面离下次使用间隔长度{Pro*page=newPro[M];page=page1;intcount=0;for(intj=i;jL;j++){if(page[t].num==p[j].num)break;//当前页面再次被访问时循环结束9elsecount++;//否则count+1}returncount;//返回count的值}intmain(){intc;intm=0,t=0;floatn=0;Prop[L];m=Input(m,p);//调用input函数，返回m值cout请输入可用内存页面数m(3～5):;do{cinM;if(M5||M3)cout内存块m须在3～5之间，请重新输入m：;elsebreak;}while(1);Pro*page=newPro[M];do{for(inti=0;iM;i++)//初试化页面基本情况{page[i].num=0;page[i].time=m-1-i;}i=0;cout1:FIFO页面置换endl;cout2:LRU页面置换endl;cout3:OPT页面置换endl;cout按其它键结束程序；endl;cinc;if(c==1)//FIFO页面置换{n=0;cout******************************************endl;10coutendl;coutFIFO算法页面置换情况如下:endl;coutendl;cout******************************************endl;while(im){if(Search(p[i].num,page)=0)//当前页面在内存中{coutp[i].num;//输出当前页p[i].numcout不缺页endl;i++;//i加1}else//当前页不在内存中{if(t==M)t=0;else{n++;//缺页次数加1page[t].num=p[i].num;//把当前页面放入内存中coutp[i].num;print(page);//打印当前页面t++;//下一个内存块i++;//指向下一个页面}}}cout缺页次数：n缺页率：n/mendl;}if(c==2)//LRU页面置换{n=0;cout******************************************endl;coutendl;coutLRU算法页面置换情况如下:endl;coutendl;cout******************************************endl;while(im){11inta;t=Search(p[i].num,page);if(t=0)//如果已在内存块中{page[t].time=0;//把与它相同的内存块的时间置0for(a=0;aM;a++)if(a!=t)page[a].time++;//其它的时间加1coutp[i].num;cout不缺页endl;}else//如果不在内存块中{n++;//缺页次数加1t=Max(page);//返回最近最久未使用的块号赋值给tpage[t].num=p[i].num;//进行替换page[t].time=0;//替换后时间置为0coutp[i].num;print(page);for(a=0;aM;a++)if(a!=t)page[a].time++;//其它的时间加1}i++;}cout缺页次数：n缺页率：n/mendl;}if(c==3)//OPT页面置换{n=0;cout******************************************endl;coutendl;coutOPT算法置换情况如下:endl;coutendl;cout******************************************endl;while(im){if(Search(p[i].num,page)=0)//如果已在内存块中12{coutp[i].num;cout不缺页endl;i++;}else//如果不在内存块中{inta=0;for(t=0;tM;t++)if(page[t].num==0)a++;//记录空的内存块数if(a!=0)//有空内存块{intq=M;for(t=0;tM;t++)if(page[t].num==0&&qt)q=t;//把空内存块中块号最小的找出来page[q].num=p[i].num;n++;coutp[i].num;print(page);i++;}else{inttemp=0,s;for(t=0;tM;t++)//寻找内存块中下次使用离现在最久的页面if(tempCount(page,i,t,p)){temp=Count(page,i,t,p);s=t;}//把找到的块号赋给spa