计算机操作系统-实验三页面置换算法模拟实验

淮海工学院计算机工程学院实验报告书课程名：《操作系统原理A》题目：虚拟存储器管理页面置换算法模拟实验班级：Z计121学号：2014140093姓名：薛慧君评语：成绩：指导教师：批阅时间：年月日《操作系统原理》实验报告-1-一、实验目的与要求1.目的：请求页式虚存管理是常用的虚拟存储管理方案之一。通过请求页式虚存管理中对页面置换算法的模拟，有助于理解虚拟存储技术的特点，并加深对请求页式虚存管理的页面调度算法的理解。2.要求：本实验要求使用C语言编程模拟一个拥有若干个虚页的进程在给定的若干个实页中运行、并在缺页中断发生时分别使用FIFO和LRU算法进行页面置换的情形。其中虚页的个数可以事先给定（例如10个），对这些虚页访问的页地址流（其长度可以事先给定，例如20次虚页访问）可以由程序随机产生，也可以事先保存在文件中。要求程序运行时屏幕能显示出置换过程中的状态信息并输出访问结束时的页面命中率。程序应允许通过为该进程分配不同的实页数，来比较两种置换算法的稳定性。二、实验说明1．设计中虚页和实页的表示本设计利用C语言的结构体来描述虚页和实页的结构。pnpfntime虚页结构实页结构在虚页结构中，pn代表虚页号，因为共10个虚页，所以pn的取值范围是0—9。pfn代表实页号，当一虚页未装入实页时，此项值为-1；当该虚页已装入某一实页时，此项值为所装入的实页的实页号pfn。time项在FIFO算法中不使用，在LRU中用来存放对该虚页的最近访问时间。在实页结构中中，pn代表虚页号，表示pn所代表的虚页目前正放在此实页中。pfn代表实页号，取值范围（0—n-1）由动态指派的实页数n所决定。next是一个指向实页结构体的指针，用于多个实页以链表形式组织起来，关于实页链表的组织详见下面第4点。2．关于缺页次数的统计为计算命中率，需要统计在20次的虚页访问中命中的次数。为此，程序应设置一个计数器count，来统计虚页命中发生的次数。每当所访问的虚页的pfn项值不为-1，表示此虚页已被装入某实页内，此虚页被命中，count加1。最终命中率=count/20*100%。3．LRU算法中“最近最久未用”页面的确定为了能找到“最近最久未用”的虚页面，程序中可引入一个时间计数器countime，每当要访问一个虚页面时，countime的值加1，然后将所要访问的虚页的time项值设置为增值后的当前pnpfnnext《操作系统原理》实验报告-2-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值为最小的虚页，将该虚页从装载它的那个实页中置换出去，并在该实页中装入当前正要访问的虚页。三、程序流程图输入页面访问序列取访问的页号查页表是否缺页置缺页标志位flag为‘*’按算法不同淘汰一页面调入所访问的页面是否《操作系统原理》实验报告-3-四、主要程序清单#includestdio.h#includestdlib.h/*全局变量*/intmSIZE;/*物理块数*/intpSIZE;/*页面号引用串个数*/FIFO开始还有指令吗？计算出页号在实存对列中查找该页号找到了吗新页块按实际循环入实存对列计算出命中率结束NNYLRU开始还有指令吗？计算出页号在实存对列中查找该页号找到了吗新页块压入栈顶，同时栈底页号移出计算出命中率结束NNY把新页放入栈顶，同时向下移动其余页号《操作系统原理》实验报告-4-staticintmemery[10]={0};/*物理块中的页号*/staticintpage[100]={0};/*页面号引用串*/staticinttemp[100][10]={0};/*辅助数组*//*置换算法函数*/voidFIFO();voidLRU();voidOPT();/*辅助函数*/voidprint(unsignedintt);voiddesignBy();voiddownload();voidmDelay(unsignedintDelay);/*主函数*/voidmain(){inti,k,code;printf(请输入物理块的个数(M=10)：);scanf(%d,&mSIZE);printf(请输入页面号引用串的个数(P=100)：);scanf(%d,&pSIZE);puts(请依次输入页面号引用串(连续输入，无需隔开)：);for(i=0;ipSIZE;i++)scanf(%1d,&page[i]);download();do{puts(输入的页面号引用串为：);for(k=0;k=(pSIZE-1)/20;k++){《操作系统原理》实验报告-5-for(i=20*k;(ipSIZE)&&(i20*(k+1));i++){if(((i+1)%20==0)||(((i+1)%20)&&(i==pSIZE-1)))printf(%d\n,page[i]);elseprintf(%d,page[i]);}}printf(***********************\n);printf(*请选择页面置换算法：\t\t\t*\n);printf(*-----------------------------------------*\n);printf(*1.先进先出(FIFO)2.最近最久未使用(LRU)*\n);printf(*3.退出*\n);printf(***********************\n);printf(请选择操作：[]\b\b);scanf(%d,&code);switch(code){case1:FIFO();break;case2:LRU();break;case3:OPT();break;case4:system(cls);//system(color0A);exit(0);《操作系统原理》实验报告-6-default:printf(输入错误，请重新输入：);}printf(按任意键重新选择置换算法：);getchar();}while(code!=4);getchar();}/*载入数据*/voiddownload(){printf(\nFinish.\n载入成功!);}/*设置延迟*/voidmDelay(unsignedintDelay){unsignedinti;for(;Delay0;Delay--){for(i=0;i124;i++){printf(\b);}}}/*显示设计者信息*/voidprint(unsignedintt){inti,j,k,l;intflag;for(k=0;k=(pSIZE-1)/20;k++){《操作系统原理》实验报告-7-for(i=20*k;(ipSIZE)&&(i20*(k+1));i++){if(((i+1)%20==0)||(((i+1)%20)&&(i==pSIZE-1)))printf(%d\n,page[i]);elseprintf(%d,page[i]);}for(j=0;jmSIZE;j++){for(i=20*k;(imSIZE+20*k)&&(ipSIZE);i++){if(i=j)printf(|%d|,temp[i][j]);elseprintf(||);}for(i=mSIZE+20*k;(ipSIZE)&&(i20*(k+1));i++){for(flag=0,l=0;lmSIZE;l++)if(temp[i][l]==temp[i-1][l])flag++;if(flag==mSIZE)/*页面在物理块中*/printf();elseprintf(|%d|,temp[i][j]);}/*每行显示20个*/if(i%20==0)continue;printf(\n);}}printf(----------------------------------------\n);《操作系统原理》实验报告-8-printf(缺页次数：%d\t\t,t+mSIZE);printf(缺页率：%d/%d\n,t+mSIZE,pSIZE);printf(置换次数：%d\t\t,t);printf(访问命中率：%d%%\n,(pSIZE-(t+mSIZE))*100/pSIZE);printf(----------------------------------------\n);}/*计算过程延迟*/voidcompute(){inti;printf(正在进行相关计算，请稍候);for(i=0;i++30;printf(\b));for(i=0;i++30;printf());for(i=0;i++30;printf(\b));}/*先进先出页面置换算法*/voidFIFO(){intmemery[10]={0};inttime[10]={0};/*记录进入物理块的时间*/inti,j,k,m;intmax=0;/*记录换出页*/intcount=0;/*记录置换次数*//*前mSIZE个数直接放入*/for(i=0;imSIZE;i++){memery[i]=page[i];time[i]=i;for(j=0;jmSIZE;j++)《操作系统原理》实验报告-9-temp[i][j]=memery[j];}for(i=mSIZE;ipSIZE;i++){/*判断新页面号是否在物理块中*/for(j=0,k=0;jmSIZE;j++){if(memery[j]!=page[i])k++;}if(k==mSIZE)/*如果不在物理块中*/{count++;/*计算换出页*/max=time[0]time[1]?0:1;for(m=2;mmSIZE;m++)if(time[m]time[max])max=m;memery[max]=page[i];time[max]=i;/*记录该页进入物理块的时间*/for(j=0;jmSIZE;j++)temp[i][j]=memery[j];}else{for(j=0;jmSIZE;j++)temp[i][j]=memery[j];}}《操作系统原理》实验报告-10-compute();print(count);}/*最近最久未使用置换算法*/voidLRU(){intmemery[10]={0};intflag[10]={0};/*记录页面的访问时间*/inti,j,k,m;intmax=0;/*记录换出页*/intcount=0;/*记录置换次数*//*前mSIZE个数直接放入*/for(i=0;imSIZE;i++){memery[i]=page[i];flag[i]=i;for(j=0;jmSIZE;j++)temp[i][j]=memery[j];}for(i=mSIZE;ipSIZE;i++){/*判断新页面号是否在物理块中*/for(j=0,k=0;jmSIZE;j++){if(memery[j]!=page[i])k++;elseflag[j]=i;《操作系统