ww.cpp

页面置换算法 设计一个虚拟存储区和内存工作区,编程序演示FIFO、LRU、OPT算法的具体实现过程,并计算访问命中率.

#include<stdio.h> 
#include<conio.h> 
  
#define M 3 
#define N 20 
#define Myprintf printf("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|\n")	/*表格控制*/ 
typedef struct page 
{ 
	int num;	/*记录页面号*/ 
	int time;	/*记录调入内存时间*/
	int hao;
}Page;			/* 页面逻辑结构，结构为方便算法实现设计*/ 
  
Page b[M];		/*内存单元数*/ 
int c[M][N];	/*暂保存内存当前的状态：缓冲区*/ 
int queue[100];	/*记录调入队列*/ 
int K;		/*调入队列计数变量*/ 
/*初始化内存单元、缓冲区*/ 
void Init(Page *b,int c[M][N]) 
{ 
	int i,j; 
	for(i=0;i<N;i++) 
	{ 
		b[i].num=-1; 
		b[i].time=N-i-1; 
		b[i].hao=-1; 
	} 
	for(i=0;i<M;i++) 
		for(j=0;j<N;j++) 
			c[i][j]=-1; 
} 
  
/*取得在内存中停留最久的页面,默认状态下为最早调入的页面*/ 
int GetMax(Page *b) 
{ 
	int i; 
	int max=-1; 
	int tag=0; 
	for(i=0;i<M;i++) 
	{ 
		if(b[i].time>max) 
		{ 
			max=b[i].time; 
			tag=i; 
		} 
	} 
	return tag; 
} 
int GetOpt(page *b,int i)
{
	int tag=0;
	int max=-1;
	int j;
	int e=100;
	int a[N]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
	for (j=0;j<M;j++)
	{ 
		if(b[j].num==-1)
			tag=j;
		else
		{
			for(j=0;j<M;j++)
			{ for(;i<N;i++)
				{
					if(b[j].num==a[i])
						b[j].hao=i;
					else
					{
						b[j].hao=e;
						e--;
					}
				}
			}
		}
		if(b[j].hao>max)
		{
			max=b[j].hao;
			tag=j;
		}
	}
	return tag;
}
  
/*判断页面是否已在内存中*/ 
int	Equation(int fold,Page *b) 
{ 
	int i; 
	for(i=0;i<M;i++) 
	{ 
		if (fold==b[i].num) 
			return i; 
	} 
	return -1; 
} 
/*LRU核心部分*/ 
void Lru(int fold,Page *b) 
{ 
	int i; 
	int val; 
	val=Equation(fold,b); 
	if (val>=0) 
	{ 
		b[val].time=0; 
		for(i=0;i<M;i++) 
			if (i!=val) 
				b[i].time++; 
	} 
	else 
	{ 
		queue[++K]=fold;/*记录调入页面*/ 
		val=GetMax(b); 
		b[val].num=fold; 
		b[val].time=0; 
		for(i=0;i<M;i++) 
			if (i!=val) 
				b[i].time++; 
	} 
} 
/*FIFO核心部分*/ 
void Fifo(int fold,Page *b) 
{ 
	int i; 
	int val; 
	val=Equation(fold,b); 
	if (val<0)  
	{
		queue[++K]=fold;/*记录调入页面*/ 
		val=GetMax(b); 
		b[val].num=fold; 
		b[val].time=0; 
		for(i=0;i<M;i++) 
				b[i].time++; 
	} 
}
/*OPT核心部分*/
void Opt(int fold,page *b,int i)
{
	int val;
	val=Equation(fold,b); 
	if(val<0)
	{
	queue[++K]=fold;
		val=GetOpt(b,i);
		b[val].num=fold;
	}
} 

  
/*主程序*/ 
void main() 
{ 
	int a[N]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1}; 
	int i,j;
	char q;
start: 
	K=-1; 
	Init(b, c); 
	printf("请选择置换算法:f? l? o?\n");
	scanf("%s",&q);
    for(i=0;i<N;i++) 
	{ 	if(q=='f')
		Fifo(a[i],b); 
	else if(q=='l')
		Lru(a[i],b);
	else if(q=='o')
		Opt(a[i],b,i);
	c[0][i]=a[i];
	/*记录当前的内存单元中的页面*/ 
		for(j=0;j<M;j++) 
			c[j][i]=b[j].num; 
	} 
	/*结果输出*/ 
	printf("内存状态为：\n"); 
	Myprintf; 
	for(j=0;j<N;j++) 
		printf("|%2d ",a[j]); 
	printf("|\n"); 
	Myprintf; 
	for(i=0;i<M;i++) 
	{	for(j=0;j<N;j++) 
		{ 
		if(c[i][j]==-1) 
			printf("|%2c ",32); 
		else 
			printf("|%2d ",c[i][j]); 
		} 
		printf("|\n"); 
	} 
	Myprintf; 
	printf("\n调入队列为:"); 
	for(i=0;i<K+1;i++) 
		printf("%3d",queue[i]); 
	printf("\n缺页次数为：%6d\n缺页率：%16.6f",K+1,(float)(K+1)/N); 
	printf("\nAre you continuing!\ty?\n"); 
	if(getche()=='y') 
		goto start; 
}