2024年面置换操作系统实验报告

试验二页面置换算法实现一、试验目标（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最近久未使用置换算法