概览：OPT、LRU、FIFO算法的实现

实验内容

（1）假设每个页面中可存放10条指令，分配给一作业的内存块数为4。

（2）用C语言模拟一作业的执行过程。该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟过程中，如果所访问的指令已经在内存中，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块中均已装入该作业，则需进行页面置换。最后显示其物理地址，并转下一条指令。在所有320条指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。

（3）置换算法：请分别考虑OPT、FIFO和LRU算法。

（4）作业中指令的访问次序按下述原则生成：

50%的指令是顺序执行的。
25%的指令是均匀分布在前地址部分。
25%的指令时均匀分布在后地址部分。

具体的实施办法是：
① 在[0，319]之间随机选取一条起始执行指令，其序号为m；
② 顺序执行下一条指令，即序号为m+1的指令；
③ 通过随机数，跳转到前地址部分[0，m-1]中的某条指令处，其序号为m1；
④ 顺序执行下一条指令，即序号为m1+1的指令；
⑤ 通过随机数，跳转到后地址部分[m1+2，319]中的某条指令处，其序号为m2；
⑥ 顺序执行下一条指令，即序号为m2+1的指令；
⑦ 重复跳转到前地址部分、顺序执行、跳转到后地址部分、顺序执行的过程，直至执行320条指令。

思路

FIFO算法是如果可用内存满了，优先替换掉在内存中存在时间最长的页面
对应的就是一个队列，容量为4，先进先出

如果队列的容量没有满
	检查是否在队列中，如果在，无操作
	如果不在，直接加入尾部队列，count+1
如果队列容量满了
	检查是否在队列中，如果在，无操作
	如果不在，首部出队列，尾部进队列，count+1


LRU算法 —— 最近最久未使用，即淘汰掉最近一段时间内没被使用的块
即在一个队列里，如果没被使用就在队列中，如果被使用了就取出加入到队尾

如果队列的容量没有满
	检查是否在队列中，如果在，取出这一块，加入到队列尾部
	如果不在，直接加入尾部队列，count+1
如果队列容量满了
	检查是否在队列中，如果在，取出这一块，加入到队列尾部
	如果不在，首部出队列，尾部进队列，count+1

OPT算法 —— 最佳适应算法
向后搜索待执行的队列，比较当前内存中哪条指令最后被执行
如果内存未满
	检查是否在内存之中，在的话，无操作
	不在的话，加入内存之中，count+1
如果内存满了
	检查是否在内存之中，在的话，无操作
	不在的话，向后搜索待执行的指令，查找在内存之中的指令哪一条最晚被执行或者永不被执行，替换掉，count+1

代码

#include <stdlib.h>
#include <iostream>
#include <ctime>
#include <conio.h>
#include <set>

using namespace std;                                                                                                                                   

//Memory
typedef int Memory;

bool FindMemoryById(Memory MyMemory[4],int memoryNum,int id)
{
	for (int i = 0; i <= memoryNum-1; i++)
	{
		if (MyMemory[i] == id)
		{
			return true;
		}
	}
	return false;
}

int GetIndexById(Memory MyMemory[4], int memoryNum, int id)
{
	for (int i = 0; i <= memoryNum - 1; i++)
	{
		if (MyMemory[i] == id)
		{
			return i;
		}
	}
}

void Print(Memory MyMemory[4], int memoryNum)
{
	for (int i = 0; i <= memoryNum - 1; i++)
	{
		cout << MyMemory[i] << " ";
	}
	cout << endl;
}

int GetFirstLargeIndex(int arr[4])
{
	int maxNum = arr[0];
	int maxNumIndex = 0;
	for (int j = 1; j < 4; j++)
	{
		if (maxNum < arr[j])
		{
			maxNum = arr[j];
			maxNumIndex = j;
		}
	}
	return maxNumIndex;
}

int GetLastIndexOrdList(Memory MyMemory[4], int orderList[320], int index)
{
	int LastIndex[4] = {999,999,999,999};
	int LastIndexNum = 0;
	for (int i=index;i<320;i++)
	{
		for (int j = 0; j < 4; j++)
		{
			if (MyMemory[j] == orderList[i])
			{
				if (LastIndex[j] == 999)
				{
					LastIndex[j] = i;
					LastIndexNum++;
					break;
				}
				else
				{
					break;
				}
			}
		}
		if (LastIndexNum == 4) break;
	}
	return GetFirstLargeIndex(LastIndex);
}

//FIFO算法
void FIFO(int orderList[320])
{
	int count = 0;//计算缺页次数
	Memory MyMemory[4];
	int memoryNum = 0;//内存已经占用的数量
	for (int i = 0; i < 320; i++)
	{
		if (memoryNum < 4)//如果内存未满
		{
			if (!FindMemoryById(MyMemory,memoryNum,orderList[i]))
			{
				//不在内存中
				MyMemory[memoryNum] = orderList[i];
				memoryNum++;
				count++;
			}
		}
		else
		{
			if (!FindMemoryById(MyMemory, memoryNum, orderList[i]))
			{
				for (int j = 0; j < 3; j++)
				{
					MyMemory[j] = MyMemory[j + 1];
				}
				MyMemory[3] = orderList[i];
				count++;
			}
		}
		//Print(MyMemory,memoryNum);
	}
	cout << "FIFO算法的缺页率为：" << double(count) / 320 << endl;
}

//LRU算法
void LRU(int orderList[320])
{
	int count = 0;//计算缺页次数
	Memory MyMemory[4];
	int memoryNum = 0;//内存已经占用的数量
	for (int i = 0; i < 320; i++)
	{
		if (memoryNum < 4)//如果内存未满
		{
			if (FindMemoryById(MyMemory, memoryNum, orderList[i]))
			{
				//在内存中
				for (int j = GetIndexById(MyMemory, memoryNum, orderList[i]); j < memoryNum - 1; j++)
				{
					MyMemory[j] = MyMemory[j + 1];
				}
				MyMemory[memoryNum-1] = orderList[i];
			}
			else
			{
				//不在内存中
				MyMemory[memoryNum] = orderList[i];
				memoryNum++;
				count++;
			}
		}
		else
		{
			if (FindMemoryById(MyMemory, memoryNum, orderList[i]))
			{
				//在内存中
				for (int j = GetIndexById(MyMemory, memoryNum, orderList[i]); j < 3; j++)
				{
					MyMemory[j] = MyMemory[j + 1];
				}
				MyMemory[3] = orderList[i];
			}
			else
			{
				//不在内存中
				for (int j = 0; j < 3; j++)
				{
					MyMemory[j] = MyMemory[j + 1];
				}
				MyMemory[3] = orderList[i];
				count++;
			}
		}
		//Print(MyMemory, memoryNum);
	}
	cout << "LRU算法的缺页率为：" << double(count) / 320 << endl;
}

//OPT算法
void OPT(int orderList[320])
{
	int count = 0;//计算缺页次数
	Memory MyMemory[4];
	int memoryNum = 0;//内存已经占用的数量
	for (int i = 0; i < 320; i++)
	{
		if (memoryNum < 4)//如果内存未满
		{
			if (!FindMemoryById(MyMemory, memoryNum, orderList[i]))
			{
				//不在内存中
				MyMemory[memoryNum] = orderList[i];
				memoryNum++;
				count++;
			}
		}
		else
		{
			if (!FindMemoryById(MyMemory, memoryNum, orderList[i]))
			{
				//不在内存中
				int index = GetLastIndexOrdList(MyMemory,orderList,i+1);
				MyMemory[index] = orderList[i];
				count++;
			}
		}
		//Print(MyMemory,memoryNum);
	}
	cout << "OPT算法的缺页率为：" << double(count) / 320 << endl;
}

 //产生随机数
int generateRandom(int begin, int end)
{
	//产生一个随机数，位于[begin,end]之间
	int ranNum = rand() % (end - begin + 1) + begin;
	return ranNum;
}

//产生随机数列表
void generateRandomList(int orderList[320])
{
	//①	在[0，319]之间随机选取一条起始执行指令，其序号为m；
	//②	顺序执行下一条指令，即序号为m + 1的指令；
	//③	通过随机数，跳转到前地址部分[0，m - 1]中的某条指令处，其序号为m1；
	//④	顺序执行下一条指令，即序号为m1 + 1的指令；
	//⑤	通过随机数，跳转到后地址部分[m1 + 2，319]中的某条指令处，其序号为m2；
	//⑥	顺序执行下一条指令，即序号为m2 + 1的指令；
	//⑦	重复跳转到前地址部分、顺序执行、跳转到后地址部分、顺序执行的过程，直至执行320条指令。
	srand((unsigned)time(NULL));
	orderList[0] = generateRandom(0, 319);
	orderList[1] = orderList[0] + 1;
	for (int i = 1; i < 320; )
	{
		i++;
		orderList[i] = generateRandom(0, orderList[i - 2] - 1);
		i++;
		orderList[i] = orderList[i - 1] + 1;
		i++;
		orderList[i] = generateRandom(orderList[i - 2] + 2, 319);
		i++;
		orderList[i] = orderList[i - 1] + 1;
	}

}


void printRandomList(int orderList[320])
{
	for (int i = 0; i < 320; i++)
	{
		cout << orderList[i] << " ";
		if ((i + 1) % 10 == 0) cout << endl;
	}
}

//指令序列转化为页面序列
void OrderList2PageList(int orderList[320])
{
	for (int i = 0; i < 320; i++)
	{
		orderList[i] = orderList[i] / 10;
	}
}

int main()
{
	//指令序列
	int orderList[320];
	generateRandomList(orderList);
	printRandomList(orderList);
	OrderList2PageList(orderList);
	cout << "==================" << endl;
	FIFO(orderList);
	cout << "==================" << endl;
	LRU(orderList);
	cout << "==================" << endl;
	OPT(orderList);
	_getch();
	return 0;
}

运行结果