fork.cpp

最佳页面置换算法

#include<iostream.h>
#define  M  40
int N;
struct Pro
{
	int num,time;
};
int Input(int m,Pro p[M])
{   
	cout<<"请输入实际运行页数:\n";
	do
	{
		cin>>m;
		if(m>M)cout<<"数目太多，请重试"<<endl;
		else break;
	}while(1);
    cout<<"请输入运行页面序列号:\n";
   	for(int i=0;i<m;i++)
	{
		cin>>p[i].num;
		p[i].time=0;
	}
	return m;
}
void print(Pro *page1)//打印当前的页面
{
	Pro *page=new Pro[N];
	page=page1;
	for(int i=0;i<N;i++)cout<<page[i].num<<"  ";
	cout<<endl;
}
int  Search(int e,Pro *page1  )
{
	Pro *page=new Pro[N];
	page=page1;
	for(int i=0;i<N;i++)if(e==page[i].num)return i;
	return -1;
}
int Max(Pro *page1)
{
	Pro *page=new Pro[N];
	page=page1;
	int e=page[0].time,i=0;
	while(i<N)//找出离现在时间最长的页面
	{
		if(e<page[i].time)e=page[i].time;
		i++;
	}
    for( i=0;i<N;i++)if(e==page[i].time)return i;
	
	return -1;
}
int Compfu(Pro *page1,int i,int t,Pro p[M])
{
	Pro *page=new Pro[N];
	page=page1;
	
	int count=0;
	for(int j=i;j<M;j++)
	{
		if(page[t].num==p[j].num )break;
		else count++;
	}
	return count;
	
}
int main()
{
    
	cout<<"可用内存页面数:  "<<endl;
	cin>>N;
	Pro p[M];
	Pro *page=new Pro[N];
	char c;
	int m=0,t=0;
	float n=0;
	m=Input(m,p);	
	
	do{
		
		for(int i=0;i<N;i++)//初试化页面基本情况
		{
			page[i].num=0;
			page[i].time=2-i;
		}
        i=0;		
        cout<<"f:FIFO页面置换"<<endl;
		cout<<"l:LRU页面置换"<<endl;
		cout<<"按其它键结束"<<endl;
		cin>>c;
		
		if(c=='f')//FIFO页面置换
		{
			n=0;
			cout<<"页面置换情况:   "<<endl;
			while(i<m)
			{
				if(Search(p[i].num,page)>=0)i++;//找到相同的页面
				else 
				{  
					if(t==N)t=0;
					else 
					{
						n++;
						page[t].num=p[i].num;
						print(page);
						t++;
					}
				}
			}
			cout<<"缺页次数："<<n<<"    缺页率："<<n/m<<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++;}
            print(page);				
			i++;
		}
		cout<<"缺页次数："<<n<<"    缺页率："<<n/m<<endl;
		}
		}while(c=='f'||c=='l');
	return 0;
}