exp3.c

linux下操作系统习题

#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{
	short int pn,pfn,counter,time;
}pl_type;
pl_type pl[total_vp];
typedef struct pfc_struct{
	short int pn,pfn;
	struct pfc_struct *next;
}pfc_type;
pfc_type pfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;

short int diseffect;
short int page[total_instruction],offset[total_instruction];
void initialize(short int total_pf);
void FIFO(short int total_pf);
void LRU(short int total_pf);
void OPT(short int total_pf);
void LFU(short int total_pf);
void NUR(short int total_pf);

main()
{
	short int a[total_instruction],S,i;
	srand(getpid()*10);
	S=(float)319*rand()/2147483647+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()/2147483647;
		a[i+3]=a[i+2]+1;
		S=(float)(318-a[i+2])*rand()/2147483647+a[i+2]+2;
	//printf("\n%d%d%d%d",a[i],a[i+1],a[i+2],a[i+3]);
	}
	for (i=0;i<total_instruction;i++)
	{
		page[i]=a[i]/10;
		offset[i]=a[i]%10;
		if(page[i]>=320&&page[i]<0)printf("###### error ######\n");
	}
	for (i=4;i<=total_vp;i++)
	{
		printf("%2d page frames   ",i);
		FIFO(i);
		LRU(i);
		OPT(i);
		LFU(i);
		NUR(i);	
		printf("\n");
	}
}
/****************************************/
void FIFO (short int total_pf)
{	short int i,j;
	pfc_type *p;
	initialize(total_pf);
	busypf_head=busypf_tail=NULL;
	for (i=0;i<total_instruction;i++)
	{
	if (pl[page[i]].pfn==INVALID)
	{diseffect++;
	if (freepf_head==NULL)
	{	p=busypf_head->next;
		pl[busypf_head->pn].pfn=INVALID;
		freepf_head=busypf_head;
		freepf_head->next=NULL;
		busypf_head=p;
	}
	p=freepf_head->next;
	freepf_head->next=NULL;
	freepf_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:%6.4f   ",1-(float)diseffect/total_instruction);
}
/****************************************/
void LRU(short int total_pf)

{	short int min,minj,i,j,present_time;
	
	initialize(total_pf);present_time=0;
	for(i=0;i<total_instruction;i++)
	{	if (pl[page[i]].pfn==INVALID)
		{ diseffect++;
		  if (freepf_head==NULL)
			{min=32767;
			for(j=0;j<total_vp;j++)
			if(min>pl[j].time&&pl[j].pfn!=INVALID)
			{min=pl[j].time;minj=j;}
			freepf_head=&pfc[pl[minj].pfn];
			pl[minj].pfn=INVALID;
			pl[minj].time=-1;
			freepf_head->next=NULL;
			}
		pl[page[i]].pfn=freepf_head->pfn;
		pl[page[i]].time=present_time;
		freepf_head=freepf_head->next;
		}
	else
	pl[page[i]].time=present_time;
	present_time++;
	}
printf("LRU:%6.4f  ",1-(float)diseffect/total_instruction);
}
/************************************/
void NUR(short int total_pf)

{short int i,j,dp,cont_flag,old_dp;
pfc_type *t;
dp=0;
initialize(total_pf);
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;
				}
			freepf_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:%6.4f  ",1-(float)diseffect/total_instruction);
}
/**************************************/
void OPT (short int total_pf)
{short int i,j,max,maxpage,d,dist[total_vp];
//pfc_type *t;

initialize(total_pf);
for(i=0;i<total_instruction;i++)
	{
	if (pl[page[i]].pfn==INVALID)
		{diseffect++;
		if(freepf_head==NULL)
			{for(j=0;j<total_vp;j++)
			if(pl[j].pfn!=INVALID) dist[j]=32767;else dist[j]=0;
			d=1;
			for(j=i+1;j<total_instruction;j++)
				{if (pl[page[j]].pfn!=INVALID)
				dist[page[j]]=d;
				d++;
				}
			max=-1;
			for(j=0;j<total_vp;j++)
			if(max<dist[j])
				{max=dist[j];maxpage=j;}
			freepf_head=&pfc[pl[maxpage].pfn];
			pl[maxpage].pfn=INVALID;
			freepf_head->next=NULL;
			
			}
		pl[page[i]].pfn=freepf_head->pfn;
		freepf_head=freepf_head->next;
		}
	}
printf("OPT:%6.4f  ",1-(float)diseffect/total_instruction);
}
/************************************/
void LFU(short int total_pf)
{short int i,j,min,minpage;

initialize(total_pf);
for(i=0;i<total_instruction;i++)
	{
	if(pl[page[i]].pfn==INVALID)
		{diseffect++;
		if (freepf_head==NULL)
			{min=32767;
			for(j=0;j<total_vp;j++)
				{if(min>pl[j].counter&&pl[j].pfn!=INVALID)
				{min=pl[j].counter;minpage=j;}
				pl[j].counter=0;
				}
			freepf_head=&pfc[pl[minpage].pfn];
			pl[minpage].pfn=INVALID;
			freepf_head->next=NULL;
			}
		pl[page[i]].pfn=freepf_head->pfn;
		freepf_head=freepf_head->next;
		}
	else
	pl[page[i]].counter++;
	}
printf("LFU:%6.4f  ",1-(float)diseffect/total_instruction);
}
/***********************************/
void initialize(short int total_pf)
//int total_pf;
{short int i;
diseffect=0;
for(i=0;i<total_vp;i++)
	{pl[i].pn=i;pl[i].pfn=INVALID;
	pl[i].counter=0;pl[i].time=-1;
	}
for(i=1;i<total_pf;i++)
	{pfc[i-1].next=&pfc[i];pfc[i-1].pfn=i-1;}
pfc[total_pf-1].next=NULL;pfc[total_pf-1].pfn=total_pf-1;
freepf_head=&pfc[0];
}