pm.txt

操作系统请求页式管理置换算法的FIFO、LRU、OPT算法实验源代码

#include<iostream>
using namespace std; 

int pop;//进程页面总数
int pom;//内存分配页面数
int callnum;//程序访问串数
int callorder[100];//存储访问内存每一步程序和数据的页号
int mempage[100];//内存中分配的页面空间，用于存储驻留在内存的页号
int counter[100];//计数器，在FIFO算法中用于记录页面驻留内存的时间，在LFU算法中用于记录页面被访问次数(在OPT算法中用做存储内存页面在将来出现的第一个位置,未出现值为0)
int is_pagelack;//是否缺页的标志
int pagelacknum;//缺页数

void display(int i,int ad){
	cout<<callorder[i]<<"              ";
	if(ad==-1){
		for(int i=0;i<pom;i++){
			cout<<mempage[i]<<" ";
	}
	}else{
		for(int j=0;j<ad+1;j++){
			cout<<mempage[j]<<" ";
		}
	}
	for(int k=0;k<16-pom*2;k++){
		cout<<" ";
	}
	if(is_pagelack){
		cout<<"不缺页";
	}else{
		cout<<"缺页！";
		pagelacknum++;	
		
	}
	cout<<endl;
}//结果输出显示

int max(){
	int maxnum=counter[0];
	int max_ad=0;
	for(int k=1;k<pom;k++){
		if(counter[k]>maxnum){
			maxnum=counter[k];
			max_ad=k;
		}
	}
	return max_ad;
}//计算计数器的最大值

void input(){
	int i;
	cout<<"请输入进程页面总数：";
	cin>>pop;
	cout<<"请输入程序访问串的步骤数：";
	cin>>callnum;
	cout<<"请输入程序访问内存的每一步程序和数据的页号："<<endl;
	for(i=0;i<callnum;i++){
		int temp;
		cout<<"请输入程序访问内存的第"<<i+1<<"步所需的程序和数据的页号：";
		cin>>temp;
		if(temp>-1 && temp<pop){
			callorder[i]=temp;
		}else{
			cout<<"该页不存在！请重新输入"<<endl;
			i--;
		}
	}
	cout<<"请输入内存分配的页面数：";
	cin>>pom;
	cout<<"初始化内存空间……"<<endl;
	for(int j=0;j<pom;j++){
		mempage[j]=-1;
	}
}//输入

void cle(){
	for(int i=0;i<100;i++){
		counter[i]=0;
		
	}
	
}//初始化计数器

void clemem(){
	for(int i=0;i<100;i++){
		
		mempage[i]=-1;
	}
}//初始化内存空间

int find_space(){
	int flag=-1;
	for(int i=0;i<pom;i++){
		if(mempage[i]==-1){
			flag=i;
			break;
		}
	}
	return flag;
}//寻找空闲内存，返回空闲内存地址，如无空闲内存地址返回-1

int is_in_mem(int num){
	int flag=-1;
	for(int i=0;i<pom;i++){
		if(mempage[i]==num){
			flag=i;
		}
	}
	return flag;
}//在内存中寻找是否有该页面,有返回该页面地址，无返回-1

void fifo(){
	cle();
	clemem();
	for(int i=0;i<callnum;i++){
		is_pagelack=0;
		int flag=is_in_mem(callorder[i]);
		int ad=find_space();
		if(flag!=-1){
			is_pagelack=1;
			if(ad==-1){
				for(int j=0;j<pom;j++){
					counter[j]++;
				
				}
			}else{
				for(int n=0;n<ad;n++){
					counter[n]++;
					
				}
			}
			
		}else{
			if(ad!=-1){
				mempage[ad]=callorder[i];
				for(int o=0;o<ad+1;o++){
					counter[o]++;
					
				}
			}else{
				int m=max();//找出驻留内存时间最久的页面，max用于记录最大的时间值，max_add用于记录驻留内存时间最久的页面所占的内存地址
				mempage[m]=callorder[i];
				counter[m]=0;
				for(int l=0;l<pom;l++){
					counter[l]++;
					
				}
			}
		}
		display(i,ad);
	}
}//FIFO算法

void lru(){
	clemem();
	for(int i=0;i<callnum;i++){
		is_pagelack=0;
		int flag=is_in_mem(callorder[i]);
		int ad=find_space();
		if(flag!=-1){
			is_pagelack=1;
			int temp=mempage[flag];
			for(int j=flag;j>0;j--){
					mempage[j]=mempage[j-1];
				}
				mempage[0]=callorder[i];
		}else{
			if(ad!=-1){
				
				for(int k=ad;k>0;k--){
					mempage[k]=mempage[k-1];
				}
				mempage[0]=callorder[i];
			}else{
				for(int l=pom-1;l>0;l--){
					mempage[l]=mempage[l-1];
				}
				mempage[0]=callorder[i];
			}
		}
	
		
		display(i,ad);
	}
}//LRU算法

void opt(){
	cle();
	clemem();
	for(int i=0;i<callnum;i++){
		is_pagelack=0;
		int flag=is_in_mem(callorder[i]);
		int ad=find_space();
		if(flag!=-1){
			is_pagelack=1;
		}else{
			if(ad!=-1){
				mempage[ad]=callorder[i];
			}else{
				if(i!=callnum-1){
					for(int j=0;j<pom;j++){
						for(int k=i+1;k<callnum;k++){
							if(mempage[j]==callorder[k]){
								counter[j]=k;
								
								break;
							}
						}
					}
					int flag_1=0;
					for(int l=0;l<pom;l++){
						if(counter[l]==0){
							flag_1=1;
							mempage[l]=callorder[i];				
							break;
						}
					}
					if(flag_1==0){
						int toreplace=max();
						mempage[toreplace]=callorder[i];
					}
					cle();
				}else{
					mempage[0]=callorder[i];
				}
			}
		}
		display(i,ad);
	}
}//OPT算法

void mainpan(){
	pagelacknum=0;
	int i;
	cout<<"欢迎使用请求页式管理置换算法分析程序!"<<endl;
	cout<<"1、FIFO算法"<<endl;
	cout<<"2、LRU算法"<<endl;
	cout<<"3、OPT算法"<<endl;
	cout<<"4、退出"<<endl;
	cout<<"请选择一种算法或退出程序:"<<endl;
	cin>>i;
	cout<<"当前访问页面号 "<<"内存页面存储状态";
		if((pom*2)>16){
			for(int j=0;j<pom*2-16;j++){
				cout<<" ";
			}
		}
	cout<<"是否缺页"<<endl;
	switch(i){
		case 1:{
			fifo(); 
			break;
			   }
		case 2:{
			lru(); 
			break;
			   }
		case 3:{
			opt(); 
			break;
			   }
		case 4: {
			exit; 
			break;
				}
		default: {
			cout<<"输入错误！请重新输入："<<endl;
			mainpan();
				 }
	}
	cout<<"缺页数为"<<pagelacknum<<endl;
	cout<<"缺页率为"<<pagelacknum/float(callnum)<<endl;
	mainpan();
}//程序主界面

void main(){
	input();
	mainpan();
}