欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LRU算法数组实现超简单

程序员文章站 2022-04-28 10:05:33
...

LRU算法

官方的解释有很多,用最通俗的话来说就是,如果你要去排队干活,每个队假如只能排十个人,每次来新人就让新人站在队伍最前面,如果队伍排满了,就要把最懒得不干活得人踢出去,显然现在队伍最后一个人就是最懒的很长时间没干活了,把他踢掉。然后在这十个人里,你要用到十个人中的一个来干活,就直接揪着他的耳朵到最前面去干活,剩下的人依次向后挪一个,如果现在来新人了,就让新人在最前面,最后一个人踢掉,就能完美的保证保留最“新鲜”的打工人了。

仔细体会一下上面的算法,然后再思考一下下面的算法。

计算机组成原理中,底层实现页面置换的LRU算法时,是给每个页面设置一个计数器,每次在内存中查找页面时,给所有的页面计数器都加1,如果访问的页面在内存中,就将这个页面的计数器置为0;如果访问的页面不在内存中,需要将该页面调入内存,这时,看哪个页面的计数器最大,将最大的页面置换掉。

是不是很神奇,还很简单,所以设计计算机的人都是神人呀!

实现

学习计算机组成原理和操作系统时,会发现有很多相通的知识点。这次操作系统实验,我们做了一个LRU算法的模拟,这里我用了一个非常简单易懂的数组实现方法。

在这之前有几个问题:

  • 页面为空和0号页面怎么区别?
  • 怎么判断哪个元素才是最新的被访问的,哪个元素是最老的?(计算机组成原理已经回答了)

以下是该算法的源代码,大家自己看看秒懂了,我就不说了:

#include <stdio.h>
//内存容量 :3个内存块
const int MemCapacity = 3;
//设置-1表示页面为空 与0号页 区分
int FIFOQueue[MemCapacity] = { -1,-1,-1 };
//标志符
int flagQueue[MemCapacity] = { 0 };
int pageInMainMem(int page)
{
	for (int i = 0; i < MemCapacity; i++) {
		//每访问一次就加一
		//如果找到就将该页计数器置0
		flagQueue[i]++;
		if (FIFOQueue[i] == page)
		{
			flagQueue[i] = 0;
			return i;
		}
	}
	return -1;
}

int foldPage(int page)
{
	int max = 0;
	int yehao = 0;
	for (int i = MemCapacity - 1; i >= 0; i--)
	{
		if ( flagQueue[i] > max) {
			max = flagQueue[i];
			yehao = i;
		}
	}
	
	int diaochu = FIFOQueue[yehao];

	FIFOQueue[yehao] = page;
	flagQueue[yehao] = 0;

	return diaochu;
}

int main()
{
	int pageFootprints[] = { 1,2,0,4,2,1,5,6,0,1,2,3,7,0,3,2,1,2,3,6 };
	//页面数
	int pageNum = sizeof pageFootprints / sizeof pageFootprints[0];


	int RequestCount = 0;
	bool request;

	printf("时刻   访问页面   主存状态   缺页中断   调入页   调出页\n");
	for (int i = 0; i < pageNum; i++) {
		printf("%3d      ", i);
		printf("    %2d    ", pageFootprints[i]);
		request = false;
		int diaochu = -1;
		//页面不在内存中
		if (pageInMainMem(pageFootprints[i]) == -1) {
			diaochu = foldPage(pageFootprints[i]);
			RequestCount++;
			request = true;
		}

		for (int j = 0; j < MemCapacity; j++)
			if (FIFOQueue[j] != -1)
				printf("%2d", FIFOQueue[j]);
			else
				printf("  ");

		if (request) {
			printf("           +   ");
			printf("     %d", pageFootprints[i]);
		}

		if (diaochu != -1) {
			printf("%9d      ", diaochu);
		}

		printf("\n");

	}

	printf("缺页中断次数 = %d\n", RequestCount);
	printf("缺页率 = %d/%d = %.2f%%\n", RequestCount, pageNum, (float)RequestCount / pageNum * 100);

	return 0;
}

运行结果:
LRU算法数组实现超简单