页面置换算法模拟实验报告

....z...中北大学软件学院实验报告专业软件工程课程名称计算机操作系统学号姓名....z...辅导教师静成绩实验日期2015.11.20实验时间1实验名称：实验四页面置换算法模拟2、实验目的（1）了解内存分页管理策略（2）掌握调页策略（3）掌握一般常用的调度算法（4）学会各种存储分配算法的实现方法。（5）了解页面大小和内存实际容量对命中率的影响。3、实验要求编程实现页面置换算法，最少实现两种算法，比较算法的优劣，并将调试结果显示在计算机屏幕上，并检测机算和笔算的一致性。（1）采用页式分配存储方案，通过分别计算不同算法的命中率来比较算法的优劣，同时也考虑页面大小及内存实际容量对命中率的影响；（2）实现OPT算法(最优置换算法)、LRU算法(LeastRecently)、FIFO算法(FirstINFirstOut)的模拟；（3）使用某种编程语言模拟页面置换算法。....z...4、实验算法描述（1）FIFO（先进先出）YNNY图4-1FIFO算法流程图开始页面走向存入数组p[]中，内存块用page[]表示初始化为0当前p[]中第i个元素是否已在内存中Page[]是否有空把page[]中最先装入的页面置换出去.i++把p[i]的内容直接装入最上面一个空内存块，i++输出当前内存块状态结束i++....z...（2）LRU（最近最久未使用）YNYN图4-2LRU算法流程图开始页面走向存入数组p[]中，内存块用page[]表示初始化为0当前p[]中第i个元素是否已在内存Page[]是否有空把page[]中最近最久未使用的页面置换出去.i++把p[i]的内容直接装入最上面一个空内存块，i++输出当前内存块状态结束i++....z...（3）OPT（最佳置换算法）YNYN图4-3OPT流程图开始页面走向存入数组p[]中，内存块用page[]表示初始化为0当前p[]中第i个元素是否已在内存Page[]是否有空把page[]中以后一段时间都不使用或是使用时间离现在最远的换出.i++把p[i]的内容直接装入最上面一个空内存块，i++输出当前内存块状态结束i++....z...6、实验代码#includeiostreamusingnamespacestd;#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++)....z...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];....z...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....z...{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;}....z...}voidmain(void){cout页面置换算法:endl;cout页面号引用串:7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1endl;cout选择1应用LRU算法endl;cout选择2应用FIFO算法endl;cout选择3应用Optimal算法endl;cout选择0退出endl;intselect;PRAtest;while(select){cinselect;switch(select){case0:break;case1:coutLRU算法结果如下:endl;test.LRU();test.BlockClear();cout----------------------endl;break;case2:coutFIFO算法结果如下:endl;test.FIFO();test.BlockClear();cout----------------------endl;break;case3:coutOptimal算法结果如下:endl;test.Optimal();test.BlockClear();cout----------------------endl;break;default:cout请输入正确功能号endl;break;}}}....z...6、实验结果....z.......z...7、实验心得加深了对操作系统的认识,了解了操作系统中各种资源分配算法的实现,特别是对虚拟存储,页面置换有了深入的了解,并能够用高级语言进行模拟演示。在这短短的两周时间里，通过浏览、阅读有关的资料，学到了很多东西，同时也发现仅仅书本的知识是远远不够的，需要把知识运用到实践中去，能力才能得到提高。使用MFC可视化编程极大的减少了编写的代码量，直观的界面设计，不但便于修改，而且简化了界面程序代码的编写两种页面置换算法FIFO和LRU理解起来相当容易，但在实际编程实现的时候需要注意各种细节，需要耐心细致，实际编程中遇到一些细节上的小问题确实需要仔细考虑才行。....z...