操作系统页面置换算法之最近最久未使用(LRU)页面置换算法

最近最久未使用(LRU)页面置换算法

【注】本代码数据及思路方法参考自《计算机操作系统（第四版）》汤小丹等 编著的教材。

#include <iostream>

int accessPage[20] = { 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 };
int flagLRU[3] = { -1, -1, -1 };					// 用来在LRU算法中标记三个物理块最近最久未使用的时间
int physicalBlock[3] = { -1,-1,-1 };			// 3个物理块，初始化物理块装入为空

// 最近最久未使用置换算法
bool LRU(int page)
{
	int i;								//标识物理块号
	for (i = 0; i < 3; i++)
	{
		
		if (flagLRU[i] == -1)			//判断该物理块是否为空物理块
			break;	//如果当前物理块为空物理块，则证明后面的物理块都为空物理块，需要装入页面。
		else
			flagLRU[i]++;		//该物理块不为空物理块，需将页面（物理块）未使用时间+1
		if (physicalBlock[i] == page)	// 判断页面是否在内存中
		{
			for (int j = i + 1; j < 3; j++)		// 将后面的有页面的物理块的未使用时间+1
			{
				if (flagFIFO[j] != -1)
					flagFIFO[j]++;
			}
			flagLRU[i] = 0;		// （该页面再次被访问）将未使用时间改为0
			return true;	//true 代表不换页
		}
	}
	if (i == 3)						//没有空物理块
	{
		int longestUnused = flagLRU[0];			//最久未使用时间
		int longestUnusedNum = 0;				//最久未使用页面的物理块编号
		for (int i = 0; i < 3; i++)						//找出最久未使用页面及其所占物理块的编号
		{
			if (flagLRU[i] > longestUnused)
			{
				longestUnused = flagLRU[i];
				longestUnusedNum = i;
			}
		}
		physicalBlock[longestUnusedNum] = page;
		flagLRU[longestUnusedNum] = 0;
		return false;
	}
	else								//有空物理快，空物理块号为i
	{
		physicalBlock[i] = page;		//第i个物理块中放入页面page
		flagLRU[i] = 0;							//修改页面的驻留时间
		return false;
	}
}
void LRUStart()
{
	int RN = 0;	//页面置换次数
	for (int i = 0; i < 20; i++)
	{
		bool b = LRU(accessPage[i]);
		printf("%d  ", b);
		if (b == false)		//页面发生了置换
		{
			RN++;
		}
	}
	printf("\n缺页次数：%d", RN);		// 结果包含了一开始物理块中没有页面是的三次缺页
	double d = (double)RN / 20 * 100;
	printf("\n缺页率：%.2f%%", d);
}

int main()
{
	LRUStart();
}