mqy.cpp

理解内存页面调度的机理

#include "stdio.h"
#include "math.h"

int pageflow[100];
int ap,pp;
int total_instruction;
int pcontrol[100];
struct contr
{
 int num;
 char note;
};

int input()
{
int i;
for(i=0;i<=100;i++)
{    
	scanf("%d",&pageflow[i]);
    if(pageflow[i]==0) break;
}
	return i;
}

void fifo()
{printf("\n#################################\n");
  printf("FIFO依次使用队列如下:\n");
  int m,n,mark;
  int point=0,diseffect=0;
  float rate;
  for(m=0;m<pp;m++)pcontrol[m]=0;
  for(n=0;n<total_instruction;n++)
  {
	  while(1)
	  {
	  mark=0;
	  for(m=0;m<pp;m++)
	  if(pcontrol[m]==pageflow[n]) mark=1;break;
	  }
	if(mark!=1)
	{
	   	if(point>=pp)diseffect++;
		pcontrol[point%pp]=pageflow[n];
		point++;
        
	}
	for(m=0;m<pp;m++)printf("%5d",pcontrol[m]);printf("\n");
  }	 
  printf("diseffect=%d\n",diseffect);
  rate=float(diseffect)/float(total_instruction);
  rate=(1-rate)*100;
  printf("FIFO命中率=%.3f%\n",rate);
  printf("#################################\n");
}

void lru()
{printf("\n#################################\n");
  printf("LRU依次使用队列如下:\n");
  int m,n,mark,lable[100],k;
  int point=0,diseffect=0;
  float rate;
  for(m=0;m<pp;m++){pcontrol[m]=0;lable[m]=0;}
   for(n=0;n<total_instruction;n++)
   {  
	  mark=0;
		  for(m=0;m<pp;m++)
			  if(pcontrol[m]==pageflow[n]) {mark=1;lable[m]=n;}
     if(mark!=1)
	 {
		if(point<pp) 
		{
			pcontrol[point]=pageflow[n];
			lable[point]=n;
		    point++;
		} 
		else
		{  k=0;
		  for(m=0;m<pp;m++)
		  {
			  if(lable[k]>=lable[m]) k=m;
		  }
		  pcontrol[k]=pageflow[n];
		  lable[k]=n;
		  diseffect++;
		}
	}	
     for(m=0;m<pp;m++)printf("%5d",pcontrol[m]);printf("\n");
  }	 
  printf("diseffect=%d\n",diseffect);
  rate=float(diseffect)/float(total_instruction);
  rate=(1-rate)*100;
  printf("LRU命中率=%.3f%\n",rate);	
  printf("#################################\n");
}


void opt()
{printf("\n#################################\n");
  printf("OPT依次使用队列如下:\n");
  int m,n,mark,k=0,p;
  int point=0,diseffect=0;
  int lable[100];
  float rate;
  for(m=0;m<pp;m++)pcontrol[m]=0;
  for(n=0;n<total_instruction;n++)
  {	    mark=0;
	    for(m=0;m<pp;m++)
	    if(pcontrol[m]==pageflow[n]) mark=1;
    	if(mark!=1)
		{
	    	if(point<pp) 
			{	pcontrol[point]=pageflow[n];
		        point++;
			} 
		    else
			{	
				{
			   	 for(m=0;m<pp;m++) lable[m]=total_instruction;
			     k=total_instruction-1;
			    	while(k>n)
					{for(m=0;m<pp;m++)if(pcontrol[m]==pageflow[k])lable[m]=k;k--;}
				}
			  p=0;
			 for(m=0;m<pp;m++)
			      if(lable[p]<lable[m])p=m;
		     pcontrol[p]=pageflow[n];
			 diseffect++;
		}	}
		for(m=0;m<pp;m++)printf("%5d",pcontrol[m]);printf("\n");
  }
  printf("diseffect=%d\n",diseffect);
  rate=float(diseffect)/float(total_instruction);
  rate=(1-rate)*100;
  printf("OPT命中率=%.3f%\n",rate);	
  printf("#################################\n");
}

void clock()
{printf("\n#################################\n");
  printf("CLOCK依次使用队列如下:\n");
 int m,n,point=0,k,mark,diseffect=0;
 float rate;
 struct contr control[100];
 for(m=0;m<pp;m++) {control[m].num=0;control[m].note='^';}  
 for(n=0;n<total_instruction;n++)
  { 
	  mark=0;
	  for(m=0;m<pp;m++)
		  if(control[m].num==pageflow[n]) {control[m].note='*';mark=1;}
    if(mark!=1)
	{
		if(point<pp) 
		{
			control[point].num=pageflow[n];
			control[point].note='*';
		    point++;
		} 
		else
		{ 
				k=0;
				for(m=0;m<pp;m++)if(control[m].note=='^'&&k==0){control[m].num=pageflow[n];control[m].note='*';k++;}
					 if(k==0)				
					 {control[0].num=pageflow[n];control[0].note='*';
                     for(m=1;m<pp;m++)control[m].note='^';}
					 diseffect++;
		}
	}	
	for(m=0;m<pp;m++)printf("%5d%c",control[m].num,control[m].note);printf("\n");
  }	 
  printf("diseffect=%d\n",diseffect);
  rate=float(diseffect)/float(total_instruction);
  rate=(1-rate)*100;
  printf("CLOCK命中率=%.3f%\n",rate);
  printf("#################################\n");
}

void main()
{
 printf("enter the page num and frame num\n");
 scanf("%d%d",&ap,&pp);
 printf("pagenum is %d,frame num is %d\n",ap,pp);
 if(ap<=0||pp<=0) printf("num error\n");
 else if(ap<=pp) printf("page num<frame num\n");
 else printf("enter page flow(0 for end)\n");
 total_instruction= input();
	 fifo();
	 lru();
	 opt();
	 clock();
}