1.c

演示了linux下的常用页面置换算法（FIFO,LRU,OPT,LFU,NUR）

#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
#define true 1
#define false 0
#define invalid -1
#define nul 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[totla_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();
void opt();
void lfu();
void nur();
int main()
{
	int s,i;
	srand((int)getpid());
	s=(int)rand()%390;
	for(i=0;i<total_instruction;i+=1)	/*产生指令队列*/
	{
		a[i]=s;
		a[i+1]=a[i]+1;
		a[i+2]=(int)rand()%390;
		a[i+3]=a[i+2]+1;
		s=(int)rand()%390;
	}
	for(i=0;i<total_instruction;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");
	}
	return 0;
}
void fifo(total_pf)	/*first in first out algorithm*/
int total_pf;
{
	int i;
	pfc_type *p,*t;
	initialize(total_pf);
	busypf_head=busypf_tail=nul;
	for(i=0;i<total_instruction;i++)
	{
		if(pl[page[i]].pfn==invalid)
		{
			diseffect+=1;
			if(freepf_head==nul)
			{
				p=busypf_head->next;
				pl[busypf_head->pn].pfn=invalid;
				freepf_busypf_head;
				freepf_head->next=nul;
				busypf_head=p;
			}
		p=freepf_head->next;
		freepf_head->next=nul;
		freepf_head->pn=page[i];
		pl[page[i]].pfn=freepf_head->pfn;
		if(busypf_tail==nul)
			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(pl[page[i]].pfn==invalid) /*页面失效*/
		{
			diseffect++;
			if(freepf_head==nul) /*无空闲页面*/
			{
				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=nul;
			}
			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/320);
}
void nur(total_pf)
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==nul)
			{
				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=nul;
			}
			pl[page[i]].counter=1;
			if(i%clear_period==0)
				for(j=0;j<total_vp;j++)
					pl[j].counter=0;
		}
		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/320);
}
void opt(total_pf)	/*optimal replacement algorithm*/
int total_pf;
{
	int i,j,max,maxpage,d,dist[total_vp];
	pfc_type *t;
	initialize(total_pf);
	for(i=0;i<total_instruction;i++)
	{
		if(i=0;i<total_instruction;i++)
		{
			diseffect++;
			if(freepf_head==nul)
			{
				for(j=0;j<total_vp;j++)
					if(pl[j].pfn!=invalid)
						dist[j]=32767;
					else
						dist=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];
						freepf_head->next=nul;
						pl[maxpage].pfn=freepf_head->next;
				}
					pl[page[i]].pfn=freepf_head->pfn;
					freepf_head=freepf_head->next;
			}
		}
		printf("opt:%6.4f",1-(float)diseffect/320);
	}
}
void lfu(total_pf)	/*leat frequently used algorithm*/
int total_pf;
{
	int i,j,min,minpage;
	pfc_type *t;
	initialize(total_pf);
	for(i=0;i<total_instruction;i++)
	{
		if(pl[page[i]].pfn==invalid)
		{
			diseffect++;
			if(freepf_head==nul)
			{
				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=nul;
			}
			pl[page[i]].pfn=freepf_freepf_head->pfn;
			freepf_head=freepf_head->next;
		}
		else
			pl[page[i]].counter++;
	}
	printf("lfu:%6.4f",1-(float)diseffect/320);
}
void initialize(total_pf)
int total_pf;	/*用户进程内存页面数*/
{
	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=nul;pfc[total_pf-1].pfn=total_pf-1;
	freepf_head=&pfc[0];
}