实验题目：
 
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算法的代码实现，对虚拟存储技术的特点有了更深的了解。

1.背景
 
进程运行时，若其访问的页面不在内存而需将其调入，但内存已无空闲空间时，就需要从内存中调出一页程序或数据，送入磁盘的对换区。
 
选择调出页面的算法就称为页面置换算法。好的页面置换算法应有较低的页面更换频率，也就是说，应将以后不会再访问或者以后较长时间内不会再访问的页面先调出。
 
 
 
2.置换策略理论
 
 
 
 1. 最佳置换算法(OPT)
 
最佳(Optimal, OPT)置换算法所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率。但由于人们目前无法预知进程在内存下的若千页面中哪个是未来最长时间内不再被访问的，因而该算法无法实现。
 
 2. 先进先出(FIFO)页面置换算法
 
优先淘汰最早进入内存的页面，亦即在内存中驻留时间最久的页面。该算法实现简单，只需把调入内存的页面根据先后次序链接成队列，设置一个指针总指向最早的页面。但该算法与进程实际运行时的规律不适应，因为在进程中，有的页面经常被访问。
 
 3. 最近最久未使用(LRU)置换算法
 
选择最近最长时间未访问过的页面予以淘汰，它认为过去一段时间内未访问过的页面，在最近的将来可能也不会被访问。该算法为每个页面设置一个访问字段，来记录页面自上次被访问以来所经历的时间，淘汰页面时选择现有页面中值最大的予以淘汰。
 
3.策论比较
 
1. FIFO，Optimal，LRU这三种置换算法的优劣？
 
•优点：
 
    ① FIFO页面置换算法实现简单，要求的硬件支持较少。
 
    ② Optimal页面置换算法可保证获得最低的缺页率，并且可以用来评价其他算法。
 
    ③ LRU页面置换算法利用“最近的过去”代替“最近的将来”，以此模拟Optimal算法，是实际应用中缺页率最低的算法。
 
 
 
•缺点：
 
    ① FIFO算法所依据的条件是各个页面调入内存的时间，而页面调入内存的先后并不能反映页面的使用情况。
 
    ② Optimal算法是理论上的算法，目前该算法是无法实现的。
 
    ③LRU算法是根据各页以前的使用情况，来代替各页面将来的使用情况，进而判断要替换出去的页面，而页面过去和将来的         走向之间并无必然的联系；其实际应用时要求较多的硬件支持，因而多采用近似算法。
 
 
 
2. 在什么情况下采用哪种置换算法更有利？
 
    •FIFO算法在按线性顺序访问地址空间时使用；当硬件水平不足时，FIFO算法也可作为首选。
 
    •OPT算法可以进行模拟实验分析或理论分析。
 
    •当系统有寄存器或栈的硬件支持时，利用LRU算法可以获得最低缺页率。
 
 
 
各个csdn太多类似的解释，就我自己百度的来看，关于OPT这个算法的解释模型基本上都是错误的。PS:可能有对的。
 
以下是我浅薄的解释：
 
 
 
   在弄清楚这些个页面置换算法之前要先弄清楚两个概念：
 
1：缺页（也称缺页中断）
 
这是百度百科的解释：
 
 
这是我的解释（大家随便看看）
 
缺页：就是指按照访问顺序去访问“页面”时，但发现物理内存中并没有（对应的“页面‘号’”），所以发生了缺页中断：需要调入内存之后才可以继续运行。
 
2:页面置换：（页面置换算法）
 
百度百科：
 
在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法
 
简单来说就是就是替换页面
 
 
 
好在了解上面之后在来说今天的重点：
 
1：OPT:最佳(Optimal, OPT)置换算法所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率. 
 
 
 
 
 
 
自我小结论：空物理块情况下：页面置换=缺页减-物理块数（一开始就要缺页3次）。
 
这个是：网络上一个博客跟我的结论是一样的
 
https://www.cnblogs.com/ctrltab/p/10013815.html
 
最佳置换算法（optimal replacement，OPT）是从内存中选择今后不再访问的页面或者在最长一段时间后才需要访问的页面进行淘汰。如下例子：
 
根据页面走向依次处理，得到最终的置换结果如下图表，整个页面缺页次数为7，缺页率为7/12=58%。
 
 
 
 
 
 
https://blog.csdn.net/qq_34777600/article/details/79508613
 
这个csdn给的列子是错误的（opt）
 
 
 
2：先进先出(FIFO)页面置换算法
 
优先淘汰最早进入内存的页面，亦即在内存中驻留时间最久的页面。
 
 
 
 
 
 
 
 
 
 
 
结论：1：FIFO的页面置换刚好是OPT的一倍（相同的情况和访问顺序下）
 
          2：：空物理块情况下：页面置换=缺页减-物理块数（一开始就要缺页3次）。
 
 
 
 
 
 3. 最近最久未使用(LRU)置换算法
 
选择最近最长时间未访问过的页面予以淘汰，它认为过去一段时间内未访问过的页面，在最近的将来可能也不会被访问
 
 
 
 
 
 
 
 
结论：
 
1：原始方法是 加一个t（时间戳）来记录上次访问后到现在所经历的时间，需要淘汰时，选择t最大的那个淘汰。
 
2：ava8以后实现了hashmap+双向link链表实现了。、
 
 
 
 
 
链接如下： http://www.imooc.com/article/details/id/285117
 
https://www.cnblogs.com/hongdada/p/10406902.html
 
 
 
 
 
 
扩展：
 
4:LFU 最少使用置换算法:
 
            LFU算法的访问图与LRU算法的访问图是一样的
 
 
 
最少使用（LFU）置换算法
 
在采用最少使用置换算法时，应为在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。该置换算法选择在之前时期使用最少的页面作为淘汰页。由于存储器具有较高的访问速度，例如100 ns，在1 ms时间内可能对某页面连续访问成千上万次，因此，通常不能直接利用计数器来记录某页被访问的次数，而是采用移位寄存器方式。每次访问某页时，便将该移位寄存器的最高位置1，再每隔一定时间(例如100 ns)右移一次。这样，在最近一段时间使用最少的页面将是∑Ri最小的页。LFU置换算法的页面访问图与LRU置换算法的访问图完全相同；或者说，利用这样一套硬件既可实现LRU算法，又可实现LFU算法。应该指出，LFU算法并不能真正反映出页面的使用情况，因为在每一时间间隔内，只是用寄存器的一位来记录页的使用情况，因此，访问一次和访问10 000次是等效的。 [3]
 
1，基本原理
 
LFU（Least Frequently Used）算法根据数据的历史访问频率来淘汰数据，其核心思想是“如果数据过去被访问多次，那么将来被访问的频率也更高”。
 
LFU的每个数据块都有一个引用计数，所有数据块按照引用计数排序，具有相同引用计数的数据块则按照时间排序。
 
 
 
具体实现如下：
 
 
 
 
 
 
 
 
 
 
1. 新加入数据插入到队列尾部（因为引用计数为1）；
 
2. 队列中的数据被访问后，引用计数增加，队列重新排序；
 
3. 当需要淘汰数据时，将已经排序的列表最后的数据块删除。
 
 

 
原文链接：https://www.jianshu.com/p/544ee20e307c
 
转载于:https://www.cnblogs.com/qy-blogs/p/10062309.html

这是一种理想情况下的页面置换算法，但实际上是不可能实现的。该算法的基本思想是：发生缺页时，有些页面在内存中，其中有一页将很快被访问（也包含紧接着的下一条指令的那页），而其他页面则可能要到10、100或者1000条指令后才会被访问，每个页面都可以用在该页面首次被访问前所要执行的指令数进行标记。最佳页面置换算法只是简单地规定：标记最大的页应该被置换。这个算法唯一的一个问题就是它无法实现。当缺页发生时，操作系统无法知道各个页面下一次是在什么时候被访问。虽然这个算法不可能实现，但是最佳页面置换算法可以用于对可实现算法的性能进行衡量比较。