osp1.c

内存管理的四种页面置换算法 FIFO LRU NUR OPT

#include<stdio.h>
#define NVisit 320  //访问次数
#define NPage 32   //进程页数
#define NPagecon 32 
#define Clearperiod 50 //访问次数清零周期

struct Pagecontrol
{
	int Pagenum;
	int own;
	int time; //在内存中的停留时间(FIFO,LRU),被访问的次数(NUR)
};

struct Page
{
	int Pagenum;
	int inmemory;   //是否在内存中
	int memorysite; //工作集页面数组下标,内存中位置
};

typedef struct Pagecontrol PC; //类型名与变量名不能相同!!
typedef struct Page P;


int visit[NVisit];
int effect=0;
float efrate; //命中率
int Distance[NPage]; //下一次访问该页的距离
int Showmemory[NPagecon+1][NVisit];
PC Pagecontrol[NPagecon];
P Page[NPage];

void initialize(int x)
{
    int nrand,i,j;
    srand(getpid()*10); 
	for(i=0;i<NVisit;i++) //初始化访问序列
	{
		nrand=rand()%NPage+1; //取1-NPage的随机数
		visit[i]=nrand;
	}

	for(i=0;i<x;i++) //初始化工作集
	{
		Pagecontrol[i].own=0;
		Pagecontrol[i].Pagenum=0;
		Pagecontrol[i].time=0;
	}

    for(i=0;i<NPage;i++)
	{
		Page[i].inmemory=0;
		Page[i].memorysite=0;
		Page[i].Pagenum=i+1; //1-NPage的页号
	}

	for(i=0;i<NPage;i++) //初始化距离数组
	{
		j=0;
		while(visit[j]!=i+1&&j<NVisit)
			j++;
		if(j<NVisit)
			Distance[i]=j+1;
		else
			Distance[i]=-1; //若访问序列中没有该页，将距离设为-1
	}

	effect=0;
}

void output(int x,FILE *f)
{
	int i,j;
	fprintf(f,"%s","访问序列  :");
    for(i=0,j=0;i<NVisit;i++)
		fprintf(f,"%3d",Showmemory[j][i]); 
	for(j=1;j<=x;j++)
	{
		fprintf(f,"%c",'\n');
	    fprintf(f,"%s%2d:","内存页面",j);
        for(i=0;i<NVisit;i++)
			fprintf(f,"%3d",Showmemory[j][i]);
	}
    fprintf(f,"%c",'\n');
	fprintf(f,"%c",'\n');
}


	
void FIFO(int x,FILE *f)
{
	int i,j,k,in;
	int	max=0;    //最大时间的下标
	int outpage;  //淘汰页号
	initialize(x);
	for(i=0;i<NVisit;i++)
	{
		in=Page[visit[i]-1].inmemory;
		if(in==1)
			effect++; //此处time统一加1，不改变大小关系，无需变化
			
		else
		{
			j=0;
			while(Pagecontrol[j].own==1&&j<x)
				j++;
			if(j<x)
			{
				for(k=0;k<j;k++)
					Pagecontrol[k].time++;

				Pagecontrol[j].own=1;
				Pagecontrol[j].Pagenum=visit[i];
				Page[visit[i]-1].inmemory=1;
				Page[visit[i]-1].memorysite=j;
			}
			else
			{
				for(j=0;j<x;j++)
					max=(Pagecontrol[j].time>Pagecontrol[max].time)?j:max;
				//淘汰停留时间最长且下标最小的页面

				outpage=Pagecontrol[max].Pagenum; //修改淘汰页页表信息
				Page[outpage-1].inmemory=0;
				Pagecontrol[max].Pagenum=visit[i];
				Pagecontrol[max].time=0;
				Page[visit[i]-1].inmemory=1;
				Page[visit[i]-1].memorysite=max;

				for(j=0;j<x;j++)
				{
					if(j==max)
						continue;
					else
						Pagecontrol[j].time++;
				}
			}
		}
		Showmemory[0][i]=visit[i];
        for(j=1;j<=x;j++)
			Showmemory[j][i]=Pagecontrol[j-1].Pagenum;

	}
	efrate=(float)effect/NVisit;
	output(x,f);
	printf("内存页面数:%d\n",x);
    printf("FIFO: %f",efrate);
	printf("\n");
}

void LRU(int x,FILE *f) //与FIFO类似，注意当命中时time归0
{
	int i,j,k,in;
	int	max=0;    //最大时间的下标
	int outpage;  //淘汰页号
	int insite;   //命中下标
	initialize(x);
	for(i=0;i<NVisit;i++)
	{
		in=Page[visit[i]-1].inmemory;
		if(in==1)
		{
			effect++; 
            insite=Page[visit[i]-1].memorysite;
			Pagecontrol[insite].time=0;
			for(j=0;j<x;j++)
				if(Pagecontrol[j].own==1&&j!=insite)
					Pagecontrol[j].time++;
		}
			
		else
		{
			j=0;
			while(Pagecontrol[j].own==1&&j<x)
				j++;
			if(j<x)
			{
				for(k=0;k<j;k++)
					Pagecontrol[k].time++;

				Pagecontrol[j].own=1;
				Pagecontrol[j].Pagenum=visit[i];
				Page[visit[i]-1].inmemory=1;
				Page[visit[i]-1].memorysite=j;
			}
			else
			{
				for(j=0;j<x;j++)
					max=(Pagecontrol[j].time>Pagecontrol[max].time)?j:max;
				// 淘汰最久未使用且下标最小的页面

				outpage=Pagecontrol[max].Pagenum; //修改淘汰页页表信息
				Page[outpage-1].inmemory=0;
				Pagecontrol[max].Pagenum=visit[i];
				Pagecontrol[max].time=0;
				Page[visit[i]-1].inmemory=1;
				Page[visit[i]-1].memorysite=max;

				for(j=0;j<x;j++)
				{
					if(j==max)
						continue;
					else
						Pagecontrol[j].time++;
				}
			}
		}

		Showmemory[0][i]=visit[i];
        for(j=1;j<=x;j++)
			Showmemory[j][i]=Pagecontrol[j-1].Pagenum;
	}
    output(x,f);
	efrate=(float)effect/NVisit;
	printf("LRU: %f",efrate);
	printf("\n");
}

void NUR(int x,FILE *f)
{
	int i,j,in;
	int	min=0;    //访问次数最少下标
	int outpage;  //淘汰页号
	int insite;   //命中下标
	initialize(x);
	for(i=0;i<NVisit;i++)
	{
		if(i%Clearperiod==0)
			for(j=0;j<x;j++)
				Pagecontrol[j].time=0;

		in=Page[visit[i]-1].inmemory;
		if(in==1)
		{
			effect++;
			insite=Page[visit[i]-1].memorysite;
			Pagecontrol[insite].time++;
		}
			
		else
		{
			j=0;
			while(Pagecontrol[j].own==1&&j<x)
				j++;
			if(j<x)
			{
				Pagecontrol[j].own=1;
				Pagecontrol[j].Pagenum=visit[i];
				Page[visit[i]-1].inmemory=1;
				Page[visit[i]-1].memorysite=j;
			}
			else
			{
				for(j=0;j<x;j++)
					min=(Pagecontrol[j].time<Pagecontrol[min].time)?j:min;
				//淘汰访问次数最少且下标最小的页面

				outpage=Pagecontrol[min].Pagenum; //修改淘汰页页表信息
				Page[outpage-1].inmemory=0;
				Pagecontrol[min].Pagenum=visit[i];
				Pagecontrol[min].time=0;
				Page[visit[i]-1].inmemory=1;
				Page[visit[i]-1].memorysite=min;

			}
		}

		Showmemory[0][i]=visit[i];
        for(j=1;j<=x;j++)
			Showmemory[j][i]=Pagecontrol[j-1].Pagenum;
	}
    output(x,f);
	efrate=(float)effect/NVisit;
	printf("NUR: %f",efrate);
	printf("\n");
}

void Renewdistance(int d) //更新下一次访问的距离
{
	int i,j;
	for(i=0;i<NPage;i++)
	{
		Distance[i]--;
		if(Distance[i]==0)
		{
			j=d+1;
			while(visit[j]!=i+1&&j<NVisit)
				j++;
			if(j<NVisit)
				Distance[i]=j-d;
			else
				Distance[i]=-1;
		}
	}
}


void OPT(int x,FILE *f)
{
	int i,j,in;
	int max=0; //最大距离页的工作集下标
	int outpage;
	initialize(x);
	for(i=0;i<NVisit;i++)
	{
		in=Page[visit[i]-1].inmemory;
		if(in==1)
		{
			effect++;
			Renewdistance(i);
		}
			
		else
		{
			j=0;
			while(Pagecontrol[j].own==1&&j<x)
				j++;
			if(j<x)
			{

				Pagecontrol[j].own=1;
				Pagecontrol[j].Pagenum=visit[i];
				Page[visit[i]-1].inmemory=1;
				Page[visit[i]-1].memorysite=j;
				Renewdistance(i);
			}
			else
			{
				for(j=0;j<x;j++)
				{
					if(Distance[Pagecontrol[j].Pagenum-1]<0)
					{
						max=j; //若有距离为负的页面直接淘汰
						break;
					}
					else //淘汰访问距离最长且下标最小的页面
					    max=(Distance[Pagecontrol[j].Pagenum-1]>Distance[Pagecontrol[max].Pagenum-1])?j:max;
				}

				outpage=Pagecontrol[max].Pagenum; //修改淘汰页页表信息
				Page[outpage-1].inmemory=0;
				Pagecontrol[max].Pagenum=visit[i];
				Pagecontrol[max].time=0;
				Page[visit[i]-1].inmemory=1;
				Page[visit[i]-1].memorysite=max;

				Renewdistance(i);
			}
		}

		Showmemory[0][i]=visit[i];
        for(j=1;j<=x;j++)
			Showmemory[j][i]=Pagecontrol[j-1].Pagenum;
	}
    output(x,f);
	efrate=(float)effect/NVisit;
	printf("OPT: %f",efrate);
	printf("\n");
	printf("\n");
}



main()
{
	int x;//内存中页面数 变量循环
	FILE *ffifo;
	FILE *flru;
	FILE *fnur;
	FILE *fopt;
	ffifo=fopen("fifo.txt","w");//注意权限w会自动创建文件 r+不能自动创建文件，需要自己建立
	flru=fopen("lru.txt","w");
	fnur=fopen("nur.txt","w");
	fopt=fopen("opt.txt","w");
	for(x=4;x<=32;x++)
	{
	    FIFO(x,ffifo);
	    LRU(x,flru);
	    NUR(x,fnur);
	    OPT(x,fopt);
	}

}

//LUNIX下的文档文件在ftp://202.112.113.88下				
//gcc -o osp1 osp1.c 生成名为osp1的执行文件