最佳置换算法（OPT）：从主存中移出永远不再需要的页面；如无这样的页面存在，则选择最长时间不需要访问的页面。于所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。 

最佳置换算法可以用来评价其他算法。假定系统为某进程分配了三个物理块，并考虑有以下页面号引用串：
    7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
进程运行时，先将7, 0, 1三个页面依次装入内存。进程要访问页面2时，产生缺页中断，根据最佳置换算法，选择第18次访问才需调入的页面7予以淘汰。然后，访问页面0时，因为已在内存中所以不必产生缺页中断。访问页面3时又会根据最佳置换算法将页面1淘汰……依此类推，如图所示。从图中可以看出釆用最佳置换算法时的情况。

#include<iostream>
#include<list>
#include<vector>
#include<iterator>
#include<fstream>
#include<algorithm>
using namespace std;

class Optimal
{
public:
	int index;
	int dis;
public:
	friend istream & operator>>(istream & i, Optimal&o);
	friend ostream & operator<<(ostream &s, const Optimal&o);
	Optimal(int i)
	{
		this->index = i;
		dis = 0;
	}
	Optimal()
	{
		dis = 0;
	}
	~Optimal()
	{

	}
	bool operator<(Optimal&s)
	{
		if (this->dis < s.dis)
			return true;
		return false;
	}
	bool operator>(Optimal&s)
	{
		if (this->dis > s.dis)
			return true;
		return false;
	}
	bool operator==(const Optimal&s)
	{
		if (this->dis==s.dis  )
			return true;
		return false;
	}
};
istream & operator>>(istream & i, Optimal&o)
{
	i >> o.index;
	return i;
}
ostream & operator<<(ostream &s,const  Optimal&o)
{

	s <<"["<<o.index << "\t" <<"下次位置："<<o.dis <<"]";

	return s;
}

void main()
{
	fstream out("data.txt");
	list<Optimal> v;
	list<Optimal> w;
	copy(istream_iterator<Optimal>(out), istream_iterator<Optimal>(), back_inserter(v));
	//copy(v.begin(),v.end(),ostream_iterator<Optimal>(cout,"\t"));

	while (v.size())
	{
		if (w.size()<3)
		{
			copy(w.begin(), w.end(), ostream_iterator<Optimal>(cout, "\t"));
			cout << endl;
			Optimal p = v.front();
			v.pop_front();
			w.push_front(p);
		}
		else
		{
			bool istrue = false;
			for (auto ib = w.begin(); ib != w.end(); ib++)
			{
				if (ib->index==v.front().index)
				{
					istrue = true;
				}
			}
			if (istrue == false)
			{
				for (auto ib = w.begin(); ib != w.end(); ib++)
				{
					int x = 0;
					for (auto vib = v.begin(); vib != v.end(); vib++)
					{
						if ((*ib).index == (*vib).index)
						{
							break;
						}
						(*ib).dis = x++;
					}
				}
				copy(w.begin(), w.end(), ostream_iterator<Optimal>(cout, "\t"));
				cout << endl;
				list<Optimal>::iterator s = max_element(w.begin(), w.end());
				w.remove(*s);
				Optimal p = v.front();
				v.pop_front();
				w.push_front(p);
			}
			else
			{
				v.pop_front();
			}
		}
	}
	copy(w.begin(), w.end(), ostream_iterator<Optimal>(cout, "\t"));
	cout << endl;
	cin.get();
}

其中data.txt文件内容为

实验结果是

前言

此篇文章是我在B站学习时所做的笔记，大部分图片都是课件老师的PPT，方便复习用。此篇文章仅供学习参考。

提示：以下是本篇文章正文内容

知识总览

最佳置换算法（OPT）

• 最佳置换算法（OPT，Optimal)：每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。
• 最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的。
  
  只有内存块已经都满的情况下，才需要页面置换。因此，在刚开始访问7、0、1这三个页面的时候，虽然它们都没在内存当中，但是由于刚开始那些有空闲的内存块，所以虽然发生了缺页中断，虽然会发生掉页，但是并不会发生页面置换这件事，只有所有的内存块都已经占满之后，再发生缺页的话，那才需要进行页面置换这件事情，因此缺页中断总共发生了9次，但页面置换只发生了6次，前面那三次只是发生了缺页，并没有页面置换，那缺页率的计算也很简单，只需要将缺页中断发生的次数除以总共访问了多少次的页面，就可以得到缺页率。

先进先出置换算法（FIFO）

• 先进先出置换算法（FIFO)：每次选择淘汰的页面是最早进入内存的页面
• 实现方法：把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面即可。队列的最大长度取决于系统为进程分配了多少个内存块。
  
  
• Belady异常―一当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。
• 只有FIFO算法会产生Belady异常。另外，FIFo算法虽然实现简单，但是该算法与进程实际运行时的规律不适应，因为先进入的页面也有可能最经常被访问。因此，算法性能差

最近最久未使用置换算法（LRU)

• 最近最久未使用置换算法（LRU，least recently used)：每次淘汰的页面是最近最久未使用的页面
• 实现方法：赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t。当需要淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面。

该算法的实现需要专门的硬件支持，虽然算法性能好,但是实现困难，开销大

在手动做题时，若需要淘汰页面，可以逆向检查此时在内存中的几个页面号。在逆向扫描过程中最后一个出现的页号就是要淘汰的页面。

时钟置换算法（CLOCK)

• 最佳置换算法性能最好，但无法实现;先进先出置换算法实现简单，但算法性能差；最近最久未使用置换算法性能好，是最接近OPT算法性能的，但是实现起来需要专门的硬件支持，算法开销大。
• 时钟置换算法是一种性能和开销较均衡的算法，又称CLOCK算法，或最近未用算法(NRU，NotRecently Used)
• 简单的CLOCK算法实现方法：为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位置为1。当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出；如果是1，则将它置为0，暂不换出，继续检查下一个页面，若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮捆描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描)

刚开始由于有五个空闲的内存块，所以前五个访问的这个页号13425都可以顺利地放入内存当中，只有在访问到6号页的时候，才需要考虑淘汰某个页面，那么在内存当中的13425这几个页面，会通过链接指针的方式连接成一个这样的循环队列。

那由于接下来要访问六号页面，但是把五个内存块都已经满了，所以需要用clock算法来选择淘汰其中的某个页面。于是会从这个循环队列的队首开始扫描，尝试找到一个访问位为零的页面，并且被扫描过的页面需要把访问为1改为0，所以在经过第一轮的扫描之后，所有的这些页面的访问位都由1置为了0。

在进行第二轮扫描的时候，1号页面的访问位为0，所以会选择淘汰1号页面，于是6号页会装入到1号以前占有的这个内存块当中，并且6号页的访问位会被置为1，然后这个扫描的指针指向下一个页面。

那接下来的访问当中会依次访问到3号和4号页面，那在访问了3号页面你们之后，3号页的访问位需要由0变为1，同样的，在访问了四号页面的时候，需要把4号页的访问位由0变为1。

在之后需要访问7号页，由于此时7号也没有在内存中，所以需要选择淘汰其中的某一个页面，然后把7号也放到内存中，那同样的需要从此时扫描到的这个位置依次的扫描，找到第一个访问位为0的页面，并且扫描过的那些页面的这个访问位需要由1变为0，所以3号和4号在扫描过后，访问位会变为0，

再扫描到2号页面的时候，我发现2号页面的访问位给本来就是0了，因此会选择淘汰2号页面，然后让7号页面放到这个位置，访问位置为1，然后这个扫描的指针再指向下一个页面的位置。

改进型的时钟置换算法

简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上，如果被淘汰的页面没有被修改过，就不需要执行I/O操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存。

• 因此，除了考虑一个页面最近有没有被访问过之外，操作系统还应考虑页面有没有被修改过。在其他条件都相同时，应优先淘汰没有修改过的页面，避免I/O操作。这就是改进型的时钟置换算法的思想。修改位=0，表示页面没有被修改过；修改位=1，表示页面被修改过。
• 为方便讨论，用==（访问位，修改位）==的形式表示各页面状态。如(1，1）表示一个页面近期被访问过，且被修改过。
  

知识回顾与重要考点