实验3虚拟存储器管理

淮海工学院计算机科学系实验报告书课程名：《操作系统原理》题目：实验三虚拟存储器管理班级：Z软件52学号：2017140595姓名：郭文静评语：成绩：指导教师：批阅时间：年月日操作系统原理实验报告1、实验目的与要求本实验模拟请求页式虚存管理系统的页面置换情况。实验程序能模拟一个拥有若干个虚页的进程在给定的若干个实页中运行、并在缺页中断发生时分别使用FIFO和LRU算法进行页面置换的情形。要求程序运行时屏幕能显示出置换过程中的状态信息并输出访问结束时的页面命中率。并通过为该进程分配不同的实页数，来比较几种算法的稳定性。2、实验内容或题目本实验要求使用C/C++语言编程模拟一个拥有若干个虚页的进程在给定的若干个实页中运行、并在缺页中断发生时分别使用FIFO和LRU算法进行页面置换的情形。其中虚页的个数可以事先给定（例如10个），对这些虚页访问的页地址流（其长度可以事先给定，例如20次虚页访问）可以由程序随机产生，也可以事先保存在文件中。要求程序运行时屏幕能显示出置换过程中的状态信息并输出访问结束时的页面命中率。程序应允许通过为该进程分配不同的实页数，来比较两种置换算法的稳定性。实验说明：（1）设计中虚页和实页的表示本设计利用C/C++/Java语言的结构体来描述虚页和实页的结构。pnpfntime虚页结构实页结构在虚页结构中，pn代表虚页号，因为共10个虚页，所以pn的取值范围是0—9。pfn代表实页号，当一虚页未装入实页时，此项值为-1；当该虚页已装入某一实页时，此项值为所装入的实页的实页号pfn。time项在FIFO算法中不使用，在LRU中用来存放对该虚页的最近访问时间。在实页结构中中，pn代表虚页号，表示pn所代表的虚页目前正放在此实页中。pfn代表实页号，取值范围（0—n-1）由动态指派的实页数n所决定。next是一个指向实页结构体的指针，用于多个实页以链表形式组织起来，关于实页链表的组织详见下面第4点。（2）关于缺页次数的统计pnpfnnext操作系统原理实验报告为计算命中率，需要统计在20次的虚页访问中命中的次数。为此，程序应设置一个计数器count，来统计虚页命中发生的次数。每当所访问的虚页的pfn项值不为-1，表示此虚页已被装入某实页内，此虚页被命中，count加1。最终命中率=count/20*100%。（3）LRU算法中“最近最久未用”页面的确定为了能找到“最近最久未用”的虚页面，程序中可引入一个时间计数器countime，每当要访问一个虚页面时，countime的值加1，然后将所要访问的虚页的time项值设置为增值后的当前countime值，表示该虚页的最后一次被访问时间。当LRU算法需要置换时，从所有已分配实页的虚页中找出time值为最小的虚页就是“最近最久未用”的虚页面，应该将它置换出去。（4）算法中实页的组织因为能分配的实页数n是在程序运行时由用户动态指派的，所以应使用链表组织动态产生的多个实页。为了调度算法实现的方便，可以考虑引入free和busy两个链表：free链表用于组织未分配出去的实页，首指针为free_head，初始时n个实页都处于free链表中；busy链表用于组织已分配出去的实页，首指针为busy_head，尾指针为busy_tail，初始值都为null。当所要访问的一个虚页不在实页中时，将产生缺页中断。此时若free链表不为空，就取下链表首指针所指的实页，并分配给该虚页。若free链表为空，则说明n个实页已全部分配出去，此时应进行页面置换：对于FIFO算法要将busy_head所指的实页从busy链表中取下，分配给该虚页，然后再将该实页插入到busy链表尾部；对于LRU算法则要从所有已分配实页的虚页中找出time值为最小的虚页，将该虚页从装载它的那个实页中置换出去，并在该实页中装入当前正要访问的虚页。3、实验步骤（1）理解好相关实验说明。（2）根据实验说明，画出相应的程序流程图。（3）按照程序流程图，用C/C++/Java语言编程并实现。4、流程图操作系统原理实验报告主页面FIFO算法OPT算法LRU算法开始取指令取指令中的页号查页表页标志=1？形成绝对地址输出绝对地址有后续指令输出*页号表示发生缺页中断YN发生缺页中断取下一条指令Y结束N操作系统原理实验报告5、源代码与测试数据与实验结果（可以抓图粘贴）#includeiostream.hconstintDataMax=100;constintBlockNum=10;intDataShow[BlockNum][DataMax];//用于存储要显示的数组boolDataShowEnable[BlockNum][DataMax];//用于存储数组中的数据是否需要显示//intData[DataMax]={4,3,2,1,4,3,5,4,3,2,1,5,6,2,3,7,1,2,6,1};//测试数据//intN=20;//输入页面个数intData[DataMax];//保存数据intBlock[BlockNum];//物理块intcount[BlockNum];//计数器intN;//页面个数intM;//最小物理块数intChangeTimes;voidDataInput();//输入数据的函数voidDataOutput();voidFIFO();//FIFO函数voidOptimal();//Optimal函数voidLRU();//LRU函数///*intmain(intargc,char*argv[]){DataInput();//DataInput();//FIFO();//Optimal();//LRU();//return0;intmenu;操作系统原理实验报告while(true){coutendl;cout*菜单选择*endl;cout*******************************************************endl;cout*1-FIFO*endl;cout*2-Optimal*endl;cout*3-LRU*endl;cout*0-EXIT*endl;cout*******************************************************endl;cinmenu;switch(menu){case1:FIFO();break;case2:Optimal();break;case3:LRU();break;default:break;}if(menu!=1&&menu!=2&&menu!=3)break;}}//*/voidDataInput(){cout请输入最小物理块数：;cinM;while(MBlockNum)//大于数据个数{操作系统原理实验报告cout物理块数超过预定值，请重新输入：;cinM;}cout请输入页面的个数：;cinN;while(NDataMax)//大于数据个数{cout页面个数超过预定值，请重新输入：;cinN;}cout请输入页面访问序列：endl;for(inti=0;iN;i++)cinData[i];}voidDataOutput(){inti,j;for(i=0;iN;i++)//对所有数据操作{coutData[i];}coutendl;for(j=0;jM;j++){cout;for(i=0;iN;i++)//对所有数据操作{if(DataShowEnable[j][i])coutDataShow[j][i];操作系统原理实验报告elsecout;}coutendl;}cout缺页次数:ChangeTimesendl;cout缺页率:ChangeTimes*100/N%endl;}voidFIFO(){inti,j;boolfind;intpoint;inttemp;//临时变量ChangeTimes=0;for(j=0;jM;j++)for(i=0;iN;i++)DataShowEnable[j][i]=false;//初始化为false，表示没有要显示的数据for(i=0;iM;i++){count[i]=0;//大于等于BlockNum，表示块中没有数据，或需被替换掉//所以经这样初始化（321），每次替换=3的块，替换后计数值置1，//同时其它的块计数值加1，成了（132），见下面先进先出程序段}for(i=0;iN;i++)//对有所数据操作{//增加countfor(j=0;jM;j++)count[j]++;操作系统原理实验报告find=false;//表示块中有没有该数据for(j=0;jM;j++){if(Block[j]==Data[i]){find=true;}}if(find)continue;//块中有该数据，判断下一个数据//块中没有该数据ChangeTimes++;//缺页次数++if((i+1)M)//因为i是从0开始记，而M指的是个数，从1开始，所以i+1{//获得要替换的块指针temp=0;for(j=0;jM;j++){if(tempcount[j]){temp=count[j];point=j;//获得离的最远的指针}}}elsepoint=i;//替换Block[point]=Data[i];count[point]=0;//更新计数值//保存要显示的数据操作系统原理实验报告for(j=0;jM;j++){DataShow[j][i]=Block[j];DataShowEnable[iM?(j=i?j:i):j][i]=true;//设置显示数据}}//输出信息coutendl;coutFIFO=endl;DataOutput();}voidOptimal(){inti,j,k;boolfind;intpoint;inttemp;//临时变量，比较离的最远的时候用ChangeTimes=0;for(j=0;jM;j++)for(i=0;iN;i++)DataShowEnable[j][i]=false;//初始化为false，表示没有要显示的数据//for(i=0;iM;i++)//{//count[i]=0;////}for(i=0;iN;i++)//对有所数据操作{find=false;//表示块中有没有该数据for(j=0;jM;j++)操作系统原理实验报告{if(Block[j]==Data[i])find=true;}if(find)continue;//块中有该数据，判断下一个数据//块中没有该数据，最优算法ChangeTimes++;//缺页次数++for(j=0;jM;j++){//找到下一个值的位置find=false;for(k=i;kN;k++){if(Block[j]==Data[k]){find=true;count[j]=k;break;}}if(!find)count[j]=N;}if((i+1)M)//因为i是从0开始记，而BlockNum指的是个数，从1开始，所以i+1{//获得要替换的块指针temp=0;for(j=0;jM;j++){if(tempcount[j])操作系统原理实验报告{temp=count[j];point=j;//获得离的最远的指针}}}elsepoint=i;//替换Block[point]=Data[i];//保存要显示的数据for(j=0;jM;j++){DataShow[j][i]=Block[j];DataShowEnable[iM?(j=i?j:i):j][i]=true;//设置显示数据}}//输出信息coutendl;coutOptimal=endl;DataOutput();}voidLRU(){inti,j;boolf