请求调页存储器管理方式的模拟.cpp

模拟内存管理中的请求掉页的小程序

#include<iostream.h>
#include<stdlib.h>
#include<conio.h>
#include<stdio.h>
#define Bsize 4

typedef struct BLOCK//声明一种新类型——物理块类型
{  
	int pagenum;//页号
	int accessed;//访问字段，其值表示多久未被访问

}BLOCK;	

int pc;//程序计数器，用来记录指令的序号
int n;//缺页计数器，用来记录缺页的次数	
static int temp[320];//用来存储320条随机数
BLOCK block[Bsize]; //定义一大小为4的物理块数组
//*************************************************************
void init();     //程序初始化函数
int findExist(int curpage);//查找物理块中是否有该页面
int findSpace();//查找是否有空闲物理块
int findReplace();//查找应予置换的页面
void display();//显示
void suijishu();//产生320条随机数,显示并存储到temp[320]
void pagestring();//显示调用的页面队列
void LRU();// LRU算法
void FIFO();//FIFO算法
//*************************************************************
void init()//初始化物理块    
{  
   for(int i=0;i<Bsize;i++) 
   {
	   block[i].pagenum=-1;//空闲物理块             
       block[i].accessed=0;
       pc=n=0;
   }
}
//-------------------------------------------------------------
int findExist(int curpage)//查找物理块中是否有该页面              
{
 
    for(int i=0; i<Bsize; i++)
	{
		if(block[i].pagenum == curpage )
        return i;//检测到内存中有该页面，返回block中的位置

	}
    return -1;//没有则返回-1
}
//-------------------------------------------------------------
int findSpace()//查找是否有空闲物理块
{   
	for(int i=0; i<Bsize; i++)
	{
	   if(block[i].pagenum == -1)
        return i;//找到空闲的block，返回block中的位置
	} 
	
    return -1;//找不到则返回-1
}
//-------------------------------------------------------------
int findReplace()//查找应予置换的页面
{
   int pos = 0;
   for(int i=0; i<Bsize; i++)
   {
	   if(block[i].accessed >block[pos].accessed)
         pos = i;//找到应予置换页面，返回BLOCK中位置
   }
 return pos;
}
//-------------------------------------------------------------
void display(int space)//显示
{
   for(int i=0; i<Bsize; i++)
   {
	   if(block[i].pagenum != -1)//物理块不空
	   {	printf(" %02d ",block[i].pagenum);}
   }
   cout<<"调入的页面是："<<block[space].pagenum<<"  其物理块的地址是："<<&block[space];
   cout<<endl;
}
//-------------------------------------------------------------
void suijishu(int pc)//产生随机数
{   int flag=0;
    cout<<"******按照要求产生的320个随机数：*******"<<endl;
    for(int i=0;i<320;i++)
	{    
		temp[i]=pc;
		if(flag%2==0) pc=++pc%320; //产生50%的顺序执行指令（flag=0或2时顺序执行）
        if(flag==1) pc=rand()% (pc-1);//产生25%的均匀分布在前地址部分指令
        if(flag==3) pc=pc+1+(rand()%(320-(pc+1)));//产生25%的均匀分布在后地址部分指令
        flag=++flag%4;
		printf(" %03d",temp[i]);
        if((i+1)%10==0) cout<<endl;
	 }
}
//-------------------------------------------------------------
void pagestring()//显示调用的页面队列
{   
	for(int i=0;i<320;i++)
	{
	   printf(" %02d",temp[i]/10);
       if((i+1)%10==0) cout<<endl;
	}

}
//-------------------------------------------------------------	
void LRU()// LRU算法（最近最少使用算法）
{
	int exist,space,position ;
	int curpage;
    for(int i=0;i<320;i++)
	{   
		if(i%100==0) getch();//getch直接从键盘获取键值
		pc=temp[i];//指令在数组中的位置 
	    curpage=pc/10;//指令所在页面
	    exist = findExist(curpage);//查找物理块中是否有该页面,若有返回物理块号
        if(exist==-1)//物理块中不存在该页
		{
			space = findSpace();//查找是否有空闲物理块
            if(space != -1)//有空闲物理块
			{
				block[space].pagenum = curpage;  
                display(space);
			    n=n+1;
			}
            else//无空闲物理块，则寻找置换页面
			{
                position = findReplace(); //查找应予置换的页面 
                block[position].pagenum = curpage; 
				block[position].accessed = -1;//恢复刚调入的BLOCK中页面accessed为-1
                display(position);
			 	n++;
				
			}
		}
        else
		{ 
			block[exist].accessed = -1;//恢复存在的并刚访问过的BLOCK中页面accessed为-1
			for(int i=0; i<Bsize; i++)			
			{  if(block[i].pagenum != -1)//物理块不空
					printf(" %02d ",block[i].pagenum);
			}
			cout<<"指令已经存在！    其物理块地址为："<<&block[exist]<<endl;
			
        
		}
			for(int j=0; j<4; j++)//物理块中各页面的访问标记加1
        {block[j].accessed++;}

	}
	cout<<"缺页次数:"<<n<<endl;
	cout<<"缺页率:"<<(n/320.0)*100<<"%"<<endl;
}
//-------------------------------------------------------------
void FIFO()//FIFO算法（先进先出算法）
{
	int exist,space,position ;
	int curpage;
    for(int i=0;i<320;i++)
	{   
		if(i%100==0) getch();//getch直接从键盘获取键值
		pc=temp[i]; 
	    curpage=pc/10;
       
	    exist = findExist(curpage);//查找物理块中是否有该页面
        if(exist==-1)//物理块中不存在该页      
		{
			space = findSpace();//查找是否有空闲物理块
            if(space != -1)//有空闲物理块
			{
				block[space].pagenum = curpage;  
                display(space);
			    n=n+1;
			}
            else//无空闲物理块，则寻找置换页面
			{
                position = findReplace(); //查找应予置换的页面  
                block[position].pagenum = curpage;   
                display(position);
			 	n++;
			    block[position].accessed=-1;//置换页面所在的物理块中访问标记设为-1
			}
		}
	    else//若存在该页
		{ 
			for(int i=0; i<Bsize; i++)			
			{  if(block[i].pagenum != -1)//物理块不空
					printf(" %02d ",block[i].pagenum);
			}
			cout<<"指令已经存在！    其物理块地址为："<<&block[exist]<<endl;			
        
		}
		for(int j=0; j<Bsize; j++)//物理块中各页面访问标记自动加1
        block[j].accessed++;
      

	}
	cout<<"缺页次数:"<<n<<endl;
	cout<<"缺页率:"<<(n/320.0)*100<<"%"<<endl;
}
//*************************************************************
void main()
{ 
  int  select;
  cout<<"请输入第一条指令号(1~319)：";
  cin>>pc;//随机选取一条起始执行指令
  if(pc>=1&&pc<=319)
  {
    suijishu(pc);//产生随机数
    cout<<"*****对应的调用页面队列*******"<<endl;
    pagestring();//显示调用的页面队列
    do
	{ 
	  cout<<"****************************************"<<endl;
      cout<<"------1:LRU   2:FIFO  3:退出 -----"<<endl;
      cout<<"****************************************"<<endl;
      cout<<"          请选择一种页面置换算法:"; 
	  cin>>select;
      cout<<"****************************************"<<endl;
	  init();
  
	  switch(select)
	  {
      case 1:cout<<"最近最久未使用置换算法LRU:"<<endl;
             cout<<"**************************"<<endl;
             LRU();
             break;
      case 2:cout<<"先进先出置换算法FIFO:"<<endl;
		     cout<<"*********************"<<endl;
             FIFO();
	         break;
   
      default: ;
	  }
  
	}while(select!=3);
  }
  else cout<<"输入非法数据！";

}