mmanage.cpp

页面置换算法的利用

#include "stdafx.h"
#include "MManage.h"
#include "iomanip"
#include "iostream"
using namespace std ;
//////////////////////////////////////////////////////////////////////

MManage::MManage()
{
	int PageTable[Psize];//页面访问顺序表  
    int myrand[Psize]; //存放随机生成指令列
	int i;
	int IP;  //指令号
	bool flag=0;
	cout<<"请输入第一条指令的指令号(指令号应在0～399之间):"<<endl;
	cin>>IP;
	cout<<"生成的随机指令序列如下:"<<endl;
    myrand[0]=IP;
	myrand[1]=IP+1;
	cout.setf(ios::left,ios::adjustfield);
	cout<<setw(5)<<myrand[0]<<setw(5)<<myrand[1];
	for(i=1;i<Psize/2;i++) //随机生成指令序列
	{
		if(flag==0)
		{
			myrand[i*2]=rand()%IP%Psize;
	        myrand[i*2+1]=(myrand[i*2]+1)%Psize;
			
			cout<<setw(5)<<myrand[i*2]<<setw(5)<<myrand[i*2+1];
			flag=1;
		}
		else
		{
			myrand[i*2]=(rand()%(Psize-IP)+IP)%Psize;
			myrand[i*2+1]=(myrand[i*2]+1)%Psize;
		
			cout<<setw(5)<<myrand[i*2]<<setw(5)<<myrand[i*2+1];
			flag=0;
		}

	}
	cout<<endl;
	cout<<"*******调页顺序如下:"<<endl;
	for(i=0;i<Psize;i++)
	{
	   PageTable[i]=myrand[i]/10;//取整
		cout<<setw(5)<<PageTable[i];
	}
	cout<<endl;
    Block = new MPage[Bsize];//Bsize是物理块数目
	for(i=0; i<Bsize; i++)
	{
		Block[i].PageNum = -1;
		Block[i].Sign = 0;//sign是被访问标记
	}
	Page = new MPage[Psize];//页面替换
	for(i=0; i<Psize; i++)//Psize是页的数目
	{
		Page[i].PageNum =PageTable[i];//页面访问顺序替代页面号
		Page[i].Sign = 0;
	}
}
//////////////////////////////////////////////////////////////
int MManage::SearchSpace( )//查找是否有空闲物理块
{
	for(int i=0; i<Bsize; i++)
	if(Block[i].PageNum == -1)
	return i;          //找到空闲块，返回空闲块号
	return -1;
}
///////////////////////////////////////////////////////
int MManage::SearchExist(int curpage)//查找该页面是否已调入内存
{
	for(int i=0; i<Bsize; i++)
	if(Block[i].PageNum == Page[curpage].PageNum)
	return i;          //该页面已存在，返回该页面所在物理块的块号
	return -1;
}
////////////////////////////////////////////////////
int MManage::SearchReplace( ) //查找可被置换的页面
{
	int pos = 0;
	for(int i=0; i<Bsize; i++)
	if(Block[i].Sign >= Block[pos].Sign)
	pos = i;    //找到置换页面，返回该页面所在物理块的块号
	return pos;
}
//////////////////////////////////////////////////////
void MManage::Display( )//显示各物理块中的页面
{
	for(int i=0; i<Bsize; i++)
	if(Block[i].PageNum != -1)
	cout<<setw(3)<<Block[i].PageNum<<" ";
	cout<<endl;
}
/////////////////////////////////////////////////
void MManage::OPT( )
{
 int Exist,Space,Position ;
 int ShortPage=0;
 for(int i=0; i<Psize; i++)   //从第一块开始 装入
 {    
	Exist = SearchExist(i);          //第一块是否存在
	if(Exist != -1)
	{ }        //已存在
	else
	{   
		Space = SearchSpace();        //若不存在，寻找空白物理块
		if(Space != -1)             //若找到空白物理块，将该页调入
		{
			 Block[Space] = Page[i];  
			 Display();
		}
		else                       //若全部物理块已分配，进行置换
		{
			ShortPage++;
			for(int k=0; k<Bsize; k++)
			for(int j=i; j<Psize; j++)
			{
				if(Block[k].PageNum != Page[j].PageNum)
				{ Block[k].Sign = 10000; }//将来不会用，设置Sign为一个很大数
				else
				{
					Block[k].Sign = j;
					break;
				}
			}
			Position = SearchReplace();  //找到不会再用的或下次调用最晚的页面   
			Block[Position] = Page[i];  //进行置换 
			Display();
		}
	}
 }
 cout<<endl;
 cout<<"最佳置换算法!"<<endl;
 cout<<"换页次数为:"<<ShortPage<<endl;
 cout<<"命中率为："<<(1-float(ShortPage)/float(Psize))*100<<"%"<<endl;
}
////////////////////////////////////////////////
void MManage::FIFO( )
{

int Exist,Space,Position ;
 int ShortPage=0;
 for(int i=0; i<Psize; i++)
 {
  Exist = SearchExist(i);
  if(Exist != -1)
  {     }

  else
  {   
   Space = SearchSpace();//若不存在，寻找空白物理块
   if(Space != -1)//若找到空白物理块，将该页调入
   {
    Block[Space] = Page[i];  
    Display();
   }
   else  //若全部物理块已分配，进行置换
   {
	ShortPage++;
    Position = SearchReplace();
    Block[Position] = Page[i];   
    Display();
   }
  }
  for(int j=0; j<Bsize; j++)
   Block[j].Sign++;       //所有物理块的访问次数加1
 }
 cout<<endl;
 cout<<"先进先出算法!"<<endl;
 cout<<"换页次数为:"<<ShortPage<<endl;
 cout<<"命中率为："<<(1-float(ShortPage)/float(Psize))*100<<"%"<<endl;
}
////////////////////////////////////////////////////////////
void MManage::LRU( )
{
 int Exist,Space,Position ;
 int ShortPage=0;
 for(int i=0; i<Psize; i++)
 {
	Exist = SearchExist(i); //第一块是否存在
  if(Exist != -1)
  {
		Block[Exist].Sign = -1;//当前块已存在，本次调用后，将访问标记复位
  }
  else
  { 
		Space = SearchSpace();//若不存在，寻找空白物理块
		if(Space != -1)//若找到空白物理块，将该页调入
		{
			Block[Space] = Page[i]; 
			Display();
		}
		else //若全部物理块已分配，进行置换
		{
			ShortPage++;
			Position = SearchReplace();  //找到最近最久未使用的页面，进行置换
			Block[Position] = Page[i];   
			Display();
		}
  }
  for(int j=0; j<Bsize; j++)
   Block[j].Sign++;
 }
 cout<<endl;
 cout<<"最近最久未使用算法!"<<endl;
 cout<<"换页次数为:"<<ShortPage<<endl;
 cout<<"命中率为："<<(1-float(ShortPage)/float(Psize))*100<<"%"<<endl;
}
///////////////////////////////////////////////////////////////////
void MManage::BlockClear(void)//物理块初始化
{
 for(int i=0; i<Bsize; i++)
 {
  Block[i].PageNum=-1;
  Block[i].Sign = 0;
 }
}
//////////////////////////////////////////////////
MManage::~MManage()
{
}
////////////////////////////////////////////////

int main(int argc, char* argv[])
{
	cout<<"                   请求调页存储管理方式模拟 "<<endl;
	cout<<"       姓名：周玉祥   班级：计062   学号：200600401079"<<endl;    
	cout<<endl;
    cout<<"                 1.最佳置换算法(OPT),请按'a' "<<endl;
	cout<<endl;
	cout<<"                 2.先进先出算法(FIFO),请按'b' "<<endl;
	cout<<endl;
	cout<<"                 3.最近最久未使用算法(LRU)，请按'c' "<<endl;
	cout<<endl;
	char  Operation;
	MManage Reqpage;
	while(Operation!='d')
	{
		cout<<"请按'a''b''c'键选择一种算法或按'd'退出: "<<endl;
		cin>>Operation;
		switch(Operation)
		{
   
			case 'a':
				cout<<" 最佳置换算法置换顺序如下: "<<endl;
				Reqpage.OPT();
				Reqpage.BlockClear();
				cout<<"*********************************************"<<endl;
				break;
			case 'b':
				cout<<" 先进先出算法置换顺序如下: "<<endl;
				Reqpage.FIFO();
				Reqpage.BlockClear();
				cout<<"********************************************"<<endl;
				break;
			case 'c': 
				cout<<" 最近最久未使用算法置换顺序如下 :"<<endl;
				Reqpage.LRU();
				Reqpage.BlockClear();
				cout<<"*********************************************"<<endl;
				break;
			case 'd':
				break; 
			default:
				cout<<" 无此操作,请从新输入: "<<endl;
				break;
		}
	}
	return 0;
}