操作系统—页面置换算法C++实现

页面置换算法: 资源包含三个算法：OPT---最佳置换算法、//FIFO---先进先出、//LRU---最近最久未使用 操作：用户输入物理块数、页面待要访问的个数、每个页面编号，计算出缺页数、置换数、缺页率 语言：C++ 运行环境：Visual Studio 2013/更高版本

//OPT---最佳置换算法
#if 1
//by liuhao
//选择永不使用或者最长时间不被使用的页面进行置换
//每次操作完之后重置队列
// 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
//结果：缺页数：9   置换数：6   缺页率：45%
#include 
#include 
#include 
#include //sort（）头文件
using namespace std;

struct pages
{
	int value;
	int time;
};
bool GreaterSort（pages a pages b）
{
	return （a.time > b.time）;
}


int main（）
{
	deque  dq;
	deque::iterator pos;
	int blockNum;//物理块数
	int pageNum;//访问页面个数
	int missPageNum = 0;//缺页数
	int pageLabel;//当前输入的页面标签
	vector pageList;//页面访问序列

	cout << “****************** OPT ********************“ << endl;

	cout << “请输入物理页框块数:“ << endl;
	cin >> blockNum;

	cout << “\n请输入页面走向个数：“ << endl;
	cin >> pageNum;

	cout << “\n请输入访问页面序列：“ << endl;
	for （int i = 0; i < pageNum; i++）
	{
		cin >> pageLabel;
		pageList.push_back（pageLabel）;
	}


	for （int i = 0; i < pageNum; i++）
	{
		if （dq.size（） < blockNum）//存在多余页框
		{
			bool flag = false;
			for （pos = dq.begin（）; pos != dq.end（）; pos++）
			{
				if （（*pos）.value == pageList[i]）//存在元素和它相同
				{
					flag = true;
					break;
				}  //存在该元素
			}

			if （!flag） //不存在此元素
			{
				missPageNum++;//缺页数+1
				pages temp;
				temp.value = pageList[i];

				bool flag2 = false;
				for （int j = i + 1; j < pageNum; j++）
				{
					if （pageList[j] == pageList[i]）
					{
						flag2 = true;
						temp.time = j - i;
						break;
					}
				}
				if （!flag2）
					temp.time = pageNum;//如果后面序列没有出现，time设置为总访问页面个数
				dq.push_back（temp）;
			}
		}
		else //不存在多余页框
		{
			bool flag = false;
			for （pos = dq.begin（）; pos != dq.end（）; pos++）
			{
				if （（*pos）.value == pageList[i]）
				{
					flag = true;
					break;
				}  //存在该元素
			}

			if （!flag） //不存在此元素 则置换time最大的项
			{
				missPageNum++;//缺页数+1
				// 按照time从大到小排序
				sort（dq.begin（） dq.end（） GreaterSort）;
				int maxTime = dq.front（）.time;//第物理块中第一个页面的time
				dq.pop_front（）;//time值最大的出队列

				pages temp;
				temp.value = pageList[i];
				bool flag2 = false;

				for （int j = i + 1; j < pageNum; j++）
				{
					if （pageList[j] == pageList[i]）
					{
						flag2 = true;
						temp.time = j - i;
						break;
					}
				}

				if （!flag2）
					temp.time = pageNum;
				dq.push_back（temp）;
			}
		}
		//每次之后重置
		cout << endl << “第“ << i + 1 << “个页面进入队列中的元素为：“;
		for （pos = dq.begin（）; pos != dq.end（）; pos++）
		{
			cout << （*pos）.value << “  “;
			int flag = false;
			for （int j = i + 1; j < pageNum; j++）
			if （pageList[j] == （*pos）.value）
			{
				flag = true;
				（*pos）.time = j - i;
				break;
			}
			if （!flag）
				（*pos）.time = pageNum;
			//cout << “<“ << （*pos）.value << ““ << （*pos）.time << “>   “;
		}
		cout << endl << endl;
	}
	cout << “OPT缺页次数为：“ << missPageNum << endl;
	cout << “OPT页面置换次数：“ << missPageNum - 3 << endl;
	cout << “OPT缺页中断率为：“ << （double）missPageNum / pageNum * 100 << “%“ << endl;
	system（“pause“）

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2019-05-13 17:31  页面置换算法\
     目录           0  2019-05-13 16:50  页面置换算法\Debug\
     文件      115200  2019-05-13 17:36  页面置换算法\Debug\页面置换算法.exe
     文件      576792  2019-05-13 17:36  页面置换算法\Debug\页面置换算法.ilk
     文件     1412096  2019-05-13 17:36  页面置换算法\Debug\页面置换算法.pdb
     文件          22  2019-05-13 17:31  页面置换算法\页面置换算法.opensdf
     文件     7864320  2019-05-13 17:32  页面置换算法\页面置换算法.sdf
     文件        1000  2019-05-11 11:08  页面置换算法\页面置换算法.sln
     文件       27648  2019-05-11 23:57  页面置换算法\页面置换算法.v12.suo
     目录           0  2019-05-13 17:36  页面置换算法\页面置换算法\
     目录           0  2019-05-13 17:36  页面置换算法\页面置换算法\Debug\
     文件      400320  2019-05-13 17:36  页面置换算法\页面置换算法\Debug\main.obj
     文件      486400  2019-05-13 17:36  页面置换算法\页面置换算法\Debug\vc120.idb
     文件      446464  2019-05-13 17:36  页面置换算法\页面置换算法\Debug\vc120.pdb
     文件        2754  2019-05-13 17:36  页面置换算法\页面置换算法\Debug\页面置换算法.log
     目录           0  2019-05-13 17:36  页面置换算法\页面置换算法\Debug\页面置换算法.tlog\
     文件        1238  2019-05-13 17:36  页面置换算法\页面置换算法\Debug\页面置换算法.tlog\cl.command.1.tlog
     文件       18940  2019-05-13 17:36  页面置换算法\页面置换算法\Debug\页面置换算法.tlog\CL.read.1.tlog
     文件         452  2019-05-13 17:36  页面置换算法\页面置换算法\Debug\页面置换算法.tlog\CL.write.1.tlog
     文件        5862  2019-05-13 17:36  页面置换算法\页面置换算法\Debug\页面置换算法.tlog\link.command.1.tlog
     文件        8262  2019-05-13 17:36  页面置换算法\页面置换算法\Debug\页面置换算法.tlog\link.read.1.tlog
     文件         430  2019-05-13 17:36  页面置换算法\页面置换算法\Debug\页面置换算法.tlog\link.write.1.tlog
     文件         195  2019-05-13 17:36  页面置换算法\页面置换算法\Debug\页面置换算法.tlog\页面置换算法.lastbuildstate
     文件        7981  2019-05-13 17:36  页面置换算法\页面置换算法\main.cpp
     文件        4095  2019-05-11 13:13  页面置换算法\页面置换算法\页面置换算法.vcxproj
     文件         945  2019-05-11 13:13  页面置换算法\页面置换算法\页面置换算法.vcxproj.filters