页面置换算法实验报告

《操作系统--页面置换算法》实验报告姓名：范学升学号：1001050903班级：电科10-1班专业：电子信息科学与技术一、实验目的1．通过模拟实现几种基本页面置换的算法，了解虚拟存储技术的特点。2．掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想，并至少用三种算法来模拟实现。3．通过对几种置换算法页面的比较，来对比他们的优缺点，并通过比较更换频率来对比它们的效率。二、实验内容：设计一个虚拟存储区和内存工作区，并使用下述算法来模拟实现页面的置换：1.先进先出的算法（FIFO）2.最近最久未使用算法（LRU）3.最佳置换算法（OPT）三、实验分析在进程运行过程中，若其所访问的页面不存在内存而需要把它们调入内存，但内存已无空闲时，为了保证该进程能够正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中。但应调出哪个页面，需根据一定的算法来确定，算法的好坏，直接影响到系统的性能。一个好的页面置换算法，应该有较低的页面更换频率。假设分给一作业的物理块数为3，页面数为20个。页面号为(20个)：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，11．先进先出(FIFO)置换算法的思路该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按照先后次序连接成一个队列，并设置一个替换指针，使它总指向最老的页面。2．最近久未使用(LRU)置换算法的思路最近久未使用置换算法的替换规则，是根据页面调入内存后的使用情况来进行决策的。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间，当需淘汰一个页面的时候选择现有页面中其时间值最大的进行淘汰。3.最佳（OPT）置换算法的思路其所选择的被淘汰的页面，奖是以后不使用的，或者是在未来时间内不再被访问的页面，采用最佳算法，通常可保证获得最低的缺页率。4．数据结构structpageInfor{intcontent;//页面号inttimer;//被访问标记};classPRA{public:PRA(void);intfindSpace(void);//查找是否有空闲内存intfindExist(intcurpage);//查找内存中是否有该页面intfindReplace(void);//查找应予置换的页面voiddisplay(void);//显示voidFIFO(void);//FIFO算法voidLRU(void);//LRU算法voidBlockClear(void);//BLOCK清空，以便用另一种方法重新演示pageInfor*block;//物理块pageInfor*page;//页面号串private:};5．FIFO页面置换算法当需要访问一个新的页面时，首先调用findExist(i)函数来查看物理块中是否就有这个页面，若要查看的页面物理块中就有，则调用display函数直接显示，不需要替换页面；如果要查看的页面物理块中没有，就需要寻找空闲物理块放入，若存在有空闲物理块，则将页面放入；若没有空闲物理块，则调用findReplace函数替换页面。并将物理块中所有页面timer++。6．LRU页面置换算法当需要访问一个新的页面，首先调用findExist(i)函数查看物理块中是否就有这个页面。7.OPT页面置换算法当需要访问一个新的页面，首先调用findExist(i)函数来查看物理块中是否有这个页面。8．寻找置换页面函数findReplace比较三个物理块中的时间标记timer，找到时间最久的。四、源程序结构分析1．程序结构程序共有以下九个部分：intfindSpace(void);//查找是否有空闲内存intfindExist(intcurpage);//查找内存中是否有该页面intfindReplace(void);//查找应予置换的页面voiddisplay(void);//显示voidFIFO(void);//FIFO算法voidLRU(void);//LRU算法voidOPT(void);//OPT算法；voidBlockClear(void);//BLOCK清空，以便用另一种方法重新演示intmain()//主程序2．源程序代码#includeiostream.h#defineBsize3#definePsize20structpageInfor{intcontent;//页面号inttimer;//被访问标记};classPRA{public:PRA(void);intfindSpace(void);//查找是否有空闲内存intfindExist(intcurpage);//查找内存中是否有该页面intfindReplace(void);//查找应予置换的页面voiddisplay(void);//显示voidFIFO(void);//FIFO算法voidLRU(void);//LRU算法voidOptimal(void);//OPTIMAL算法voidBlockClear(void);//BLOCK恢复pageInfor*block;//物理块pageInfor*page;//页面号串private:};PRA::PRA(void){intQString[20]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};block=newpageInfor[Bsize];for(inti=0;iBsize;i++){block[i].content=-1;block[i].timer=0;}page=newpageInfor[Psize];for(i=0;iPsize;i++){page[i].content=QString[i];page[i].timer=0;}}intPRA::findSpace(void){for(inti=0;iBsize;i++)if(block[i].content==-1)returni;//找到空闲内存，返回BLOCK中位置return-1;}intPRA::findExist(intcurpage){for(inti=0;iBsize;i++)if(block[i].content==page[curpage].content)returni;//找到内存中有该页面，返回BLOCK中位置return-1;}intPRA::findReplace(void){intpos=0;for(inti=0;iBsize;i++)if(block[i].timer=block[pos].timer)pos=i;//找到应予置换页面，返回BLOCK中位置returnpos;}voidPRA::display(void){for(inti=0;iBsize;i++)if(block[i].content!=-1)coutblock[i].content;coutendl;}voidPRA::Optimal(void){intexist,space,position;for(inti=0;iPsize;i++){exist=findExist(i);if(exist!=-1){cout不缺页endl;}else{space=findSpace();if(space!=-1){block[space]=page[i];display();}else{for(intk=0;kBsize;k++)for(intj=i;jPsize;j++){if(block[k].content!=page[j].content){block[k].timer=1000;}//将来不会用，设置TIMER为一个很大数else{block[k].timer=j;break;}}position=findReplace();block[position]=page[i];display();}}}}voidPRA::LRU(void){intexist,space,position;for(inti=0;iPsize;i++){exist=findExist(i);if(exist!=-1){cout不缺页endl;block[exist].timer=-1;//恢复存在的并刚访问过的BLOCK中页面TIMER为-1}else{space=findSpace();if(space!=-1){block[space]=page[i];display();}else{position=findReplace();block[position]=page[i];display();}}for(intj=0;jBsize;j++)block[j].timer++;}}voidPRA::FIFO(void){intexist,space,position;for(inti=0;iPsize;i++){exist=findExist(i);if(exist!=-1){cout不缺页endl;}else{space=findSpace();if(space!=-1){block[space]=page[i];display();}else{position=findReplace();block[position]=page[i];display();}}for(intj=0;jBsize;j++)block[j].timer++;//BLOCK中所有页面TIMER++}}voidPRA::BlockClear(void){for(inti=0;iBsize;i++){block[i].content=-1;block[i].timer=0;}}voidmain(void){cout|----------页面置换算法----------|endl;cout|---powerbywangxinchuang(080501228)---|endl;cout|-------------------------------------|endl;cout页面号引用串:7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1endl;cout----------------------------------------------------endl;cout选择1应用Optimal算法endl;cout选择2应用FIFO算法endl;cout选择3应用LRU算法endl;cout选择0退出endl;intselect;PRAtest;while(select){cinselect;switch(select){case0:break;case1:coutOptimal算法结果如下:endl;test.Optimal();test.BlockClear();cout----------------------endl;break;case2:coutFIFO算法结果如下:endl;test.FIFO();test.BlockClear();cout----------------------endl;break;case3:coutLRU算法结果如下:endl;test.LRU();test.BlockClear();cout----------------------endl;break;default:cout请输入正确功能号endl;break;}}}五、实验结果1运行后的初始界面2opt算法3.FIFO算法4LRU算法