fi.cpp

页面置换算法模拟设计,VC++写的(操作系统课程设计)

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<iostream.h>
#include<time.h>           
#define M 3        //物理块号
#define N 10        //页面个数
#define Myprintf printf("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|\n")      /*表格控制*/
typedef struct page
{
	int num;  /*记录页面号*/
	int time;   /*记录调入内存时间,即用时间来限制页面的置换*/
}Page;             /* 页面逻辑结构，结构为方便算法实现设计*/
Page unit[M];            /*内存单元数*/	
int buffer[M][N];     /*暂保存内存当前的状态：缓冲区*/
int queue[100];       /*记录调入队列*/
int K;             /*调入队列计数变量*/
int lacknumber=0;              //缺页的总数

             /*fifo函数*/
void fifoa(int duilie[N],int array[][N])
{
	int j=0;
	for(int i=0;i<M;i++)     //刚开始置换前M个空页面
		{
			if(i<M)
			{
				array[0][i]=duilie[i];
				cout<<"页面"<<duilie[i]<<"进入内存"<<endl;// 将最开始的那个几个置换出来，即大小与页面数相等的前面几个
				cout<<"缺页  此时页面内容为";
				for(int j=0;j<M;j++)
				{
					cout<<array[0][j]<<" ";
				}
				cout<<"(-1代表没有内容)"<<endl;
			}
			cout<<endl;
		}
		int h=0;
		for(i=M;i<N;i++)
		{
			int flag=0;
			for(int k=0;k<M;k++)
			{
				if(array[0][k]==duilie[i])//如果后面的几个数与之前的数有相等的，则标识它
				{
					flag=1;break;   //跳出离它最近的for循环
				}
			}  
			cout<<endl;
			if(flag==1)         //输出原来内存中的数
			{  
				cout<<"页面"<<duilie[i]<<"进入内存"<<endl;
				cout<<"此时页面内容为";
				for(int j=0;j<M;j++) 
				{
					cout<<array[0][j]<<" ";
				}
			}
			if(flag==0)    
			{
				int tem=array[0][h];    //array[0][h]的第一个元素
				array[0][h]=duilie[i];    //i开始为3，即duilie[i]为第四的一个元素，交换位置
				cout<<"页面"<<duilie[i]<<"进入内存"<<endl;
				cout<<"缺页页面"<<tem<<"被替换"<<endl;  //把array[0][h]的第一个元素付给tem后被置换出来
				cout<<"此时页面内容为";
				for(int j=0;j<M;j++)
				{
					cout<<array[0][j]<<" ";   //array[0][0]的数变为duilie[3]的数
				}
				cout<<endl;
				h++;
				lacknumber++;               //缺页数
				if(h==M)        //因为array[0][h]最多只能存放3个数
				{
					h=0;
				}
			}
		}
		cout<<endl;
        lacknumber=M+lacknumber;    //计算缺页率
		cout<<"缺页次数为：    "<<lacknumber<<endl;
		cout<<"缺页率 ：     "<<float(lacknumber)/float(N)<<endl;
}   
 

/*LRU函数调用，初始化内存单元、缓冲区*/

void Init(Page *unit,int buffer[M][N])
{
	int i,j;
	for(i=0;i<N;i++)
	{
		unit[i].num=-1;    //初始化全为-1，表示没有内容
		unit[i].time=N-i-1;  //从第一个开始依次赋时间，因为第一个先进入，所以呆在内存中的时间最久
	}                         //时间依次为11,10,9,8,7,6,5,4,3,2,1,0
	for(i=0;i<M;i++)
		for(j=0;j<N;j++)
			buffer[i][j]=-1;  //初始化缓冲区也为-1
}

/*取得在内存中停留最久的页面,默认状态下为最早调入的页面*/

int GetMax(Page *unit)
{
	int i;
	int max=-1;   
	int flag=0;
	for(i=0;i<M;i++)   
	{
		if(unit[i].time>max)    //若以第一个页面为例，则时间为11
		{
			max=unit[i].time;   //标记停留在内存中最久的页面，把11赋max
			flag=i;    //flag=0
		}
	}
	return flag;    //执行i=1时，因时间不满足条件，所以flag还是为0
}

int    Equation(int fold,Page *unit)   /*判断页面是否已在内存中*/
{
	int i;
	for(i=0;i<M;i++)
	{
		if (fold==unit[i].num)    //如果在内存中，就返回i的值
			return i;
	}
	return -1;    //不在就返回-1
}

/*LRU核心部分*/
void shixian(int fold,Page *unit)
{
	int i;
	int val;
	val=Equation(fold,unit);
	if (val>=0)               //目的是使页面按物理块的个数来存放
	{
		unit[val].time=0;     
		for(i=0;i<M;i++)
			if (i!=val)
				unit[i].time++;
	}
	else
	{
		queue[++K]=fold;     /*记录调入页面*/
		val=GetMax(unit);  
		unit[val].num=fold;
		unit[val].time=0; 
		for(i=0;i<M;i++)
			if (i!=val)
				unit[i].time++;
	}
}

void lru(int duilie[])
{
	int i;
	K=-1;
	Init(unit, buffer);
	for(i=0;i<N;i++)
	{
		shixian(duilie[i],unit);
		buffer[0][i]=duilie[i];     //把页面存入缓冲区
		/*记录当前的内存单元中的页面*/
		for(int j=0;j<M;j++)
			buffer[j][i]=unit[j].num;
	}
	/*结果输出*/
	cout<<"内存状态为："<<endl;
	Myprintf;
	for(int j=0;j<N;j++)
		printf("|%2d ",duilie[j]);
	cout<<endl;
	Myprintf;
	for(i=0;i<M;i++)
	{    
		for(j=0;j<N;j++)
		{
			if(buffer[i][j]==-1)
				printf("|%2c ",32);
			else
				printf("|%2d ",buffer[i][j]);
		}
		printf("|\n");
	}
	Myprintf;
	cout<<endl;
	cout<<"调入队列为:";
	for(i=0;i<K+1;i++)
          cout<<" "<<queue[i];
	cout<<endl;
	cout<<"缺页次数为："<<K+1<<endl;
		cout<<"缺页率："<<(float)(K+1)/N<<endl;
}


/*主程序*/
void main()
{
	cout<<"*************页 面 置 换 算 法*************"<<endl;
	cout<<"请选择:"<<endl;
	cout<<"              1: FIFO算法"<<endl;
	cout<<"              2: LRU算法"<<endl;
	cout<<"              0: 退出 "<<endl<<endl;
	int array[1][N];             //-1代表没有内容
	for(int y=0;y<2;y++)
		for(int x=0;x<20;x++)
		{
			array[y][x]=-1;
		}
		int duilie[N]={0};     //定义一个长度为20的队列	                        	  
		int select;
		while(select)
		{	
			cout<<"输入选择的序号:";
			cin>>select;
			if((select==0)||(select>2)) break;
			cout<<"下面是页面的访问顺序:"<<endl;    
			srand((unsigned)time(NULL));    //随机产生1~100的数
			for(int i=0;i<N;i++)                  
			{
				duilie[i]=rand()/1000+1; 
				printf("%d\n",duilie[i]);
			}
			switch(select)
			{
			case 0:
				break;
			case 1:
				cout<<"*****************应用FIFO算法*****************"<<endl<<endl;
				fifoa(duilie,array);             //调用FIFO函数
				cout<<"**********************************************"<<endl;
				break;
			case 2:
				cout<<"*****************应用LRU算法******************"<<endl<<endl;
				lru(duilie);                      //LRU
				cout<<"**********************************************"<<endl;
				break;
			default:
				 cout<<"警告:请输入正确序号!"<<endl;
				 break;

			}
		}
}