最近最久未使用

最近最久未使用（LRU）的页面置换算法是根据页面调入内存后的使用情况做出决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t。当需要淘汰一个页面时，选择现有也面中t值最大的，即最近最久未使用的页面予以淘汰。

访问页面	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
物理块1	7	7	7	2		2		4	4	4	0			1		1		1
物理块2		0	0	0		0		0	0	3	2			3		0		0
物理块3			1	1		3		3	2	2	3			2		2		7

#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;
	list<Optimal> l;
	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)
		{
			Optimal p = v.front();
			v.pop_front();
			w.push_front(p);
			l.push_back(p);
			copy(w.begin(), w.end(), ostream_iterator<Optimal>(cout, "\t"));
			cout << endl;
		}
		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 = l.rbegin(); vib != l.rend(); vib++)
					{
						if ((*ib).index == (*vib).index)
						{
							break;
						}
						(*ib).dis = ++x;
					}
				}
				list<Optimal>::iterator s = max_element(w.begin(), w.end());
				w.remove(*s);
				Optimal p = v.front();
				v.pop_front();
				l.push_back(p);
				w.push_front(p);
				copy(w.begin(), w.end(), ostream_iterator<Optimal>(cout, "\t"));
				cout << endl;
			}
			else
			{
				Optimal p = v.front();
				v.pop_front();
				l.push_back(p);
			}
		}
	}
	cin.get();
}

data.txt文件

测试结果: