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

实验编号４名称页面置换算法模拟实验目的通过请求页式存储管理中页面置换算法模拟设计，以便：1、了解虚拟存储技术的特点2、掌握请求页式存储管理中页面置换算法实验内容与步骤设计一个虚拟存储区和内存工作区，并使用FIFO和LRU算法计算访问命中率。程序设计先用srand()函数和rand()函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算相应的命中率。程序1#includewindows.h//Windows版，随机函数需要，GetCurrentProcessId()需要//#includestdlib.h//Linux版，随机函数srand和rand需要#includestdio.h//printf()需要#defineTRUE1#defineFALSE0#defineINVALID-1#defineNULL0#definetotal_instruction320//共320条指令#definetotal_vp32//虚存页共32页#defineclear_period50//访问次数清零周期typedefstruct{//定义页表结构类型（页面映射表PMT）intpn,pfn,counter,time;//页号、页框号(块号)、一个周期内访问该页面的次数、访问时间}PMT;PMTpmt[32];typedefstructpfc_struct{//页面控制结构intpn,pfn;structpfc_struct*next;}pfc_type;pfc_typepfc[32];pfc_type*freepf_head,*busypf_head,*busypf_tail;//空闲页头指针，忙页头指针，忙页尾指针intNoPageCount;//缺页次数inta[total_instruction];//指令流数组intpage[total_instruction],offset[total_instruction];//每条指令的页和页内偏移voidinitialize(int);voidFIFO(int);//先进先出voidLRU(int);//最近最久未使用voidNRU(int);//最近最不经常使用/****************************************************************************main()*****************************************************************************/voidmain(){inti,s;//srand(10*getpid());//用进程号作为初始化随机数队列的种子//Linux版srand(10*GetCurrentProcessId());//用进程号作为初始化随机数的种子//Windows版s=rand()%320;//在[0，319]的指令地址之间随机选取一起点mfor(i=0;itotal_instruction;i+=4){//产生指令队列if(s0||s319){printf(wheni==%d,error,s==%d\n,i,s);exit(0);}a[i]=s;//任意选一指令访问点m。（将随机数作为指令地址m）a[i+1]=a[i]+1;//顺序执行下一条指令a[i+2]=rand()%(s+2);//在[0，m+1]的前地址之间随机选取一地址，记为m'a[i+3]=a[i+2]+1;//顺序执行一条指令s=a[i+2]+(int)rand()%(320-a[i+2]);//在[m'，319]的指令地址之间随机选取一起点mif((a[i+2]318)||(s319))printf(a[%d+2,anumberwhichis:%dands=%d\n,i,a[i+2],s);}for(i=0;itotal_instruction;i++){//将指令序列变成页地址流page[i]=a[i]/10;offset[i]=a[i]%10;}for(i=4;i=32;i++){//内存块分别为4块、5块、...32块时的命中率printf(%2dpageframes,i);FIFO(i);//计算用FIFO置换时，有i个内存块时的命中率LRU(i);//最近最久未使用NRU(i);//最近最不经常使用printf(\n);}}/***************************************************************************initialize()形参：内存块数功能：初始化*****************************************************************************/voidinitialize(inttotal_pf)//初始化相关数据结构，形参total_pf是用户进程的内存页面数{inti;NoPageCount=0;//缺页次数，初始化为0for(i=0;itotal_vp;i++){pmt[i].pn=i;//填逻辑页号pmt[i].pfn=INVALID;//物理页面号为-1pmt[i].counter=0;//置页面控制结构中的访问次数为0pmt[i].time=-1;//置页面控制结构中的时间为-1}for(i=0;itotal_pf-1;i++){//建立pfc[i-1]和pfc[i]之间的连接pfc[i].next=&pfc[i+1];pfc[i].pfn=i;}pfc[total_pf-1].next=NULL;pfc[total_pf-1].pfn=total_pf-1;freepf_head=&pfc[0];//页面队列的头指针为pfc[0]}/*****************************************************************************FIFO算法形参：内存块数输出：命中率*****************************************************************************/voidFIFO(inttotal_pf)//形参total_pf是用户进程的内存页面数{inti;pfc_type*p;initialize(total_pf);//初始化相关数据结构busypf_head=busypf_tail=NULL;for(i=0;itotal_instruction;i++){//访问每条指令if(pmt[page[i]].pfn==INVALID){//缺页NoPageCount+=1;//失效(缺页)次数增1if(freepf_head==NULL){//无空闲页面p=busypf_head-next;pmt[busypf_head-pn].pfn=INVALID;freepf_head=busypf_head;//释放忙页面队列的第一个页面freepf_head-next=NULL;busypf_head=p;}p=freepf_head-next;//按FIFO方式调新页面入内存freepf_head-next=NULL;freepf_head-pn=page[i];pmt[page[i]].pfn=freepf_head-pfn;if(busypf_tail==NULL)busypf_head=busypf_tail=freepf_head;else{busypf_tail-next=freepf_head;//free页面减少一个busypf_tail=freepf_head;}freepf_head=p;}}printf(FIFO:%6.4f,1-(float)NoPageCount/320);}/****************************************************************************LRU算法（最近最久未使用）形参：内存块数输出：命中率*****************************************************************************/voidLRU(inttotal_pf)//形参total_pf是给用户进程的内存块数{intmin,minj,i,j,present_time;initialize(total_pf);present_time=0;for(i=0;itotal_instruction;i++){if(pmt[page[i]].pfn==INVALID){//页面失效NoPageCount++;if(freepf_head==NULL){//无空闲页面min=32767;for(j=0;jtotal_vp;j++)//找出time的最小值if(minpmt[j].time&&pmt[j].pfn!=INVALID){min=pmt[j].time;minj=j;}freepf_head=&pfc[pmt[minj].pfn];//腾出一个单元pmt[minj].pfn=INVALID;pmt[minj].time=-1;freepf_head-next=NULL;}pmt[page[i]].pfn=freepf_head-pfn;//有空闲页面，改为有效pmt[page[i]].time=present_time;freepf_head=freepf_head-next;//减少一个free页面}elsepmt[page[i]].time=present_time;//更新该页面的访问时间（并非真的时间，而是循环次数，每执行一条指令，时间加1）present_time++;//当前时间加1}printf(LRU:%6.4f,1-(float)NoPageCount/320);}/****************************************************************************NRU算法（最近最不经常使用）形参：内存块数输出：命中率*****************************************************************************/voidNRU(inttotal_pf){inti,j,dp,cont_flag,old_dp;initialize(total_pf);dp=0;for(i=0;itotal_instruction;i++){if(pmt[page[i]].pfn==INVALID){//缺页NoPageCount++;if(freepf_head==NULL){//无空闲页面cont_flag=TRUE;old_dp=dp;while(cont_flag)if(pmt[dp].counter==0&&pmt[dp].pfn!=INVALID)cont_flag=FALSE;else{dp++;if(dp==total_vp)dp=0;if(dp==old_dp)for(j=0;jtotal_vp;j++)pmt[j].counter=0;}freepf_head=&pfc[pmt[dp].pfn];pmt[dp].pfn=INVALID;freepf_head-next=NULL;}pmt[page[i]].pfn=freepf_head-pfn;freepf_head=freepf_head-next;}elsepmt[page[i]].counter=1;if(i%clear_period==0)for(j=0;jtotal_vp;j++)pmt[j].counter=0;}printf(NUR:%6.4f,1-