实验二 fifo与lru更新cache.cpp

计算机体系结构实验程序

/*
   FIFO算法：
   用数组模拟队列，使得第一个内存块中永远是最久未使用的页面，而下标最大的内存块永远是刚刚进入的页面。
   发生页面中断时总是替换出第一个内存块中的页面，同时调整队列，似的下标最大的是刚刚置换进来的页面。              

   LRU算法：把用数组模拟的内存块看做一个栈，页面按时间顺序压如栈中。
   如果被访问的页在栈中，则从栈中移出页面，压入栈顶。
   这样栈底记录离当前时间最近的一段时间内最久没有使用过的页面。发生页面中断时置换出栈底页面。            
*/

//#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#include <time.h>
#include <windows.h>
#include <conio.h>


#define PageLayoutNumber 10  //页面数
#define PhysicsBlock  7      //内存分配给进程的最大物理块数
#define PageNumber 20        //页面串长度

typedef struct paga_layout
{
	int number;              //页面号	
}PAGE;

PAGE page[PageNumber];       //页面引用串
PAGE MemPage[PhysicsBlock];  //内存物理块
int input[PageNumber];
int count[4];

void MyCase(int num,int PN,int PB,PAGE * MemPage,PAGE* page)
{	
	for(int i=num;i<=PB-2;i++)
		MemPage[i].number=MemPage[i+1].number;
	MemPage[PB-1].number=page[PN].number;
}

void intial(PAGE *page,int *input)  //页面初始化
{ 
	int i;
	for(i=0;i<PageNumber;i++)
		page[i].number=input[i];
}

int CheckMem(PAGE e,int MyPhysicsBlock )  //检测内存块，确定当前访问页面e是否在内存
{                                         //若在则返回内存块号,否则返回-1                      
	int tmp,flag;
	flag=-1;
	for(tmp=0;tmp<MyPhysicsBlock;)
	{//检测内存块号与当前访问页面是否匹配
		if(MemPage[tmp].number==e.number)
		{
			flag=tmp;
			break;
		}
		else
			tmp++;
	}
	return flag;
}

void display()
{
	//getche();
	getch();
}               

void Print()//输出页面引用串
{
	int tmp;
	cout<<endl;
	cout<<"                    页面引用串为:"<<endl;
	cout<<"━━━━━━━━━━━━━━━━━━━━"<<endl;
	for(tmp=0;tmp<PageNumber;tmp++)
	{
		cout<<input[tmp]<<" ";
	}
	cout<<endl;
	cout<<"━━━━━━━━━━━━━━━━━━━━"<<endl;
}

void ProRondPage()  //随机页面生成函数
{
	int i,tmp;
	input[0]=rand()%PageLayoutNumber;  //第一个页面
	i=1;
	while(1)  //第二个页面
	{ 
		tmp=rand()%PageLayoutNumber;
		if(tmp==input[0])
			continue;
		else
		{
			input[i]=tmp;
			i=i+1;
			break;
		}
	}
	while(1)  //第三个页面
	{ 
		tmp=rand()%PageLayoutNumber;
		if(tmp==input[0]||tmp==input[1])
			continue;
		else
		{
			input[i]=tmp;
			break;
		}
	}
	for(i=3;i<PageNumber;i++)  //以后的页面
	{
		input[i]=rand()%PageLayoutNumber;
	}
}

void LastPrint()
{
	system("CLS");
	Print();
	
	cout<<"━━━━━━━━━━━━━━━━━"<<endl;
	cout<<"             FIFO算法：";
	cout<<endl;
	cout<<"         缺页次数为："<<count[1]<<endl;
	cout<<"         缺页率为："<<(float)count[1]/PageNumber*100<<"%"<<endl;
	cout<<"━━━━━━━━━━━━━━━━━"<<endl;
	
	cout<<"━━━━━━━━━━━━━━━━━"<<endl;
	cout<<"             LRU算法：";
	cout<<endl;
	cout<<"         缺页次数为："<<count[2]<<endl;
	cout<<"         缺页率为："<<(float)count[2]/PageNumber*100<<"%"<<endl;
	cout<<"━━━━━━━━━━━━━━━━━"<<endl;
	
	
}

void FIFOPrintM(int MyPhysicsBlock)
{
	int k;
	cout<<"当前内存(页面号):";
	for(k=0;k<MyPhysicsBlock;k++)
		cout<<MemPage[k].number<<" ";
}

void FIFt(int MyPhysicsBlock)  //FIFO算法
{
	int i,j,tmp;
	count[1]=0;
	Print();
	cout<<endl;
	cout<<"━━━━━━━━━━━━━━━━━━━"<<endl;
	cout<<"FIFO算法过程:"<<endl;
	for(i=0;i<MyPhysicsBlock;i++)  //数组模拟队列，下标为0的页面是最先进来的
	{
		MemPage[i].number=page[i].number;
	}
	for(i=MyPhysicsBlock;i<PageNumber;i++)
	{ 
		cout<<endl;
		system("CLS");
        Print();
		cout<<endl;
		cout<<"━━━━━━━━━━━━━━━━━━━"<<endl;
		cout<<"     FIFO算法过程："<<endl;
		FIFOPrintM(MyPhysicsBlock);
		cout<<endl;
		cout<<"当前访问"<<page[i].number<<"页面"<<endl;
		tmp=CheckMem(page[i],MyPhysicsBlock);
		if(tmp!=-1)//当前页面已存在
		{
			cout<<"页面已在内存"<<endl;
			cout<<"━━━━━━━━━━━━━━━━━━━"<<endl;
			display();
		}
		else//如果不存在，换出内存块下表为0中的页面
		{
			count[1]++;
			cout<<"页面中断"<<endl;
			cout<<"页面"<<page[i].number<<"置换出页面"<<MemPage[0].number<<endl;
			for(j=0;j<MyPhysicsBlock;j++)  //页面置换，换出最早进入内存的页面
			{
				MemPage[j].number=MemPage[j+1].number;
			}
			MemPage[j-1].number=page[i].number;
			cout<<"━━━━━━━━━━━━━━━━━━━"<<endl;
			display();
		}
		
	} 
}

void LRU(int MyPhysicsBlock )  //LRU算法
{
	int i,j,tmp;
	count[2]=0;
	Print();
	cout<<endl;
	cout<<"━━━━━━━━━━━━━━━━━━━━"<<endl;
	cout<<"LRU算法过程:"<<endl;
	for(i=0;i<MyPhysicsBlock;i++)//数组模拟栈，下标为0的物理块为栈底,即最近最久未使用的页面
	{                            //下标为PhysicsBlock-1的物理块为栈顶,即最新的页面
		MemPage[i].number=page[i].number;
	}
	cout<<i;
	for(i=MyPhysicsBlock;i<PageNumber;i++)
	{ 
		cout<<endl;
		system("CLS");
        Print();
		cout<<endl;
		cout<<"━━━━━━━━━━━━━━━━━━━"<<endl;
		cout<<"     LRU算法过程："<<endl;
		FIFOPrintM( MyPhysicsBlock );
		cout<<endl;
		cout<<"当前访问"<<page[i].number<<"页面"<<endl;
		tmp=CheckMem(page[i], MyPhysicsBlock );
		if(tmp!=-1)//当前页面已存在
		{
			if( MyPhysicsBlock==7)
			{
				switch(tmp)
				{//根据页面在内存块中的序号调整栈,使得内存块中序号为0的是最近最久未使用的,
				case 0:    
					MyCase(0,i,PhysicsBlock ,MemPage,page);
					break;
				case 1:
					MyCase(1,i,PhysicsBlock ,MemPage,page);
					break;
				case 2:
					MyCase(2,i,PhysicsBlock ,MemPage,page);
					break;
				case 3:				
					MyCase(3,i,PhysicsBlock ,MemPage,page);
					break;
				case 4:
					MyCase(4,i,PhysicsBlock ,MemPage,page);
					break;					
				case 5:
					MyCase(5,i,PhysicsBlock ,MemPage,page);
					break;					
				default:
					break;
				}
			}
			if(MyPhysicsBlock==6)
			{
				switch(tmp)
				{//根据页面在内存块中的序号调整栈,使得内存块中序号为0的是最近最久未使用的,
				case 0:    //序号为2的是最新的页面
					MyCase(0,i,PhysicsBlock ,MemPage,page);
					break;
				case 1:
					MyCase(1,i,PhysicsBlock ,MemPage,page);
					break;
				case 2:
					MyCase(2,i,PhysicsBlock ,MemPage,page);
					break;
				case 3:				
					MyCase(3,i,PhysicsBlock ,MemPage,page);
					break;
				case 4:
					MyCase(4,i,PhysicsBlock ,MemPage,page);
					break;				
				default:
					break;
				}
			}
			if(MyPhysicsBlock==5)
			{
				switch(tmp)
				{//根据页面在内存块中的序号调整栈,使得内存块中序号为0的是最近最久未使用的,
				case 0:    //序号为2的是最新的页面
					MyCase(0,i,PhysicsBlock ,MemPage,page);
					break;
				case 1:
					MyCase(1,i,PhysicsBlock ,MemPage,page);
					break;
				case 2:
					MyCase(2,i,PhysicsBlock ,MemPage,page);
					break;
				case 3:				
					MyCase(3,i,PhysicsBlock ,MemPage,page);
					break;					
				default:
					break;
				}				
			}
			if(MyPhysicsBlock==4)
			{
				switch(tmp)
				{//根据页面在内存块中的序号调整栈,使得内存块中序号为0的是最近最久未使用的,
				case 0:    //序号为2的是最新的页面
					MyCase(0,i,PhysicsBlock ,MemPage,page);
					break;
				case 1:
					MyCase(1,i,PhysicsBlock ,MemPage,page);
					break;
				case 2:
					MyCase(2,i,PhysicsBlock ,MemPage,page);
					break;				
				default:
					break;
				}
			}
			if(MyPhysicsBlock==3)
			{
				switch(tmp)
				{//根据页面在内存块中的序号调整栈,使得内存块中序号为0的是最近最久未使用的,
				case 0:    //序号为2的是最新的页面
					MyCase(0,i,PhysicsBlock ,MemPage,page);
					break;
				case 1:
					MyCase(1,i,PhysicsBlock ,MemPage,page);
					break;
					
				default:
					break;
				}
			}
			
			if(MyPhysicsBlock==2)
			{
				switch(tmp)
				{//根据页面在内存块中的序号调整栈,使得内存块中序号为0的是最近最久未使用的,
				case 0:    //序号为2的是最新的页面
					MyCase(0,i,PhysicsBlock ,MemPage,page);
					break;
				default:
					break;
				}
			}			
			cout<<"页面已在内存"<<endl;
			cout<<"━━━━━━━━━━━━━━━━━━━"<<endl;
			display();
}
else//如果不存在，换出内存块下标为0中的页面
{
	count[2]++;
	cout<<"页面中断"<<endl;
	cout<<"页面"<<page[i].number<<"置换出页面"<<MemPage[0].number<<endl;
	for(j=0;j<MyPhysicsBlock;j++)//页面置换，换出最近最久未使用的页面
	{
		MemPage[j].number=MemPage[j+1].number;
	}
	MemPage[j-1].number=page[i].number;
	cout<<"━━━━━━━━━━━━━━━━━━━"<<endl;
	display();
}
} 
}

void main()
{	
	int physicsblock ;
	int t;
	
	cout<<"输入内存分配给进程的物理块(即页帧数1-7)"<<endl;
	cin>>physicsblock;
	cout<<endl<<endl<<endl<<endl;	
	
	t=time(NULL);
	srand(t);
	system("CLS");
	ProRondPage();
	intial(page,input);
	
	FIFt(physicsblock);
	LRU(physicsblock);
	
	LastPrint();		
}