实验三2011122635王秀丽

淮海工学院计算机科学系实验报告书课程名：《操作系统原理A》题目：虚拟存储器管理页面置换算法模拟实验班级：软件112学号：2011122635姓名：王秀丽评语：成绩：指导教师：批阅时间：年月日《操作系统原理A》实验报告-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《操作系统原理A》实验报告-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值为最小的虚页，将该虚页从装载它的那个实页中置换出去，并在该实页中装入当前正要访问的虚页。三、程序流程图四、主要程序清单#includestdlib.h《操作系统原理A》实验报告-3-#includestdio.h#includeconio.h#includetime.h#defineM10//10个虚页#defineN20//20个页面的访问序列#defineL5//固定5个实页。//定义虚页的结构typedefstructVirtualPage{intpn;intpfn;inttime;}VirtualPage;//定义实页的结构typedefstructPage{intpn;intpfn;structPage*next;}Page;structPagepp[L];structVirtualPagevp[M];intqueue[N];intcount;intcountime;intMemoryStatus[L][N];intNotInMemory[N];intsa;structPage*Free,*Free_head,*Busy,*Busy_tail,*Busy_head,*temp,*temp2;voidFIFO(){inti,j,k,currentpage;for(i=0;iN;i++)《操作系统原理A》实验报告-4-{currentpage=queue[i];if(vp[currentpage].pfn!=-1){for(j=0;jL;j++){MemoryStatus[j][i]=MemoryStatus[j][i-1];}NotInMemory[i]=0;}else{count=count+1;if(Free!=NULL){temp=Free_head;Free_head=Free_head-next;Free=Free_head;vp[currentpage].pfn=temp-pfn;temp-pn=currentpage;temp-next=NULL;if(Busy==NULL){Busy=temp;Busy_head=Busy;Busy_tail=Busy;}else{Busy_tail-next=temp;Busy_tail=temp;}for(k=0;kL;k++){《操作系统原理A》实验报告-5-MemoryStatus[k][i]=MemoryStatus[k][i-1];}MemoryStatus[temp-pfn][i]=currentpage;}else{temp=Busy;Busy_head=Busy-next;Busy=Busy_head;vp[temp-pn].pfn=-1;vp[currentpage].pfn=temp-pfn;temp-pn=currentpage;temp-next=NULL;Busy_tail-next=temp;Busy_tail=temp;for(k=0;kL;k++){MemoryStatus[k][i]=MemoryStatus[k][i-1];}MemoryStatus[temp-pfn][i]=currentpage;}}}}voidLRU(){inti,j,k,currentpage;for(i=0;iN;i++)《操作系统原理A》实验报告-6-{currentpage=queue[i];if(vp[currentpage].pfn!=-1){countime=countime+1;vp[currentpage].time=countime;for(j=0;jL;j++){MemoryStatus[j][i]=MemoryStatus[j][i-1];}NotInMemory[i]=0;}else{count=count+1;if(Free!=NULL){temp=Free_head;Free_head=Free_head-next;Free=Free_head;vp[currentpage].pfn=temp-pfn;temp-pn=currentpage;countime=countime+1;vp[currentpage].time=countime;temp-next=NULL;if(Busy==NULL){Busy=temp;Busy_head=Busy;Busy_tail=Busy;}else{《操作系统原理A》实验报告-7-Busy_tail-next=temp;Busy_tail=temp;}for(k=0;kL;k++){MemoryStatus[k][i]=MemoryStatus[k][i-1];}MemoryStatus[temp-pfn][i]=currentpage;}else{intmin=100;for(k=0;k10;k++){if(minvp[k].time&&vp[k].pfn!=-1){min=vp[k].time;sa=k;}}vp[currentpage].pfn=vp[sa].pfn;vp[sa].pfn=-1;countime=countime+1;vp[currentpage].time=countime;for(k=0;kL;k++){MemoryStatus[k][i]=MemoryStatus[k][i-1];}MemoryStatus[vp[currentpage].pfn][i]=currentpage;}}《操作系统原理A》实验报告-8-}}voidmain(){intflag=1;inti,j,k;inta;while(flag!=0){count=0;countime=0;//初始化10个虚页for(i=0;iM;i++){vp[i].pn=i;vp[i].pfn=-1;vp[i].time=0;}//初始化5个实页，并将其串成链表形式for(i=0;iL;i++){pp[i].pn=-1;pp[i].pfn=i;pp[i].next=NULL;}//将5个实页依次相连，形成Free链表Free=&pp[0];Free-next=&pp[1];pp[1].next=&pp[2];pp[2].next=&pp[3];pp[3].next=&pp[4];pp[4].next=NULL;《操作系统原理A》实验报告-9-Free_head=Free;//初始化Busy链表Busy=NULL;Busy_head=NULL;Busy_tail=NULL;//初始化MemoryStatus数组for(i=0;iL;i++)for(j=0;jN;j++){MemoryStatus[i][j]=-1;}//初始化NotInMemory数组for(i=0;iN;i++){NotInMemory[i]=1;}for(i=0;iN;i++){queue[i]=rand()%10;}printf(\n随机产生20页面访问顺序为:\n\n);for(i=0;iN;i++){printf(%3d,queue[i]);}printf(\n*******************************************************************************\n);printf(\n请选择你要使用的算法(1.FIFO;2.LRU)\n\n);scanf(%d,&a);if(a==1)FIFO();elseLRU();《操作系统原理A》实验报告-10-for(i=0;iN;i++){printf(|%3d,queue[i]);}printf(\n);printf(*******************************************************************************\n);for(i=0;iL;i++){for(j=0;jN;j++){if(NotInMemory[j]==1)//当访问的这个虚页不在内存时，显示将其调入内存后的详细内存信息printf(|%3d,MemoryStatus[i][j]);elseprintf(|%3c,32);//当访问的这个虚页在内存时，内存状态未发生改变，故无需再显示一遍。本例用空格代替，其中32是空格的ASCII码}}printf(\n************