页面替换算法（程序一演示替换过程）.cpp

这是一个C语言实现的存储器管理中页面替换算法的模拟程序

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#define F 5
#define maximum 12

int M[F];
int P[maximum];

int best(){
	int i,j,t,sign;
	int flag;
	int next=F;
	int N[F];
	int times=0;
	printf("最佳替换算法\n");
	for(i=0;i<F;i++)
			printf("%d",M[i]);
	printf("\t");
	for(i=0;i<5000000;i++);//为了显示效果的可观性，这里进行了输出延时，以下同理
	for(i=0;i<F;i++)
		N[i]=0;
	while(next<maximum){
		flag=0;
		for(i=0;i<F;i++)
			if (M[i]==P[next]) flag=1;
		if(flag==1) next++;
		else{
				for(j=0;j<F;j++)
					for(i=next;i<maximum;i++){
						if(M[j]!=P[i]) N[j]++;
						else break;
					}
                t=-1;
				for(i=0;i<F;i++)
					if(N[i]>t){
						t=N[i];
						sign=i;
					}
				M[sign]=P[next];
				next++;
				times++;
			}
		for(i=0;i<F;i++)
			printf("%d",M[i]);
		for(i=0;i<50000000;i++);
		printf("\t");
	}
	return times;
}//最佳替换算法

int random(){
	int i;
	int flag;
	int next=F;
	int times=0;
	printf("\n随机替换算法\n");
	for(i=0;i<F;i++)
			printf("%d",M[i]);
	printf("\t");
	for(i=0;i<50000000;i++);
	srand((unsigned)time(NULL));
	while(next<maximum){
		flag=0;
		for(i=0;i<F;i++)
			if (M[i]==P[next]) flag=1;
		if(flag==1) next++;
		else{
				i=rand()%F;
				M[i]=P[next];
				next++;
				times++;
			}
		for(i=0;i<F;i++)
			printf("%d",M[i]);
		for(i=0;i<50000000;i++);
		printf("\t");
	}
	return times;
}//随机替换算法



int FIFO(){
	int i;
	int flag;
	int point=0;
	int next=F;
	int times=0;
	printf("\nFIFO算法\n");
	for(i=0;i<F;i++)
			printf("%d",M[i]);
	printf("\t");
	for(i=0;i<50000000;i++);
	while(next<maximum){
		flag=0;
		for(i=0;i<F;i++)
			if (M[i]==P[next]) flag=1;
		if(flag==1) next++;
		else{
				M[point]=P[next];
				next++;
				point=++point%F;
				times++;
			}
		for(i=0;i<F;i++)
			printf("%d",M[i]);
		for(i=0;i<50000000;i++);
		printf("\t");

	}
	return times;
}//FIFO算法



int LRU(){
	int i,j,r;
	int flag;
	int next=F;
	int index[F];
	int times=0;
	printf("\nLRU算法\n");
	for(i=0;i<F;i++)
			printf("%d",M[i]);
	printf("\t");
	for(i=0;i<50000000;i++);
	for(i=0;i<F;i++)
		index[i]=i;
	while(next<maximum){
		flag=0;
		for(i=0;i<F;i++)
			if (M[i]==P[next]){
				flag=1;
				break;}
			if(flag==1){
				next++;
			    r=index[i];
                for(j=i;j<F-1;j++)
					index[j]=index[j+1];
				index[F-1]=r;
			}
		else{
				r=index[0];
				M[r]=P[next];
				for(i=0;i<F-1;i++)
					index[i]=index[i+1];
				index[F-1]=r;
				next++;
				times++;
			}
		for(i=0;i<F;i++)
			printf("%d",M[i]);
		for(i=0;i<50000000;i++);
		printf("\t");
	}
	return times;
}//LRU算法


int CLOCK(){
	int i;
	int flag=0;
	int point;
	int next=F;
	int sign[F];
	int times=0;
	printf("\nCLOCK算法\n");
	for(i=0;i<F;i++)
			printf("%d",M[i]);
	printf("\t");
	for(i=0;i<50000000;i++);
	for(i=0;i<F;i++)
		sign[i]=0;
	while(next<maximum){
		flag=0;
		for(i=0;i<F;i++)
			if(M[i]==P[next]) flag=1;
		if(flag==1) next++;
		else{
				for(i=0;i<F;i++)
					if(sign[i]==0&&i>=point){
						M[i]=P[next];
						sign[i]=1;
						break;
					}
					else sign[i]=0;
				point=++point%F;
				next++;
				times++;
			}
		for(i=0;i<F;i++)
			printf("%d",M[i]);
		for(i=0;i<50000000;i++);
		printf("\t");
	}
	printf("\n");
	return times;
}//CLOCK算法


void generate(){
	int i;
	int count=0;
	int q,p=0,e=5;
	int m=2;
	int P_const=10;
	double r,t=0.5;
	while(count<maximum){
		for(i=0;i<m;i++){			
			q=rand()%e;
			P[count+i]=(p+q)%P_const;}
		r=double(rand()%100)/100;
		if(r<t) p=rand()%P_const;
		else p=(p+1)%P_const;
		count=count+m;
	}
}//引用串的产生

void main()
{
	int i,choice=1;
	int times[5];
	printf("本程序模拟内存为5祯;引用串长度为12(可以通过程序任意设定)\n");
	srand((unsigned)time(NULL));
	generate();//引用串的产生
	printf("\n模拟生成引用串:");
	for(i=0;i<maximum;i++)
		printf("%d",P[i]);
	printf("\n\n\n");
	printf("依次显示每次替换时物理内存中的内容\n\n");
	while(choice<=5){
	for(i=0;i<F;i++)
		M[i]=P[i];
	switch(choice){
	case 1:{times[0]=best();break;}//最佳替换算法
	case 2:{times[1]=random();break;}//随机替换算法
	case 3:{times[2]=FIFO();break;}//FIFO算法
	case 4:{times[3]=LRU();break;}//LRU算法
	case 5:{times[4]=CLOCK();break;}//CLOCK算法
	}
	choice++;
	}
	printf("\n五种算法的页面替换次数:\n\n最佳  随机  FIFO  LRU  CLOCK\n");
	for(i=0;i<5;i++)
		printf("%d     ",times[i]);
	printf("\n\n\n");
}