页面置换-操作系统实验报告

实验二页面置换算法实现一、实验目的（1）了解内存分页管理策略（2）掌握调页策略（3）掌握一般常用的调度算法（4）学会各种存储分配算法的实现方法。（5）了解页面大小和内存实际容量对命中率的影响。二、实验内容采用页式分配存储方案，通过分别计算不同算法的命中率来比较算法的优劣，同时也考虑页面大小及内存实际容量对命中率的影响，设计一个虚拟存储区和内存工作区，并使用下述算法来模拟实现页面的置换：1.先进先出的算法（FIFO）2.最近最久未使用算法（LRU）3.最佳置换算法（OPT）实验分析在进程运行过程中，若其所访问的页面不存在内存而需要把它们调入内存，但内存已无空闲时，为了保证该进程能够正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中。但应调出哪个页面，需根据一定的算法来确定，算法的好坏，直接影响到系统的性能。一个好的页面置换算法，应该有较低的页面更换频率。2.1先进先出（FIFO）页面置换算法当需要访问一个新的页面时，首先查看物理块中是否就有这个页面，若要查看的页面物理块中就有，则直接显示，不需要替换页面；如果要查看的页面物理块中没有，就需要寻找空闲物理块放入，若存在有空闲物理块，则将页面放入；若没有空闲物理块，则替换页面。并将物理块中所有页面timer++。2.2最近久未使用(LRU)置换算法的思路最近久未使用置换算法的替换规则，是根据页面调入内存后的使用情况来进行决策的。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间，当需淘汰一个页面的时候选择现有页面中其时间值最大的进行淘汰。2.3最佳（OPT）置换算法的思路其所选择的被淘汰的页面，是以后不使用的，或者是在未来时间内不再被访问的页面，采用最佳算法，通常可保证获得最低的缺页率。三、实验流程3.1系统功能图图3-1系统功能图3.2算法流程图1）先进先出（FIFO）页面置换算法流程图图3-2先进先出页面置换算法流程图2）最近久未使用(LRU)置换算法图3-3最近久未使用置换算法流程图3）最佳（OPT）置换算法图3-4最佳置换算法流程图四、源程序#includeiostream.h#includestdlib.h#includetime.h#includestdio.h#defineL20//页面长度最大为20intM;//内存块structPro//定义一个结构体{intnum,time;};Input(intm,Prop[L])//打印页面走向状态{cout请输入页面长度(10～20)：;do{cinm;if(m20||m10){coutendl;cout页面长度必须在10～20之间endlendl;cout请重新输入L：;}elsebreak;}while(1);inti,j;j=time(NULL);//取时钟时间srand(j);//以时钟时间j为种子，初始化随机数发生器coutendl;cout输出随机数:endl;coutendl;for(i=0;im;i++){p[i].num=rand()%10;//产生0到9之间的随机数放到数组p中p[i].time=0;coutp[i].num;}coutendlendl;returnm;}voidprint(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;//当前页面再次被访问时循环结束elsecount++;//否则count+1}returncount;//返回count的值}intmain(){intc;intm=0,t=0;floatn=0;Prop[L];m=Input(m,p);//调用input函数，返回m值cout请输入分配的物理块m(2～6):;coutendlendl;do{cinM;if(M6||M2){coutendl;cout物理块m必须在2～6之间endlendl;cout请重新输入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;coutendl;cout1:FIFO页面置换2:LRU页面置换endl;cout3:OPT页面置换4:退出endl;cout请选择页面置换算法：endl;cinc;if(c==1)//FIFO页面置换{n=0;coutFIFO算法页面置换情况如下:endl;coutendl;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++;//指向下一个页面}}}coutendl;cout缺页次数：n缺页率：n/mendlendl;}if(c==2)//LRU页面置换{n=0;coutLRU算法页面置换情况如下:endl;coutendl;while(im){inta;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++;}coutendl;cout缺页次数：n缺页率：n/mendlendl;}if(c==3)//OPT页面置换{n=0;coutOPT算法置换情况如下:endl;coutendl;while(im){if(Search(p[i].num,page)=0)//如果已在内存块中{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;}//把找到的块号赋给spage[s].num=p[i].num;n++;coutp[i].num;print(page);i++;}}}coutendl;cout缺页次数：n缺页率：n/mendlendl;}if(c==4)break;}while(c==1||c==2||c==3);return0;}五、实验结果5.1程序主界面运行程序后，将会提示用户输入页面长度，长度在10到20之间。当用户输入长度（以12为例）后，系统将会显示随机数。系统提示用户输入分配的物理块，用户输入数据（以3为例）。程序主界面运行图如图5-1所示。图5-1程序主界面5.2先进先出(FIFO)页面置换算法运行结果选择算法1之后，进入算法1的操作。系统会显示算法的页面置换情况。先来先服务算法的运行图如图5-2所示。图5-2先进先出页面置换算法运行结果图5.3最近久未使用(LRU)置换算法运行结果选择算法2之后，进入算法2的操作。系统会显示算法的页面置换情况。最近久未使用的运行图如图5-3所示。图5-3最近久未使用置换算法运行结果图4）最佳（OPT）置换算法运行结果选择算法3之后，进入算法3的操作。系统会显示算法的页面置换情况。最近久未使用的运行图如图5-4所示。图5-4最佳置换算法运行结果图四、总结通过本次实验，我对页面置换算法的了解更加的深刻。页面置换算法主要有以下置换算法：OPT（最佳置换算法）、FIFO（先进先出置换算法）、LRU（最近最久未使用算法）。在进程运行过程中，若其访问的页面不在内存而需把它们调入内存，但内存以无空闲空间时，为了保证该进程能正常的运行，系统必须从内存中调出一页程序或数据送磁盘的兑换区中，但应将哪个页面调出，需根据一定的算法来确定。