一分钟学会页面置换算法【OPT、FIFO、LRU、NUR】

程序执行期间，若程序所要访问的页面未在内存时，便发出缺页中断，中断处理程序首先保留CPU环境，转入缺页中断处理程序。查找页表，得到该页在外存的物理块后，如果内存未满，则将缺页调入内存并修改页表。
如果内存已满，则按照某种置换算法从内存中选出一页换出；如果该页未被修改过，可不必将该页写回磁盘；但如果此页已被修改，则必须将它写回磁盘，然后再把所缺的页调入内存，并修改页表中的相应表项，置其存在位为“1”，并将此页表项写入快表中。

最佳置换(OPT)算法选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面；采用最佳置换算法可保证获得最低的缺页率。但是由于无法预知哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的；

先进先出（FIFO）算法淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。

最近最久未使用（LRU）算法根据页面调入内存后的使用情况进行决策，选择最近最久未使用的页面予以淘汰；该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问一来所经历的时间T，当需要淘汰一个页面时，选择现有页面中T值最大的，即最近最久未使用的页面予以淘汰。

CLCOK算法又称为最近未使用算法（NUR） 每页设置一个访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列；当某个页面被访问时，其访问位置1。淘汰时，检查其访问位，如果是0，就换出；若为1，则重新将它置0；再按FIFO算法检查下一个页面，到队列中的最后一个页面时，若其访问位仍为1，则再返回到队首再去检查第一个页面。

1．假设系统为某进程分配了四个物理块，页面使用走向为：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1，分别采用OPT算法，FIFO算法，LRU算法，给出页面的置换过程，以及各自发生了几次页面置换？
OPT:4次；FIFO:6次；LRU:4次

2．打开“Microsoft Visual C++ 6.0”，输入相关代码，根据代码注释把空缺的FIFO算法补充完毕，对程序行进编译运行。给出你所填写的FIFO算法代码：

bc[p%blockCount]=pc[i];
					p++;

3．根据提示输入上述相关数据，分别记录OPT算法、FIFO算法、LRU算法以及CLOCK算法运行结果：
（1）OPT算法：

（2）FIFO算法

（3）LRU算法

（4）CLOCK算法

——————————————————————————————————————————————————————————————————————————————————————
附上源代码：

#include<iostream>
using namespace std;
void Print(int bc[],int blockCount){
	for(int i=0; i<blockCount;i++){
		cout<<bc[i]<<" ";
	}
	cout<<endl;
}
int Travel(int bc[],int blockCount,int x){
	int index =-1;
	int i;
	for(i=0; i<blockCount; i++){
      if(bc[i]==x){
			index=i; 
			break;
	  }
	}
	return index;
}
void FIFO(int pc[], int bc[], int pageCount, int blockCount){
	cout<<"0:FIFO置换算法"<<endl;
	int i;
	if(pageCount<=blockCount){
		cout<<" 缺页次数为"<<0<<endl;
		cout<<"缺页率为  "<<0<<endl;
	}
	else{
		int noPage=0;
		int p=0;
		for(i=0; i<pageCount;i++){
			cout<<"引用页:"<<pc[i]<<endl;
			if(Travel(bc,blockCount,pc[i])==-1){
				if(i<blockCount){
					bc[i]=pc[i];
				}
				else{
					bc[p%blockCount]=pc[i];
					p++;//页面不在内存，淘汰最先进入的页面。
				}
				noPage++;
				cout<<"物理块情况: ";
				Print(bc, blockCount);
			}
			cout<<endl;
		}
		cout<<"缺页次数为："<<noPage<<endl;
		cout<<" 缺页率为："<<(float)noPage/pageCount<<endl;
	}
}   
int FoundMaxNum(int a[],int n){
	int k,j;
	k=a[0];
	j=0;
	for(int i=0; i<n;i++){
		if(a[i]>=k){
			k=a[i];
			j=i;
		}
	}
	return j;
}
 void LRU(int pc[],int bc[], int pageCount, int blockCount) {
	cout<<"1:LRU 置换算法"<<endl;   
	if(pageCount<=blockCount){
		cout<<"缺页次数为："<<0<<endl; 
		cout<<"缺页率为："<<0<<endl;
	}
	 else{
		int noPage=0;
		int i, j, m;
		int*bc1=new int[blockCount];   
		for(i=0;i<blockCount;i++){
			bc1[i]=0;
		}
		for(i=0; i<pageCount;i++){
			 cout<<"引用页:"<<pc[i]<<endl;
			if(Travel(bc,blockCount,pc[i])==-1){//页面不在内存
				if(i<blockCount) {//欲调页
					bc[i]=pc[i];
					for(int p=0; p<=i; p++){
							bc1[p]++;
					}
				}
				else{
					for(j=0;j<blockCount;j++){  
						bc1[j]++;
					}
					int k=FoundMaxNum(bc1,blockCount);		
					bc[k]=pc[i];
					bc1[k]=1;
				}
				noPage++;
				cout<<"物理块情况:"; 
				Print(bc,blockCount);
			}
			else {                                 //页面在内存
				if(i<blockCount){
					for(j=0; j<=i; j++){
					bc1[j]++;
				}
				for(m=0; m<i;m++){
					if(bc[m]==pc[i]){
						break;
					}
				}
				bc1[m]=1;
				bc[m]=pc[i];
			}
			else{
				for(j=0;j<blockCount;j++){
					bc1[j]++;
				}
				for(m=0;m<blockCount;m++){
					if(bc[m]==pc[i]){
						break;
					}
				}
				bc1[m]=1;
				bc[m]=pc[i];
				}
			}
			cout<<endl;
	 }
	cout<<"缺页次数为:"<<noPage<<endl;
	cout<<"缺页率为:"<<(float)noPage/pageCount<<endl; 
	delete bc1;
	}
 }
void Optiomal(int pc[],int bc[],int pageCount,int blockCount){	
	cout<<"2:最佳置换算法"<<endl;   
	if(pageCount<=blockCount){
		cout<<"缺页次数为："<<0<<endl;
		cout<<"缺页率为："<<0<<endl;
	}
	else{
		int noPage=0;
		int i,j, k;
		for(i=0; i<pageCount;i++){
			cout<<"引用页:"<<pc[i]<<endl;
			if(Travel(bc,blockCount,pc[i]) ==-1){
				if(i<blockCount){
					bc[i]=pc[i];
				}
				else{
					int max=0;
					int blockIndex;;
					for(j=0;j<blockCount; j++){
						for(k=i;k<pageCount; k++){
							if(bc[i]=pc[k]){	
							break;
							}
						}
						if(k>=max){ 
							max=k;
							blockIndex=j;
						}
					}
					bc[blockIndex]=pc[i];
				}
				 noPage++;
				cout<<"物理块情况:"; 
				Print(bc, blockCount);
			}
			cout<<endl;
		}
		cout<<"缺页次数为："<<noPage<<endl;
		cout<<"缺页率为："<<(float)noPage/pageCount<<endl;
	}
}
void NRU(int pc[], int bc[], int pageCount,int blockCount){
	cout<<"3: Clock置换算法"<<endl ;
	if(pageCount<=blockCount){
		cout<<"缺页次数为"<<0<<endl;
		cout<<"缺页率为"<<0<<endl;
	}
	else{
	int noPage=0;
	 int i,j;
	 int *bc1=new int[blockCount];   
	 for(i=0;i<blockCount;i++){
		 bc1[i]=0;
	 }
	 int replace=0;
	 for(i=0;i<pageCount;i++){
		cout<<"引用页:"<<pc[i]<<endl;
		int index=Travel(bc, blockCount, pc[i]);
		if(index ==-1) {
			for(j=0;j<blockCount;j++){
				if(bc1[replace]==1){
					bc1[replace]=0;
					replace =(replace+1)%blockCount;
				}
				else{
					break;
				}
			}
				bc[replace]=pc[i];
				bc1[replace]=1;
				replace=(replace+1)% blockCount; 
				noPage++;
				cout<<"物理块情况:"; 
				Print(bc,blockCount);  
				cout<<"标志位情况:";   
				Print(bc1,blockCount);
		}
		else{
			bc1[index]=1;
			replace=(index+1)% blockCount; 
			cout<<"物理块情况:";
			Print(bc,blockCount);
			cout<<"标志位情况:";
			Print(bc1,blockCount);
		}
		cout<<endl;
	 }
	cout<<"缺页次数为："<<noPage<<endl;
	cout<<"缺页率为："<<(float)noPage/pageCount<<endl;
	delete bc1;
	}
}
 int main(){
	int pageCount,blockCount,i;
	cout<<"输入页面数"<<endl;
	cin>>pageCount;
	int *pc=new int[pageCount];  
	cout<<"输入页面走向"<<endl;  
	for(i=0;i<pageCount;i++){
		cin>>pc[i];
	}
	cout<<"输入物理块数"<<endl;   
	cin>>blockCount;  
	cout<<"0:FIFO置换算法"<<endl;   
	cout<<"1:LRU置换算法"<<endl;   
	cout<<"2:最佳置换算法"<<endl;
	cout<<"3: Clock置换算法"<<endl;
	cout<<"按数字选择类别:"<<endl;
	int n;
	while(cin>>n){
		if(n==0){
			int *bc=new int[blockCount];
			FIFO(pc,bc,pageCount,blockCount);
			delete bc;
		}
		else if(n==1){
			int *bc=new int[blockCount];
			LRU(pc,bc,pageCount,blockCount);
			delete bc;
		}
		else if(n==2){
			 int *bc=new int[blockCount];
			 Optiomal(pc,bc,pageCount,blockCount);
			 delete bc;
		}
		else if(n==3){
			 int *bc=new int[blockCount];
			 for(i=0; i<blockCount;i++){
				bc[i]=-1;
			 }
			NRU(pc,bc,pageCount,blockCount); 
			delete bc;
		}
		else break;
	}
	delete pc; 
	return 0;
}

其实做人最重要的是自信，到哪儿都一样。————《叶问4》