页面置换之lru与fifo.cpp

页面置换之LRU与FIFO

#include<iostream.h>
#define  M  40
struct Q
{
	int num,time;
};


/************输入页面个数与页面号************/
int Input(int m,Q p[M])
{   
	cout<<"请输入页数：";
	do
	{
		cin>>m;
		if(m>M)cout<<"数目太多，请重试"<<endl;
	    else break;
	}while(1);
    cout<<endl<<"请输入各页面号"<<endl;
   	for(int i=0;i<m;i++)
	{
		cin>>p[i].num;
		p[i].time=0;
	}
	return m;
}

/**********显示置换的情况**************/
void print(Q page[3])
{
	for(int i=0;i<3;i++)cout<<page[i].num<<"  ";
	cout<<endl;
}

/***********寻找指定元在固定页中的位置***********/
int  Search(int e,Q page[3]  )
{
  for(int i=0;i<3;i++)if(e==page[i].num)return i;
  return -1;
}

/*************寻找最大时间元在 固定页中的位置***************/
int Max(Q page[3])
{
	int e=page[0].time,i=0;
     while(i<3)
	{
		 if(e<page[i].time)e=page[i].time;
		 i++;
	}
    for( i=0;i<3;i++)if(e==page[i].time)return i;

  return -1;
}

/*********************固定分配局部置换主函数*******************/
int main()
{
    Q p[M], page[3];
	 char c;
     int m=0,t=0;
	 float n=0;
	m=Input(m,p);

 
  do{

       for(int i=0;i<3;i++)
		  {
		  page[i].num=p[i].num;
          page[i].time=2-i;
		  }
        i=3; 
       cout<<"开始时";
	   print(page);
        
      cout<<"若FIFO页面置换则输入f,若LRU页面置换则输入l,否则输入其他键：";
	  cin>>c;
	  
     if(c=='f')//FIFO页面置换
	 {
		
		 cout<<"页面置换情况:   "<<endl;
        while(i<m)
	   {
		if(Search(p[i].num,page)>=0)i++;
		else 
		{  
			if(t==3)t=0;
		    else 
			{
				n++;
			page[t].num=p[i].num;
			print(page);
			t++;
			}
		}
	   }
       cout<<"缺页次数："<<n<<"    缺页率："<<n/(n+3)<<endl;      

	 }
     if(c=='l')//LRU页面置换
	 {    n=0;
		 cout<<"页面置换情况:   "<<endl; 
		 while(i<m)
		 {    
			int k;
		    k=t=Search(p[i].num,page);
			if(t>=0)
			
			  page[t].time=0;
			  
           
              else
			{  
				  n++; 
			  t=Max(page);
		
			  page[t].num=p[i].num;
              page[t].time=0;
              }
			  if(t==0){page[t+1].time++;page[t+2].time++;}
			  if(t==1){page[2].time++;page[0].time++;}
              if(t==2){page[1].time++;page[0].time++;}
            if(k==-1)   print(page);
              
	          
		 	 i++;
		 }
     cout<<"缺页次数："<<n<<"    缺页率："<<n/(n+3)<<endl; 
	 }
  
	}while(c=='f'||c=='l');
 
 

	return 0;
}