操作系统实验3虚拟存储器管理[1]

实验报告班级：系统本111学号：2011415108姓名：张国锋日期：2013.6.27⒈实验题目模拟分页式虚拟存储管理实验。2．实验要求编写一段程序来模拟页面置换算法。要求能分别显示最佳(Optimal)置换算法、先进先出(FIFO)页面置换算法和最近最久未使用(LRU)置换算法的置换过程。3.实验目的通过本实验帮助学生理解虚拟存储器的工作方法。了解分页式存储管理里中各页面置换算法是怎样实现的，各算法有怎样的优缺点。⒋实验原理分析⑴页面置换算法是在分页存储管理方式中为了合理的将进程运行所需的页面调入内存而产生的算法。一个好的页面转换算法，应具有较低的页面更换频率。最常见的页面置换算法有最佳(Optimal)置换算法、先进先出(FIFO)页面置换算法和最近最久未使用(LRU)置换算法。⑵算法的说明最佳置换算法：选择以后永不使用或是在最长时间内不再被访问的页面作为被淘汰的页面。这种算法通常可保证获得最低的缺页率，但因为内存中哪个页面是以后永不使用的是无法预知的，所以该算法是无法实现的。先进先出页面置换算法：选择内存中驻留时间最长的页面作为被淘汰的页面。该算法实现简单，只需将调入内存中的页面链成一个队列，并设置一个指针指向最老的页面即可。最近最久未使用置换算法：选择最近最久未使用的页面作为被淘汰的页面。该算法需要为每个页面设置一个访问字段用来记录页面上次被访问的时间，通过这个时间来决定淘汰哪一个页面。⑶主要变量及函数说明如表1所示表1主要变量及函数说明表PRA(void)初始化intfindSpace(void)查找是否有空闲内存intfindExist(intcurpage)查找内存中是否有该页面intfindReplace(void)查找应予置换的页面voiddisplay(void)显示voidFIFO(void)FIFO算法voidLRU(void)LRU算法voidOptimal(void)OPTIMAL算法voidBlockClear(void)BLOCK恢复structpageInfor*block物理块structpageInfor*page页面号串5.实验代码清单#includestdio.h#includestdlib.h#includeconio.h#defineBsize3#definePsize20structpageInfor{intcontent;/*页面号*/inttimer;/*被访问标记*/};voidPRA();/*初始化*/intfindSpace();/*查找是否有空闲内存*/intfindExist(intcurpage);/*查找内存中是否有该页面*/intfindReplace();/*查找应予置换的页面*/voiddisplay();/*显示*/voidFIFO();/*FIFO算法*/voidLRU();/*LRU算法*/voidOptimal();/*OPTIMAL算法*/voidBlockClear();/*BLOCK恢复*/structpageInfor*block;/*物理块*/structpageInfor*page;/*页面号串*/intQString[20];voidPRA(){inti,n;printf(请输入页面号引用串:\n);for(i=0;i20;i++){scanf(%d,&QString[i]);}printf(您输入页面号引用串为:\n);printf(==================\n);for(i=0;i20;i++){printf(%d\t,QString[i]);}printf(==================\n);block=(structpageInfor*)malloc(sizeof(structpageInfor));for(i=0;iBsize;i++){block[i].content=-1;block[i].timer=0;}page=(structpageInfor*)malloc(sizeof(structpageInfor)*Psize);for(i=0;iPsize;i++){page[i].content=QString[i];page[i].timer=0;}}intfindSpace(){inti=0;for(i=0;iBsize;i++)if(block[i].content==-1)returni;/*找到空闲内存，返回BLOCK中位置*/return-1;}intfindExist(intcurpage){inti=0;for(i=0;iBsize;i++)if(block[i].content==page[curpage].content)returni;/*找到内存中有该页面，返回BLOCK中位置*/return-1;}intfindReplace(){intpos=0,i;for(i=0;iBsize;i++)if(block[i].timer=block[pos].timer)pos=i;/*找到应予置换页面，返回BLOCK中位置*/returnpos;}voiddisplay(){inti=0;for(i=0;iBsize;i++)if(block[i].content!=-1)printf(%d\t,block[i].content);printf(\n);}voidOptimal(){intexist,space,position,i,k,j;for(i=0;iPsize;i++){exist=findExist(i);if(exist!=-1){printf(不缺页\n);}else{space=findSpace();if(space!=-1){block[space]=page[i];display();}else{for(k=0;kBsize;k++)for(j=i;jPsize;j++){if(block[k].content!=page[j].content){block[k].timer=1000;}else{block[k].timer=j;break;}}position=findReplace();block[position]=page[i];display();}}}getch();system(cls);}voidLRU(){intexist,space,position,i,k,j;for(i=0;iPsize;i++){exist=findExist(i);if(exist!=-1){printf(不缺页\n);block[exist].timer=-1;}else{space=findSpace();if(space!=-1){block[space]=page[i];display();}else{position=findReplace();block[position]=page[i];display();}}for(j=0;jBsize;j++)block[j].timer++;}getch();system(cls);}voidFIFO(){intexist,space,position,i,k,j;for(i=0;iPsize;i++){exist=findExist(i);if(exist!=-1){printf(不缺页\n);}else{space=findSpace();if(space!=-1){block[space]=page[i];display();}else{position=findReplace();block[position]=page[i];display();}}for(j=0;jBsize;j++)block[j].timer++;/*BLOCK中所有页面TIMER++*/}getch();system(cls);}voidBlockClear()//清空页面信息{inti;for(i=0;iBsize;i++){block[i].content=-1;block[i].timer=0;}}voidmain(){PRA();system(color2);intselect=1;while(select){printf(系统本111项静怡小组页面置换算法程序\n);printf(请按以下菜单选择：\n);printf([1]\tOptimal\t算法\n);printf([2]\tFIFO\t算法\n);printf([3]\tLRU\t算法\n);printf([0]\t退出\n);scanf(%d,&select);switch(select){case0:break;case1:printf(Optimal算法结果如下:\n);Optimal();break;case2:printf(FIFO算法结果如下:\n);FIFO();break;case3:printf(LRU算法结果如下:\n);LRU();break;default:printf(菜选项输入错误，请输入(1,2,3,0)\n);break;}BlockClear();}}6.实现①输入课本中例题数据，创建3个物理模块，页面引用串为70120304230321201701运行界面如图1所示图1输入②用最佳置换算法，运行后如图2所示图2Optinal算法③用FIFO先进先出算法运行后如图3所示图3FIFO算法④用LRU最久未使用算法，运行后如图4所示图4LRU算法