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;
}
运行结果: