OS 页面置换算法

一、要求

对访问串：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6。
驻留集大小分配为1，2，3，4，5，6，7 时，试指出在淘汰算法FIFO、LRU和OPT控制下的页故障数，要求列表显示和比较。开发工具可用C++或自选。

二、算法

#include 
#include 
using namespace std;
/*
   注释话语   
    OPT
	LRU
	FIFO   
	这三种算法分别有着共性
	OPT算法 ：   
	类似于LRU算法，LRU看的之前最久最远未使用的   OPT算法则是看的之后驻留集之中那种最晚出现或者不出现
	算法步骤：    首先
	我们 for 从第一个序号开始 按顺序遍历所有的序号  i 
	  如果当前的序号不在驻留集之中 也就是没有命中 
	  [
	     这里又有两种情况需要考虑  
            1.驻留集没有满 直接将该序列放入其中
			2.驻留级满了    
			[
			   此时我需要从其中找到一个替换 
			   替换的规则是驻留集合之中找到从i开始的后面的所有序列之中未出现或者都出现但是是最晚出现的那个 
			   举个例子 驻留集[1,2]  后面的序列是 1 2 那么要替换的就是2  此时是驻留集中的元素在后面都出现，取最晚出现的
			       驻留集[1,2]  后面的序列是 3 2 那么要替换的就是1  此时是驻留集中的元素1在后面不出现 那么替换未出现的
				   多个未出现的 取从左往右最先判断到的 驻留集[1,2,3]  后面的序列是 3 5 0 那么替换1  因为for是从左往右，判断到
				   第一个未出现的就是我们所需要替换的（我只是偷懒） 
			]		 
	  ] 
	  如果当前的序号在驻留集之中 也就是命中了 此时不需要做出任何操作 命中驻留集合不变 
	FIFO算法：
	   这种就是最为简单的，和之前一样的思路，这里只不过是先进先出
	   for 遍历所有的序列  假设当前到达i
	   [
	      1.当前命中，驻留集和其他地方不作出任何操作
		  2.当前未命中  
		  [
		     1.如果驻留集合没有满，直接放入
			 2.驻留集满了,将最前面的那个移出去，刚刚到的这个序号放到最后 
		  ] 
	   ] 
	LRU算法：
	  根据先前我们对驻留集的了解，离之前使用最远的那个就被替换
	  for 遍历所有的序列  假设当前到达i
	   [
	      1.当前命中，驻留集和其他地方不作出任何操作
	      [
	         这边我们有三种做法   一种是循环队列，就是一个圈，你把所有的驻留集放到圈之中，转到的那个移出去
			 二是每个对应的驻留集中的序列弄一个时间  命中的时间+2 其他的时间-1  但是这样有一种缺点，就是我们知道
			 命中的就是放到驻留集最后，那么加的时间一定要让他变成最大 举个例子： 驻留集[1,2,3,4,5,6] 时间分别是
			 1 2 3 4 5 6如果此时的序列是1，那么1命中，1就是最近的，那么时间要变成驻留集里面最大的，只是加2就达不到最大
			 1+2=3小于6的时间，因为这样的情况可能就是驻留集很大里面有些元素时间就很低，你可能加上也不一定是最大的，
			 这个加上的时间  难以确定，不过对于本实验足够了
			 第三种就是我下面写的 如果命中，我就把他往后面放，这样就能保证时间最短的永远在前面，刚刚命中的始终是最后 
		  ] 
		  2.当前未命中    操作和FIFO操作一样 
		  [
		     1.如果驻留集合没有满，直接放入
			 2.驻留集满了,将最前面的那个移出去，刚刚到的这个序号放到最后 
		  ] 
	   ] 
	   接下来开始代码   里面很多都是时间比较慢的，但是便于理解  这里还有一点，每钟算法本来能重复利用的数组变量我没有用
	   因为我要让这三种算法能够同时输出 
*/
int M[21] = {0,1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6}; /// 这里我是打算从1开始，前面就加上一个0作为无关的序列 
int N[10];/// 驻留集实验中最大为7   这个是针对FIFO算法的 
int N_1[10];///  驻留集实验中最大为7   这个是针对LRU算法的 
int N_2[10];///  驻留集实验中最大为7   这个是针对OPT算法的 
int cnt = 0;/// 当前驻留集大小  这个是针对FIFO算法的 
int cnt_1 = 0;///  驻留集实验中最大为7   这个是针对LRU算法的
int cnt_2 = 0;///  驻留集实验中最大为7   这个是针对OPT算法的 
int all = 0;/// 缺页总数 这个是针对FIFO算法的
int all_1 = 0;///  这个是针对LRU算法的
int all_2 = 0;///  这个是针对OPT算法的 
int m;/// 驻留集大小 
void FIFO_out(bool f)
{
	puts("-------------------------------------------------------------------------------");
	if (!f)
	{
		cout<<"已命中,当前驻留集情况：[";
		for (int k=0;kt)/// 用来说明当前这个驻留集中的该元素在后面出现的位置更远 
								{
									t = k;
									idx = w;	
								}
								break;
							}
						}
						///cout<>m;
   FIFO();
   
   return 0;	
} 
/// 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6

三、结果