/* 內(nèi)存管理 */

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

#define total_instruction 320   /* 指令流長(zhǎng) */
#define total_vp 32             /* 虛頁長(zhǎng) */

typedef struct{
	int pn,pfn,counter,time;
}p1_type;
p1_type p1[total_vp];         /* 頁面結(jié)構(gòu)數(shù)組 */

struct pfc_struct{            /* 頁面控制結(jié)構(gòu) */
	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 initialize();
void FIFO();
void LRU();

main()
{
	int S,i,j;
	srand(getpid()*10);
	S=rand()%319; 
	for (i=0;i<total_instruction;i+=4)	
	{
		a[i]=S;
		a[i+1]=a[i]+1;
		a[i+2]=rand()%(a[i]+1);
		a[i+3]=a[i+2]+1;
		/* S=rand()*(318-a[i+2])%319+a[i+2]+2; */
		S=rand()%(319-a[i+2])+a[i+2]+1; 
	}
	for (i=0;i<total_instruction;i++)	
	{
		page[i]=a[i]/10;
		offset[i]=a[i]%10;
	}
	for (i=4;i<=32;i++)
	{
		printf("%2d page frames",i);	
		FIFO(i);
		LRU(i);
		printf("\n");
	}	
}

void FIFO(total_pf)
int 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 (p1[page[i]].pfn==INVALID)
		{
			diseffect+=1;
			if (freepf_head==NULL)
			{
				p=busypf_head->next;
				p1[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];
			p1[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/320);
}

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

void initialize(total_pf)
int total_pf;
{
	int i;
	diseffect=0;
	for (i=0;i<total_vp;i++)
	{
		p1[i].pn=i;
		p1[i].pfn=INVALID;	
		p1[i].counter=0;
		p1[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];
}