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

...wd......wd......wd...实验二页面置换算法实现一、实验目的〔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算法流程图先进先出〔FIFO〕页面置换算法流程图图3-2先进先出页面置换算法流程图最近久未使用(LRU)置换算法图3-3最近久未使用置换算法流程图最正确〔OPT〕置换算法图3-4最正确置换算法流程图源程序#include<iostream.h>#include<stdlib.h>#include<time.h>#include<stdio.h>#defineL20//页面长度最大为20intM;//内存块structPro//定义一个构造体{intnum,time;};Input(intm,Prop[L])//打印页面走向状态{ cout<<"请输入页面长度(10～20)："; do { cin>>m; if(m>20||m<10) {cout<<endl; cout<<"页面长度必须在10～20之间"<<endl<<endl; cout<<"请重新输入L："; } elsebreak; }while(1); inti,j; j=time(NULL);//取时钟时间 srand(j);//以时钟时间j为种子，初始化随机数发生器 cout<<endl; cout<<"输出随机数:"<<endl; cout<<endl; for(i=0;i<m;i++) { p[i].num=rand()%10;//产生0到9之间的随机数放到数组p中 p[i].time=0; cout<<p[i].num<<""; } cout<<endl<<endl; returnm;}voidprint(Pro*page1)//打印当前的页面{ Pro*page=newPro[M]; page=page1; for(inti=0;i<M;i++) cout<<page[i].num<<""; cout<<endl;}intSearch(inte,Pro*page1)//寻找内存块中与e一样的块号{ Pro*page=newPro[M]; page=page1; for(inti=0;i<M;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(i<M)//找出离现在时间最长的页面 { if(e<page[i].time)e=page[i].time; i++; } for(i=0;i<M;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;j<L;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):"; cout<<endl<<endl; do{ cin>>M; if(M>6||M<2) {cout<<endl; cout<<"物理块m必须在2～6之间"<<endl<<endl; cout<<"请重新输入m：";} elsebreak; }while(1); Pro*page=newPro[M]; do{ for(inti=0;i<M;i++)//初始化页面根本情况 {page[i].num=0; page[i].time=m-1-i; } i=0; cout<<endl; cout<<"1:FIFO页面置换 2:LRU页面置换"<<endl; cout<<"3:OPT页面置换 4:退出"<<endl; cout<<"请选择页面置换算法："<<endl; cin>>c; if(c==1)//FIFO页面置换 { n=0; cout<<"FIFO算法页面置换情况如下:"<<endl; cout<<endl; while(i<m) { if(Search(p[i].num,page)>=0)//当前页面在内存中 { cout<<p[i].num<<"";//输出当前页p[i].num cout<<"不缺页"<<endl; i++;//i加1 } else//当前页不在内存中 { if(t==M)t=0; else { n++;//缺页次数加1 page[t].num=p[i].num;//把当前页面放入内存中 cout<<p[i].num<<""; print(page);//打印当前页面 t++;//下一个内存块 i++;//指向下一个页面 } } } cout<<endl; cout<<"缺页次数："<<n<<"缺页率："<<n/m<<endl<<endl; } if(c==2)//LRU页面置换 { n=0; cout<<"LRU算法页面置换情况如下:"<<endl; cout<<endl; while(i<m) { inta; t=Search(p[i].num,page); if(t>=0)//如果已在内存块中 {page[t].time=0;//把与它一样的内存块的时间置0 for(a=0;a<M;a++) if(a!=t)page[a].time++;//其它的时间加1 cout<<p[i].num<<""; cout<<"不缺页"<<endl; } else//如果不在内存块中 { n++;//缺页次数加1 t=Max(page);//返回最近最久未使用的块号赋值给t page[t].num=p[i].num;//进展替换 page[t].time=0;//替换后时间置为0 cout<<p[i].num<<""; print(page); for(a=0;a<M;a++) if(a!=t)page[a].time++;//其它的时间加1 } i++; } cout<<endl; cout<<"缺页次数："<<n<<"缺页率："<<n/m<<endl<<endl; } if(c==3)//OPT页面置换 { n=0; cout<<"OPT算法置换情况如下:"<<endl; cout<<endl; while(i<m) { if(Search(p[i].num,page)>=0)//如果已在内存块中 { cout<<p[i].num<<""; cout<<"不缺页"<<endl; i++; } else//如果不在内存块中 { inta=0; for(t=0;t<M;t++) if(page[t].num==0)a++;//记录空的内存块数 if(a!=0)//有空内存 { intq=M; for(t=0;t<M;t++) if(page[t].num==0&&q>t)q=t;//把空内存块中块号最小的找出来 page[q].num=p[i].num; n++; cout<<p[i].num<<""; print(page); i++; } else { inttemp=0,s; for(t=0;t<M;t++)//寻找内存块中下次使用离现在最久的页面 if(temp<Count(page,i,t,p)) { temp=Count(page,i,t,p); s=t;}//把找到的块号赋给s page[s].num=p[i].num; n++; cout<<p[i].num<<""; print(page); i++; } } } cout<<endl; cout<<"缺页次数："<<n<<"缺页率："<<n/m<<endl<<endl; } 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最近久未使