虚拟存储器.txt

关与操作系统的c模拟程序

#define TRUE 1  
#define FALSE 0
#define INVALID -1
#define null 0

#define total_instruction 320  /*指令流长*/
#define total_vp 32            /*虚页长*/
#define clear_period 50        /*清零周期*/

typedef struct                 /*页面结构*/
 { int pn,pfn,counter,time;
 }pl_type;
pl_type pl[total_vp];          /*页面结构数组*/
struct pfc_struct              /*页面控制结构*/
 { int pn,pfn;
   struct pfc_struct *next;
 };
 typedef struct pfc_struct pfc_type;
 pfc_type pfc[total_vp],**freepf_head,*busypf_head,**busypf_tail;

 int diseffect,  a[total_instruction];
 int page[total_instruction],  offset[total_instruction];
 void initatialize();
 void FIFO();
 void LRU();
 void OPT();
 void LFU();
 void NUR(); 
 
main()
 { int s,i,j;
   s=(float)319*rand()/32767+1;
   for(i=0;i<total_instruction;i+=4) /*产生指令队列*/
   { a[i]=s;                         /*任选一指令访问点*/
     a[i+1]=a[i]+1;                  /*顺序执行一条指令*/
     a[i+2]=(float)a[i]*rand()/32767;/*执行前地址指令m’*/
     a[i+3]=a[i+2]+1;                /*执行后地址指令*/
     s=(float)rand()*(318-a[i+2])/32767+a[i+2]+2;
   }
   for(i=0;i<total_instructionn;i++) /*将指令序列变换成页地址流*/
   { page[i]=a[i]/10;
     offset[i]=a[i]%10;
   }
   for(i=4;i<=32;i++)                /*用户内存工作区从4个页面到32个页面*/
   { printf("%2d page frames",i);
     FIFO(i);
     LRU(i);
     OPT(i);
     LFU(i);
     NUR(i);
     printf("\n");
   }
 }

/*以下为FIFO算法源代码*/
 void FIFO(int total_pf)           /*total_pf为用户进程的内存页面数*/
 { int i,j;
   pfc_type *p,*t;
   initialize(total_pf);           /*初始化相关页面控制用数据结构*/
   busypf_head=busypf_tail=NULL;   /*忙页面队列头、队列尾链接*/
   for(i=0;i<total_instruction;i++)
   {if(pl[page[i]].pfn==INVALID)    /*页面失效*/
    {diseffect++;                   /*失效次数*/
     if(freef_head==NULL)           /*无空闲页面*/
      {p=busypf_head->next;
       pl[busypf_head->pn].pfn=INVALID;
       freef_head=busypf_head;          /*释放忙页面队列中的第一个页面*/
       freef_head->next=NULL;
       busypf_head=p;
      }
      p=freef_head->next;               /*按FIFO方式调新页面入内存页面*/
      freef_head->next=NULL;                      
      freef_head->pn=page[i];
      pl[page[i]].pfn=freepf_head->pfn;
      if(busypf_tail==NULL)
       busypf_head=busypf_tail=freepf_head;
      else
       {busypf_tail->next=freepf_head;
	busypf_tail=freepf_head;
       }
      freepf_head=p;
     }
    }
    printf("FIFO:%.4f",1-(float)diseffect/320);
   }

/*LRU算法略*/

 /*以下为NUR算法源代码*/
 void NUR(int total_pf)
   { int i,j,dp,cont_flag,old_dp;
     pfc_type *t;
     initialize(total_pf);
     dp=0;
     for(i=0;i<total_instruction;i++)
      {if(pl[page[i]].pfn==INVALID)      /*页面失效*/
       {diseffect++;
	if(freepf_head==NULL)                /*无空闲页面*/
	 {cont_flag=TRUE;old_dp=dp;
	  while(cont_flag)
	   if(pl[dp].counter==0&&pl[dp].pfn!=INVALID)
	    cont_flag=FALSE;
	   else
	    {dp++;if(dp==total_vp) dp=0;
	     if(dp==old_dp)
	      for(j=0;j<total_vp;j++) pl[j].counter=0;
	    }
	    freept_head=&pfc[pl[dp].pfn];
	    pl[dp].pfn=INVALID;
	    freepf_head->next=NULL;
	   }
	   pl[page[i]].pfn=freepf_head->pfn;
	   freepf_head=freepf_head->next;
	  }
	  else pl[page[i]].counter=1;
	  if(i%clear_period==0)
	   for(j=0;j<total_vp;j++)
	    pl[j].counter=0;
	 }
	 printf("NUR:%.4f",1-(float)diseffect/320);
	}
/*OPT算法略*/