题目：一进程刚获得三个主存块的使用权，若该进程访问页面的次序是｛1，3，2，1，2，1，5，1，2，3｝，采用LRU算法时，缺页数是______次。

LRU算法

简介：算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。
 
以｛1，3，2，1，2，1，5，1，2，3｝为例子，进行LRU算法演示，假设把三主存块想象成长度为3的数组。开始演示：

1 进入 —> 1（缺1）
3 进入 —> 3 1 （刚使用的放在前面(左边)，未使用的依次后移(右移))（缺3）
2 进入 —> 2 3 1（缺2）
1 进入 —> 1 2 3（把原本的1移出）
2 进入 —> 2 1 3
1 进入 —> 1 2 3
5 进入 —> 5 1 2 （进行页面置换，3是最少使用的所以换出）
1 进入 —> 1 5 2
2 进入 —> 2 1 5
3 进入 —> 3 2 1（进行页面置换，5是最少使用的所以推出）

总共进行了两次页面置换，所以缺页数=3+2=5，这个3代表前三个缺的，2代表置换的次数，缺页率为5/10=0.5；
页面置换算一次缺页数，

FIFO算法

简介：FIFO（First In First Out）就是先进先出的意思，算法的核心是更换最早进入内存的页面。

以｛1，3，2，1，2，1，5，1，2，3｝为例子，进行FIFO算法演示，假设把三主存块想象成长度为3的数组。开始演示：

1 进入 —> 1（缺1）
3 进入 —> 1 3（最先进入内存的放在前面(左边)）(缺3）
2 进入 —> 1 3 2（缺2）
1 进入 —> 1 3 2（当放入1的时候，已经存在，不需要置换）
2 进入 —> 1 3 2（当放入2的时候，已经存在，不需要置换）
1 进入 —> 1 3 2（当放入1的时候，已经存在，不需要置换）
5 进入 —> 3 2 5 （进行页面置换，1是最早进去内存所以换出）
1 进入 —> 2 5 1（进行页面置换，3是最早进去内存所以换出）
2 进入 —> 2 5 1（当放入2的时候，已经存在，不需要置换）
3 进入 —> 5 1 3（进行页面置换，5是最少使用的所以推出）

总共进行了三次页面置换，所以缺页数=3+3=6，这个3代表前三个缺的，3代表置换的次数，缺页率为6/10=0.6；

OPT算法

简介：从主存中移出永远不再需要的页面，如果没有这样的页面存在，那就选择最长时间不需要访问的页面，来保证最低的缺页率。

以｛1，3，2，1，2，1，5，1，2，3｝为例子，进行LRU算法演示，假设把三主存块想象成长度为3的数组。开始演示：

1 进入 —> 1（缺1）
3 进入 —> 1 3（下次出现1的下标比下次出现的3的下标小，所以把3放后面(右边)）(缺3）
2 进入 —> 1 2 3（下次出现1的下标比下次出现的3的下标小，下次出现2的下标比下次出现3的下标小，下次出现1的下标比下次出现2的下标小，所以把3放最后面(最右边)，把1放在最前面(最左边)）（缺2）
1 进入 —> 2 1 3（当放入1的时候，已经存在，不需要置换）
2 进入 —> 1 2 3（当放入2的时候，已经存在，不需要置换）
1 进入 —> 1 2 3（当放入1的时候，已经存在，不需要置换）
5 进入 —> 1 2 5 （进行页面置换，3下次出现的下标比1和2都小，换出）
1 进入 —> 2 1 5（当放入1的时候，已经存在，不需要置换）
2 进入 —> 2 1 5（当放入2的时候，已经存在，不需要置换）
3 进入 —> 3 2 1（进行页面置换，2或者1或者5任选一个置换）

总共进行了两次页面置换，所以缺页数=3+2=5，这个3代表前三个缺的，2代表置换的次数，缺页率为5/10=0.5；

都看到这里了，不考虑点个赞再走嘛？

置换策略OPT算法的实现

最佳（OPT）

OPT策略选择置换下次访问当前时间最长的那些页
可以看出该算法能导致最少的缺页中断，但是由于它要求操作系统必须知道将来的事件。显然这是不可能实现的。但是它仍能作为一种标准来衡量其他算法的性能。
下图给出了关于OPT策略的一个例子，该例子假设固定的为该进程分配3个页框（驻留集合大小固定）。进程的执行需要访问5个不同的页，运行该程序需要的页地址的顺序为：
2，3, 2, 1, 5, 2, 4, 5, 3 , 2 , 5 , 2
这意味着访问的第一个页是2，第二个页是3，依次类推。当页框分配满了以后，OPT策略产生3次缺页中断。

代码实现及注释

选择永不使用或者未来最长时间不被使用的页面置换
每次操作完之后重置队列
2 3 2 1 5 2 4 5 3 2 5 2

#include <deque>
#include <cstdio>
#include <algorithm>
#include<iostream>
using namespace std;
struct opt
{
	int value;//值 
	int time;//时间 
};
const int maxn = 105;
int a[maxn];
int main()
{
	deque<opt>  dq;//定义一个队列
	deque<opt >::iterator pos;//定义迭代器
	int numyk, numqueye = 0;
	cout << "请输入物理页框块数:";
	cin >> numyk;//物理页框块数

	int n;
	cout << endl << "请输入页面走向个数：";
	cin >> n;//一共访问页面的个数

	for (int i = 0; i < n; i++)//依次输入页面的页号
	{
		cin >> a[i];
	}

	for (int i = 0; i < n; i++)//遍历要访问的页
	{
		cout << "第" << i << "个" << endl;
		int in;
		in = a[i];//获取当前页面的页号并赋值给in
		if (dq.size() < numyk)//如果存在多余页框
		{
			int flag = 0;
			for (pos = dq.begin(); pos != dq.end(); pos++)
				if ((*pos).value == in)//存在元素和它相同
				{
					flag = 1;
					break;
				}  //存在该元素
			if (!flag) //如果页框中不存在此元素
			{
				opt temp;
				temp.value = in;//当前页号赋值给temp的value
				int f = 0;//标记值初始化为0
				for (int j = i + 1; j < n; j++)//依次遍历后面的页面的页号
					if (a[j] == in)//如果匹配到了相同的页号
					{
						f = 1;//标记值置为1
						temp.time = j - i;//记录距离即是时间距离
						break;
					}
				if (!f)//后面没有找到和当前页面页号相同的页
				{
					temp.time = n;//时间距离置为最大值n
				}
				dq.push_back(temp);//把当前的temp入队
			}
		}
		else//如果不存在多余页框
		{
			int flag = 0;//初始化标记值为0
			for (pos = dq.begin(); pos != dq.end(); pos++)//迭代器遍历队列
				if ((*pos).value == in)//匹配到页号相同
				{
					flag = 1;//标记值置为1
					break;
				}//存在该元素
			if (!flag) //如果不存在此元素 则置换time最大的项
			{
				numqueye++;//缺页数+1
				int m = dq.front().time;//获取队列的头部元素
				cout << "m初始值为" << m;
				deque<opt >::iterator mp = dq.begin();//注意此处千万注意初始化 否则有可能erase找不到对象崩溃 
				for (pos = dq.begin(); pos != dq.end(); pos++)
				{
					cout << (*pos).value << (*pos).time << endl;
					if ((*pos).time > m)//寻找后面页面元素中的时间值最大的页面元素的位置
					{
						cout << "迭代";
						mp = pos;//时间距离值最大的页面元素的位置
						m = (*pos).time;
					}
				}
				opt temp;
				temp.value = in;//把要换入的页面的页号赋值给temp的value
				int f = 0;//初始化标记值
				dq.erase(mp);//把队列中的这个页元素(时间距离最大的)删除出去
				for (int j = i + 1; j < n; j++)//往后遍历页面的页号
					if (a[j] == in)//后面找到和当前页面页号相同的页
					{
						f = 1;//标记值置为1
						temp.time = j - i;//计算时间距离
						break;
					}
				if (!f)//后面找不到和当前页面页号相同的页
				{
					temp.time = n;//把页面的个数赋值给时间
				}
				dq.push_back(temp);//把当前的temp入队列
			}
		}
		//每次之后重置，重新计算
		for (pos = dq.begin(); pos != dq.end(); pos++)//迭代器遍历队列
		{
			cout << "队列中的元素为" << (*pos).value << endl;
			int f = 0;//标记值初始化为0
			for (int j = i + 1; j < n; j++)//往后遍历页面的页号
				if (a[j] == (*pos).value)//后面找到和当前页面页号相同的页
				{
					f = 1;//标记值置为1
					(*pos).time = j - i;//计算出时间距离
					break;
				}
			if (!f)//后面找不到和当前页面页号相同的页
			{
				(*pos).time = n;//把页面的个数赋值给时间
			}
		}

	}
	cout << "OPT缺页次数为:" << numqueye << endl;
	cout << "OPT缺页中断率为:" << (double)numqueye * 1.0 / n << endl;
}

运行截图

回车！

实验题目：

OPT算法实验

实验内容：

已知页面访问序列，采用OPT页面置换算法，求缺页次数、页面置换次数和缺页率。

实验目的：

通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。

实验原理：问题分析及算法设计（流程图）

实验源代码：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>

int toNextPageLen[50];//当前页面位置下一次被访问的位置,下标为当前页面位置,值为下一次访问位置 
//OPT算法 
void OPT(int page_access[],int PBC,int PAC,int result[][50]){
	int k = 0;
	int nextPageAccessIndex[50];//存储当前页面的位置,作为该页面上一次被访问的下一次访问位置 ,下标为页面,值为下一次访问位置 
	memset(nextPageAccessIndex,0,sizeof(nextPageAccessIndex));//初始化为0,代表没再访问过 
	//1.获取当前位置页面下次访问该页面的位置 
	for(int i = PAC-1; i>=0; i--){
		int nextIndex = nextPageAccessIndex[page_access[i]]; 
		if(nextIndex <= 0){//没在访问过则位置设为无穷 
			toNextPageLen[i] = INT_MAX;
		}else{
			toNextPageLen[i] =  nextIndex;
		}
		nextPageAccessIndex[page_access[i]] = i;
	}
	
	//2.计算每一次访问的每个物理块存放的当前页面 
	int flagBlock[50];//存储页面是否在物理块中,用于去重,下标为页面,值为访问位置 
	memset(flagBlock,-1,sizeof(flagBlock));//不存在物理块中为-1 
	for(int i = 0 ; i < PAC; i++){//遍历访问位置 
		int len = 0;//存储下一次访问该页的最大长度 
		int block = -1;//要替换的物理块中页面 
		
		if(flagBlock[page_access[i]]!=-1){//如果存在物理块中,直接复制前一次数据 
			for(int j = 0; j < k; j++){
				result[j][i] = result[j][i-1];
			}
			flagBlock[page_access[i]] = i; 
			continue;
		}
		for(int j = 0; j < PBC; j++){//遍历物理块 
			if(k < PBC){//如果当前使用的物理块数少于总共物理块数,复制上一次访问页面,在剩下的物理块中添加当前页面 
				if(j == k){//如果为新的物理块,直接存储当前页面 
					result[k][i] = page_access[i];//存储当前页面 
					flagBlock[page_access[i]] = i;// 标记为存在物理块中 
					k++; //使用的物理块数+1
					result[PBC][i] = 1;  //判断是否缺页,有增加则缺页 
					break;
				}else{//复制上一次的页面 
					result[j][i] = result[j][i-1];
				}
			}else{//如果物理块满 
				result[j][i] = result[j][i-1];//复制上一次页面 
				int s = toNextPageLen[flagBlock[result[j][i-1]]]-i;
			
				if(len < s){//找到下次访问最长页面替换 ,即判断物理块中页面 上次的下标 的下一次访问位置减去当前位置,得到距离长度 
					block = j;
					len = s;
				}
			}
		}
		if(block!=-1){
			flagBlock[result[block][i]] = -1;
			flagBlock[page_access[i]] = i;
			result[block][i] = page_access[i];//替换下次访问最长的页面 
			result[PBC][i] = 1;
		}
	}
}
int main(){
	int PBC;//物理块数 physical block count 
	int PAC;//页面访问次数 Page access count 
	int page_access[50];//存储访问的页面,下标代表第几次访问 
	int result[50][50];//0~PBC-1行0~PAC-1列代表每个物理块存储每次访问的页面,PBC行存储是否缺页,是为1,否为0 
	memset(result, -1, sizeof(result)); 
	printf("请输入物理块数:"); 
	scanf("%d",&PBC);
	printf("请输入访问次数:"); 
	scanf("%d",&PAC);
	for(int i = 0 ; i < PAC; i++){
		printf("请输入第%d次访问的页面:",i+1);
		scanf("%d",&page_access[i]); 
	}
	
	//OPT 
	OPT(page_access, PBC, PAC, result);
	
	//输出 
	printf("\n\n页面访问\t");
	for(int i = 0 ; i < PAC; i++){
		printf("%d\t",page_access[i]);
	}
	printf("\n");
	for(int i = 0; i < PBC; i++){
		printf("物理块%d\t\t",i+1);
		for(int j = 0; j < PAC; j++){
			if(result[i][j]!=-1&&result[PBC][j]!=-1){
				printf("%d\t",result[i][j]);
			}else{
				printf("\t");
			}
		}
		printf("\n");
	}
	int lack_page_number = 0;//缺页次数 
	printf("是否缺页\t");
	for(int i = 0; i < PAC; i++){
		printf("%c\t",result[PBC][i]==1?'Y':'N');
		if(result[PBC][i]==1)lack_page_number++;
	} 
	printf("\n"); 
	
	int exchange_numbber = lack_page_number - PBC;
	double lack_page_rate = lack_page_number/(double)PAC;
	printf("缺页次数: %d\n", lack_page_number);
	printf("置换次数: %d\n",exchange_numbber);
	printf("缺页率: %0.2lf%%\n",lack_page_rate) ;

}
/*
3
12
2
3
2
1
5
2
4
5
3
2 
5 
2

3
20
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
*/

实验结果：（截图）

实验总结：（心得体会）

通过此次实验，我熟练掌握了几种页面置换算法，自己独立写出了OPT算法的代码实现，对虚拟存储技术的特点有了更深的了解。