页面置换算法（FIFO,OPT,LRU)_fifo算法

FIFO（First In First Out）

先进先出页面置换算法（First In First Out，FIFO）是一种简单的页面置换算法，它依据页面进入主存储器的先后顺序进行页面置换。FIFO算法是一种非常直观的页面置换算法，它将最早进入主存储器的页面作为最先置换的页面。

具体来说，FIFO算法维护一个先进先出的页面队列，当一个页面需要调入主存储器时，它被加入队列的末尾。当需要置换页面时，FIFO算法选择队列头部的页面进行置换。这样，最先进入主存储器的页面总是最先被置换出去，而最后进入主存储器的页面总是保留在主存储器中。

FIFO算法的优点是实现简单，适用于对于页面访问顺序没有特别要求的场景，缺点是无法判断哪些页面是频繁使用的，而只是根据时间进行置换，可能会导致一些常用的页面被频繁置换，从而影响系统的性能。

int FIFO(int n){
	//创建长度为n的空间来表示已经存储进去了
	int *tmp=new int[n];
	int i=0;
	//统计页面交换的次数
	int exchange=0;
	//初始化标记成-1是，说明空间没有被占用
	for(i=0;i<n;i++){
		tmp[i]=-1;
	}
	for(i=0;i<ppLength;i++){
		//index返回小于0说明tmp中没有要查找的元素
		if(index(tmp,n,processPage[i])<0){
			//说明tmp还有位置
			if(index(tmp,n,-1)>=0){
				int pos=index(tmp,n,-1);
				//直接把进程的页面填进来了
				tmp[pos]=processPage[i];
			}else{
				//没有位置了就把最先到的移出去
				int j=0;
				for(j=0;j<n-1;j++){
					tmp[i]=tmp[i+1];
				}
				//把新进来的加到数组的末尾
				tmp[n-1]=processPage[i];
				//记录交换的次数
				exchange++;
			}
		}
	}
	return exchange; 
}
 
//查找数组arr中有没有target元素
int index(int *arr,int size,int target){
	int i=0;
	for(i=0;i<size;i++){
		//查找到元素，返回其下标
		if(arr[i]==target){
			return i;
		}
	}
	//没有查到则返回-1
	return -1;
}

我原本是这样写的，但是这种写法到后面没有输出了，可能是数组需要经常的移动元素，浪费的大量的时间，这个其实可以不移动数组元素，类似循环队列的思想，来实现移动队列元素的效果。

//先进先出置换算法
int FIFO(int n){
	//记录页面交换的次数
	int exchange=0;
	int head,tail,count;
	//记录队头,队尾,以及当前队列中的元素个数
	head=tail=count=0;
	int *arr=new int[n];
	int i=0;
	for(i=0;i<ppLength;i++){
		//查找物理内存中是否含有该页面
		if(index(arr,head,tail,processPage[i],n+1)<0){
			//判断物理内存是否填满，没有就直接添加进来
			if(count<n){
				arr[tail]=processPage[i];
				tail=(tail+1)%(n+1);
				count++;
				exchange++;
			}else{
				//“移除”最先进来的页面
				head=(head+1)%(n+1);
				//添加新页面
				arr[tail]=processPage[i];
				tail=(tail+1)%(n+1);
				exchange++;
			}
		}
	}
	return exchange;
}
 
//查找数组arr中有没有target元素[head,tail]
int index(int *arr,int head,int tail,int target,int size){
	while(head!=tail){
		if(arr[head]==target){
			return head;
		}
		head=(head+1)%size;
	}
	return -1;
}

代码思路分析：首先判断页面是否已经存在物理内存中，然后就判断内存里面还有没有空间，如果还有空间就直接加到末尾即可，要注意的这个tail就是末尾，head表示开头，然后通过取余实现循环队列的效果。

OPT(Optimal)

最佳置换算法（Optimal，OPT）是一种最理想的页面置换算法，它会选择未来最长时间内不使用的页面进行置换。但是很遗憾，实际上无法完全地预测出未来哪个页面最长时间内不会被使用，因此最佳置换算法只能算是一种理论上的算法。

具体来说，最佳置换算法维护一个未来页面使用情况的列表，当需要置换页面时，它会选择未来最长时间内不会被使用的页面进行置换。因此，最佳置换算法需要预测未来页面使用情况，通常通过分析页面的历史使用情况来进行预测。

最佳置换算法的优点是最理想的，可以保证置换出去的页面未来不会被再次访问，因此是页面置换算法的一个理论上的最佳选择。缺点是需要精确预测未来的内存访问模式，而这通常是不可能做到的。实际应用中，最佳置换算法很少被使用，通常使用一些近似算法来优化系统的性能。

//最佳置换算法
int OPT(int n){
	int *arr=new int[n];
	int exchange=0;//统计页面交换的次数
	int count=0;//记录当前物理内存中已经添加的数量
	int i;
	for(i=0;i<ppLength;i++){
		//查找物理内存中是否含有该页面
		if(index(arr,0,count,processPage[i],n+1)<0){
			if(count<n){
				//直接添加到最后
				arr[count]=processPage[i];
				count++;
				exchange++;
			}else{
				//寻找最久页面不用的下标
				int pos=index(arr,count,processPage[i],i);
				//更新内存中的页面
				arr[pos]=processPage[i];
				exchange++;
			}
		}
	}
	return exchange;
}
 
//查找数组arr中有没有target元素[head,tail]
int index(int *arr,int head,int tail,int target,int size){
	while(head!=tail){
		if(arr[head]==target){
			return head;
		}
		head=(head+1)%size;
	}
	return -1;
}
 
//查找最久不用页面对应在数组中元素的下标
int index(int *arr,int size,int target,int pos){
	int farthestDistance=0;//记录最远距离的页面位置
	int sub=0;//记录最远不用页面在物理内存（arr)中对应的元素下标
	bool flag=false;//标记该页面是否被找到
	int i,j;
	for(i=0;i<size;i++){
		flag=false;
		j=pos+1;//从pos之后的位置开始找最久不用的页面
		while(j<ppLength&&!flag){
			//找到页面
			if(arr[i]==processPage[j]){
				flag=true;
				//判断是否还有更久不用的页面
				if((j-pos)>farthestDistance){
					//更新最远距离
					farthestDistance=j-pos;
					sub=i;
				}
			}
			j++;
		}
		if(!flag){
			//可以取到的最近不用页面的距离
			farthestDistance=ppLength-pos;
			sub=i;
		}
	}
	return sub;
}

代码思路分析：首先的判断还是和前面一样，就是对于查找应该置换页面的方式不同，通过遍历之后的页面来判断哪个是最久才会被使用的将他淘汰，记录最晚出现的页面在内存中对应的下标进行淘汰即可。

LRU（Least Recently Used）

最近最久未使用（Least Recently Used，LRU）是一种常用的页面置换算法。LRU算法的基本思想是，根据页面的使用历史，置换最近最久未使用的页面。

具体来说，LRU算法维护一个页面使用时刻的列表，当需要置换页面时，它会选择最近最久未使用的页面进行置换。为了实现这个算法，可以使用一个链表来维护已经调入内存的页面，每次页面被访问时，将其移到链表的头部，最近访问的页面总是在头部。

这种算法的优点是相对简单，不需要像最佳置换算法一样需要精确地预测未来的内存访问模式。它完全按照页面的历史使用情况来进行置换，可以有效地利用已经调入内存的页面资源，提高了系统性能。缺点是实现比较复杂，需要维护一个按访问时间排序的列表，因此会增加一定的计算负担。

总的来说，LRU算法是一种比较优秀的页面置换算法，被广泛应用于操作系统和数据库等领域。

//最久未使用置换算法 
int LRU(int n){
	//物理内存
	int *arr=new int[n];
	int *help=new int[n];//记录页面被访问的情况,数值大的被交换
	int exchange=0;//统计页面交换的次数
	int count=0;//记录当前物理内存中已经添加的数量
	int i,j;
	//最开始页面都没被调用
	for(i=0;i<n;i++){
		help[i]=0;
	}
	for(i=0;i<ppLength;i++){
		for(j=0;j<n;j++){
			//每次有新的页面都加一，不管有没有发生置换，表示页面这次没有被使用
			help[j]++;
		}
		//查找物理内存中是否含有该页面
		if(index(arr,0,count,processPage[i],n+1)<0){
			//判断物理内存是否填满，没有就直接添加进来
			if(count<n){
				//直接添加到最后，并标记为0
				arr[count]=processPage[i];
				help[count]=0;
				count++;
				exchange++;
			}else{
				//查找最久没有使用的下标，并进行交换
				int pos=index(help,n);
				arr[pos]=processPage[i];
				help[pos]=0;
				exchange++;
			}
		}else{
			//虽然不用置换，但是也要标记，说明该页面被使用
			int pos=index(arr,0,count,processPage[i],n+1);
			help[pos]=0;
		}
	}
	return exchange;
}
 
//查找数组arr中有没有target元素[head,tail]
int index(int *arr,int head,int tail,int target,int size){
	while(head!=tail){
		if(arr[head]==target){
			return head;
		}
		head=(head+1)%size;
	}
	return -1;
}
 
 
//返回数组arr中最大值对应的下标
int index(int *arr,int size){
	int max=0;
	int sub;
	int i;
	for(i=0;i<size;i++){
		//记录最大值以及对应的下标
		if(max<arr[i]){
			sub=i;
			max=arr[i];
		}
	}
	return sub;
}

代码思路分析：通过一个数组来记录对应页面没有使用的次数，然后就淘汰最久没有使用的哪个即可，要注意的是，当页面在内存中已经存在的时候也要更新记录次数的数组，标记成0就意味着改页面被使用了。

 注意我这里的话重载了三个index函数，都是查找下标，但是里面还是有差别的。

#include<iostream>
using namespace std;
 
//所有进程的页面走向，这个设置成全局变量就减少了参数的传递 
int processPage[]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1};
int ppLength=sizeof(processPage)/sizeof(int);
 
//相关函数的声明	
int FIFO(int i);//先进先出置换算法 
int OPT(int i);//最佳置换算法 
int LRU(int i);//最久未使用置换算法 
 
//查找数组arr中有没有target元素
int index(int *arr,int head,int tail,int target,int size);
int index(int *arr,int size,int target,int pos);
int index(int *arr,int size);
 
int main(){
	int i=0;
	//先把所有的页面打印一遍 
	cout<<"访问页为：";
	for(i=0;i<ppLength;i++){
		cout<<processPage[i]<<" ";
	}
	cout<<endl<<endl;
	//系统给进程的物理块数 
	for(i=1;i<=7;++i){
		//输出相关信息 ，这个输出可能会造成输出混乱
		cout<<"驻留集大小 "<<i<<endl;
		cout<<"FIFO 缺页次数 "<<FIFO(i)<<endl;
		cout<<"OPT 缺页次数 " <<OPT(i)<<endl;
		cout<<"LRU 缺页次数 "<<LRU(i)<<endl;
		cout<<endl; 
	}
	return 0;
}
 
//先进先出置换算法
int FIFO(int n){
	//记录页面交换的次数
	int exchange=0;
	int head,tail,count;
	//记录队头,队尾,以及当前队列中的元素个数
	head=tail=count=0;
	int *arr=new int[n];
	int i=0;
	for(i=0;i<ppLength;i++){
		//查找物理内存中是否含有该页面
		if(index(arr,head,tail,processPage[i],n+1)<0){
			//判断物理内存是否填满，没有就直接添加进来
			if(count<n){
				arr[tail]=processPage[i];
				tail=(tail+1)%(n+1);
				count++;
				exchange++;
			}else{
				//“移除”最先进来的页面
				head=(head+1)%(n+1);
				//添加新页面
				arr[tail]=processPage[i];
				tail=(tail+1)%(n+1);
				exchange++;
			}
		}
	}
	return exchange;
}
 
//最佳置换算法
int OPT(int n){
	int *arr=new int[n];
	int exchange=0;//统计页面交换的次数
	int count=0;//记录当前物理内存中已经添加的数量
	int i;
	for(i=0;i<ppLength;i++){
		//查找物理内存中是否含有该页面
		if(index(arr,0,count,processPage[i],n+1)<0){
			if(count<n){
				//直接添加到最后
				arr[count]=processPage[i];
				count++;
				exchange++;
			}else{
				//寻找最久页面不用的下标
				int pos=index(arr,count,processPage[i],i);
				//更新内存中的页面
				arr[pos]=processPage[i];
				exchange++;
			}
		}
	}
	return exchange;
}
 
//最久未使用置换算法 
int LRU(int n){
	//物理内存
	int *arr=new int[n];
	int *help=new int[n];//记录页面被访问的情况,数值大的被交换
	int exchange=0;//统计页面交换的次数
	int count=0;//记录当前物理内存中已经添加的数量
	int i,j;
	//最开始页面都没被调用
	for(i=0;i<n;i++){
		help[i]=0;
	}
	for(i=0;i<ppLength;i++){
		for(j=0;j<n;j++){
			//每次有新的页面都加一，不管有没有发生置换，表示页面这次没有被使用
			help[j]++;
		}
		//查找物理内存中是否含有该页面
		if(index(arr,0,count,processPage[i],n+1)<0){
			//判断物理内存是否填满，没有就直接添加进来
			if(count<n){
				//直接添加到最后，并标记为0
				arr[count]=processPage[i];
				help[count]=0;
				count++;
				exchange++;
			}else{
				//查找最久没有使用的下标，并进行交换
				int pos=index(help,n);
				arr[pos]=processPage[i];
				help[pos]=0;
				exchange++;
			}
		}else{
			//虽然不用置换，但是也要标记，说明该页面被使用
			int pos=index(arr,0,count,processPage[i],n+1);
			help[pos]=0;
		}
	}
	return exchange;
}
 
//查找数组arr中有没有target元素[head,tail]
int index(int *arr,int head,int tail,int target,int size){
	while(head!=tail){
		if(arr[head]==target){
			return head;
		}
		head=(head+1)%size;
	}
	return -1;
}
 
//查找最久不用页面对应在数组中元素的下标
int index(int *arr,int size,int target,int pos){
	int farthestDistance=0;//记录最远距离的页面位置
	int sub=0;//记录最远不用页面在物理内存（arr)中对应的元素下标
	bool flag=false;//标记该页面是否被找到
	int i,j;
	for(i=0;i<size;i++){
		flag=false;
		j=pos+1;//从pos之后的位置开始找最久不用的页面
		while(j<ppLength&&!flag){
			//找到页面
			if(arr[i]==processPage[j]){
				flag=true;
				//判断是否还有更久不用的页面
				if((j-pos)>farthestDistance){
					//更新最远距离
					farthestDistance=j-pos;
					sub=i;
				}
			}
			j++;
		}
		if(!flag){
			//可以取到的最近不用页面的距离
			farthestDistance=ppLength-pos;
			sub=i;
		}
	}
	return sub;
}
 
//返回数组arr中最大值对应的下标
int index(int *arr,int size){
	int max=0;
	int sub;
	int i;
	for(i=0;i<size;i++){
		//记录最大值以及对应的下标
		if(max<arr[i]){
			sub=i;
			max=arr[i];
		}
	}
	return sub;
}

这个最开始写的时候是把框架写成这样，结果发现和理想的输出不符合。不知道是不是我写错的问题，我的思路就行先把他输出就行，每次输出的函数都是返回一个0.后面看到一个可能原因。

for循环中有异步操作导致数据顺序错乱的问题 - 码农教程 (manongjc.com)http://www.manongjc.com/detail/25-jxvuwkozmptrftp.html

#include<iostream>
using namespace std;
 
//所有进程的页面走向，这个设置成全局变量就减少了参数的传递 
int processPage[]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1};
int ppLength=sizeof(processPage)/sizeof(int);
 
//相关函数的声明	
int FIFO(int i);//先进先出置换算法 
int OPT(int i);//最佳置换算法 
int LRU(int i);//最久未使用置换算法 
 
int main(){
	int i=0;
	//先把所有的页面打印一遍 
	cout<<"访问页为：";
	for(i=0;i<ppLength;i++){
		cout<<processPage[i]<<" ";
	}
	cout<<endl<<endl;
	//系统给进程的物理块数 
	for(i=1;i<=7;++i){
		//输出相关信息 
		cout<<"驻留集大小 "<<i<<endl;
		cout<<"FIFO 缺页次数 "<<FIFO(i)<<endl;
		cout<<"OPT 缺页次数 " <<OPT(i)<<endl;
		cout<<"LRU 缺页次数 "<<LRU(i)<<endl;
		cout<<endl; 
	}
	return 0;
}
 
//先进先出置换算法 
int FIFO(int i){
	return 0; 
}
 
//最佳置换算法
int OPT(int i){
	return 0; 
}
 
//最久未使用置换算法 
int LRU(int i){
	return 0; 
}