lru算法代码

⑴ lru算法是什么

lru算法是一种页面置换算法，在对于内存中但是又不用的数据块，叫做LRU，操作系统会根据那些数据属于LRU而将其移出内存而腾出空间来加载另外的数据。

LRU算法：最近最少使用，简单来说就是将数据块中，每次使用过的数据放在数据块的最前端，然后将存在的时间最长的，也就是数据块的末端的数据剔除掉这就是LRU算法。

如果进程被调度，该进程需要使用的外存页（数据）不存在于数据块中，这个现象就叫做缺页。如果这个数据此时不在，就会将这个数据从加入到数据块首部。

数据块插入与剔除：每次有新数据到来时，会将其放入数据块首部，当数据每次被访问时，岩键肢将这个数据插入数据块的首部如果数据块满了，每次新进的数据都会将数据块尾部的数据挤出数据块。

差距

为了尽量减少与理想算法的差距，产生了各种精妙的算法，最少使用页面置换算法便是其中一个。LRU算法的提出，是基于这样一个事实：在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。

反过来说，已经亮铅很久没有使用的页面很可能在未来较长的一段时间内不会被用到。这个，就是着名的局部性原理——比内存速度还要快的cache，也是基于同样的原理运行的。因此，我们只需要在每次调换时，找到最少使用的那个页面调出内存。这就是LRU算法的全部内容。

LRU在电子系统中的解释：

Line Replaceable Unit—LRU，电子系统中常采用模块化设计，这种可更换的模块单元则被叫做LRU，中文名称是“线性可粗世更换单元”。

⑵ 用C++语言编写FIFO页面置换算法代码

分别使用FIFO、OPT、LRU三种置换算法来模拟页面置换的过程。（Linux、Windows下皆可）
输入：3//页帧数
70120304230321201701//待处理的页
输出：页面置换过程中各帧的变化过程和出现页错误的次数
[cpp]
#include<iostream>
usingnamespacestd;
intinput[20]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
classpage
{
public:
intnum;
intmark;
page()
{
num=0;
mark=21;
}
};
voidFIFO()
{
cout<<"------FIFO-----------"<<endl;
interror=0;
pageframe[3];//页帧
for(inti=0;i<3;i++)//处理前三个引用
{
frame[i].num=input[i];
error++;
cout<<frame[i].num<<"|";
for(intj=0;j<=i;j++)
cout<<frame[j].num<<'';
cout<<endl;
}
for(inti=3;i<20;i++)
{
intj;
for(j=0;j<3;j++)
if(input[i]==frame[j].num)
{
cout<<input[i]<<endl;
break;
}
if(j==3)
{
error++;
frame[((error-1)%3)].num=input[i];//换掉最旧的页
cout<<input[i]<<"|";
for(intk=0;k<3;k++)
cout<<frame[k].num<<'';
cout<<endl;
}
}
cout<<"FrameError:"<<error<<endl<<endl;
}
voidOPT()
{
cout<<"------OPT------------"<<endl;
interror=0;
pageframe[3];
for(inti=0;i<3;i++)//处理前三个引用
{
frame[i].num=input[i];
error++;
cout<<frame[i].num<<"|";
for(intj=0;j<=i;j++)
cout<<frame[j].num<<'';
cout<<endl;
}
for(inti=3;i<20;i++)
{
intj;
for(j=0;j<3;j++)
if(input[i]==frame[j].num)
{
cout<<input[i]<<endl;
break;
}
if(j==3)
{
error++;
for(j=0;j<3;j++)
{
frame[j].mark=21;
for(intk=20;k>=i;k--)//向后遍历，找到最长时间不用的页
{
if(frame[j].num==input[k])
frame[j].mark=k;
}
}
if(frame[0].mark>frame[1].mark&&frame[0].mark>frame[2].mark)
frame[0].num=input[i];
elseif(frame[1].mark>frame[0].mark&&frame[1].mark>frame[2].mark)
frame[1].num=input[i];
else
frame[2].num=input[i];
cout<<input[i]<<"|";
for(intk=0;k<3;k++)
cout<<frame[k].num<<'';
cout<<endl;
}
}
cout<<"FrameError:"<<error<<endl<<endl;
}
voidLRU()
{
cout<<"------LRU------------"<<endl;
interror=0;
pageframe[3];
for(inti=0;i<3;i++)//处理前三个引用
{
frame[i].num=input[i];
error++;
cout<<frame[i].num<<"|";
for(intj=0;j<=i;j++)
cout<<frame[j].num<<'';
cout<<endl;
}
for(inti=3;i<20;i++)
{
intj;
for(j=0;j<3;j++)
if(input[i]==frame[j].num)
{
cout<<input[i]<<endl;
break;
}
if(j==3)
{
error++;
for(j=0;j<3;j++)
{
frame[j].mark=0;
for(intk=0;k<=i;k++)//向前遍历，找到最近最少使用的
{
if(frame[j].num==input[k])
frame[j].mark=k;
}
}
if(frame[0].mark<frame[1].mark&&frame[0].mark<frame[2].mark)
frame[0].num=input[i];
elseif(frame[1].mark<frame[0].mark&&frame[1].mark<frame[2].mark)
frame[1].num=input[i];
else
frame[2].num=input[i];
cout<<input[i]<<"|";
for(intk=0;k<3;k++)
cout<<frame[k].num<<'';
cout<<endl;
}
}
cout<<"FrameError:"<<error<<endl<<endl;
}
intmain()
{
FIFO();
OPT();
LRU();
}

⑶ Redis的LRU缓存淘汰算法实现

LRU， 最近最少使用 （Least Recently Used，LRU），经典缓存算法。

LRU会使用一个链表维护缓存中每个数据的访问情况，并根据数据的实时访问，调整数据在链表中的位置，然后通过数据在链表中的位置，表示数据是最近刚访问的，还是已有段时间未访问。

LRU会把链头、尾分别设为MRU端和LRU端：

LRU可分成如下情况：

case2图解：链表长度为5，从链表头部到尾部保存的数据分别是5，33，9，10，8。假设数据9被访问一次，则9就会被移动到链表头部，同时，数据5和33都要向链表尾部移动一位。

所以若严格按LRU实现，假设Redis保存的数据较多，还要在代码中实现：

最终导致降低Redis访问性能。

所以，无论是为节省内存 or 保持Redis高性能，Redis并未严格按LRU基本原理实现，而是 提供了一个近似LRU算法实现 。

Redis的内存淘汰机制是如何启用近似LRU算法的？redis.conf中的如下配置参数：

所以，一旦设定maxmemory选项，且将maxmemory-policy配为allkeys-lru或volatile-lru，近似LRU就被启用。allkeys-lru和volatile-lru都会使用近似LRU淘汰数据，区别在于：

Redis如何实现近似LRU算法的呢？

近似LRU算法仍需区分不同数据的访问时效性，即Redis需知道数据的最近一次访问时间。因此，有了LRU时钟：记录数据每次访问的时间戳。

Redis对每个KV对中的V，会使用个redisObject结构体保存指向V的指针。那redisObject除记录值的指针，还会使用24 bits保存LRU时钟信息，对应的是lru成员变量。这样，每个KV对都会把它最近一次被访问的时间戳，记录在lru变量。

redisObject定义包含lru成员变量的定义：

每个KV对的LRU时钟值是如何计算的？Redis Server使用一个实例级别的全局LRU时钟，每个KV对的LRU time会根据全局LRU时钟进行设置。

这全局LRU时钟保存在Redis全局变量server的成员变量 lruclock

当Redis Server启动后，调用initServerConfig初始化各项参数时，会调用getLRUClock设置lruclock的值：

于是，就得注意， 若一个数据前后两次访问的时间间隔 1s，那这两次访问的时间戳就是一样的！ 因为LRU时钟精度就是1s，它无法区分间隔小于1秒的不同时间戳！

getLRUClock函数将获得的UNIX时间戳，除以LRU_CLOCK_RESOLUTION后，就得到了以LRU时钟精度来计算的UNIX时间戳，也就是当前的LRU时钟值。

getLRUClock会把LRU时钟值和宏定义LRU_CLOCK_MAX（LRU时钟能表示的最大值）做与运算。

所以默认情况下，全局LRU时钟值是以1s为精度计算得UNIX时间戳，且是在initServerConfig中进行的初始化。

那Redis Server运行过程中，全局LRU时钟值是如何更新的？和Redis Server在事件驱动框架中，定期运行的时间事件所对应的serverCron有关。

serverCron作为时间事件的回调函数，本身会周期性执行，其频率值由redis.conf的 hz配置项 决定，默认值10，即serverCron函数会每100ms（1s/10 = 100ms）运行一次。serverCron中，全局LRU时钟值就会按该函数执行频率，定期调用getLRUClock进行更新：

这样，每个KV对就能从全局LRU时钟获取最新访问时间戳。

对于每个KV对，它对应的redisObject.lru在哪些函数进行初始化和更新的呢？

对于一个KV对，其LRU时钟值最初是在这KV对被创建时，进行初始化设置的，这初始化操作在 createObject函数 中调用，当Redis要创建一个KV对，就会调用该函数。

createObject除了会给redisObject分配内存空间，还会根据maxmemory_policy配置，初始化设置redisObject.lru。

LRU_CLOCK返回当前全局LRU时钟值。因为一个KV对一旦被创建，就相当于有了次访问，其对应LRU时钟值就表示了它的访问时间戳：

那一个KV对的LRU时钟值又是何时再被更新？

只要一个KV对被访问，其LRU时钟值就会被更新！而当一个KV对被访问时，访问操作最终都会调用 lookupKey 。

lookupKey会从全局哈希表中查找要访问的KV对。若该KV对存在，则lookupKey会根据maxmemory_policy的配置值，来更新键值对的LRU时钟值，也就是它的访问时间戳。

而当maxmemory_policy没有配置为LFU策略时，lookupKey函数就会调用LRU_CLOCK函数，来获取当前的全局LRU时钟值，并将其赋值给键值对的redisObject结构体中的lru变量

这样，每个KV对一旦被访问，就能获得最新的访问时间戳。但你可能好奇：这些访问时间戳最终是如何被用于近似LRU算法进行数据淘汰的？

Redis之所以实现近似LRU，是为减少内存资源和操作时间上的开销。

近似LRU主要逻辑在performEvictions。

performEvictions被evictionTimeProc调用，而evictionTimeProc函数又是被processCommand调用。

processCommand，Redis处理每个命令时都会调用：

然后，isSafeToPerformEvictions还会再次根据如下条件判断是否继续执行performEvictions：

一旦performEvictions被调用，且maxmemory-policy被设置为allkeys-lru或volatile-lru，近似LRU就被触发执行了。

执行可分成如下步骤：

调用getMaxmemoryState评估当前内存使用情况，判断当前Redis Server使用内存容量是否超过maxmemory配置值。

若未超过maxmemory ，则返回C_OK，performEvictions也会直接返回。

getMaxmemoryState评估当前内存使用情况的时候，若发现已用内存超出maxmemory，会计算需释放的内存量。这个释放内存大小=已使用内存量-maxmemory。

但已使用内存量并不包括用于主从复制的复制缓冲区大小，这是getMaxmemoryState通过调用freeMemoryGetNotCountedMemory计算的。

而若当前Server使用的内存量超出maxmemory上限 ，则performEvictions会执行while循环淘汰数据释放内存。

为淘汰数据，Redis定义数组EvictionPoolLRU，保存待淘汰的候选KV对，元素类型是evictionPoolEntry结构体，保存了待淘汰KV对的空闲时间idle、对应K等信息：

这样，Redis Server在执行initSever进行初始化时，会调用evictionPoolAlloc为EvictionPoolLRU数组分配内存空间，该数组大小由EVPOOL_SIZE决定，默认可保存16个待淘汰的候选KV对。

performEvictions在淘汰数据的循环流程中，就会更新这个待淘汰的候选KV对集合，即EvictionPoolLRU数组。

performEvictions调用evictionPoolPopulate，其会先调用dictGetSomeKeys，从待采样哈希表随机获取一定数量K：

于是，dictGetSomeKeys返回采样的KV对集合。evictionPoolPopulate根据实际采样到的KV对数量count，执行循环：调用estimateObjectIdleTime计算在采样集合中的每一个KV对的空闲时间：

接着，evictionPoolPopulate遍历待淘汰的候选KV对集合，即EvictionPoolLRU数组，尝试把采样的每个KV对插入EvictionPoolLRU数组，取决于如下条件之一：

有一成立，evictionPoolPopulate就能把采样KV对插入EvictionPoolLRU数组。等所有采样键值对都处理完后，evictionPoolPopulate函数就完成对待淘汰候选键值对集合的更新了。

接下来，performEvictions开始选择最终被淘汰的KV对。

因evictionPoolPopulate已更新EvictionPoolLRU数组，且该数组里的K，是按空闲时间从小到大排好序了。所以，performEvictions遍历一次EvictionPoolLRU数组，从数组的最后一个K开始选择，若选到的K非空，就把它作为最终淘汰的K。

该过程执行逻辑：

一旦选到被淘汰的K，performEvictions就会根据Redis server的惰性删除配置，执行同步删除或异步删除：

至此，performEvictions就淘汰了一个K。若此时释放的内存空间还不够，即没有达到待释放空间，则performEvictions还会 重复执行 前面所说的更新待淘汰候选KV对集合、选择最终淘汰K的过程，直到满足待释放空间的大小要求。

performEvictions流程：

近似LRU算法并未使用耗时且耗空间的链表，而使用 固定大小的待淘汰数据集合 ，每次随机选择一些K加入待淘汰数据集合。

最后，按待淘汰集合中K的空闲时间长度，删除空闲时间最长的K。

根据LRU算法的基本原理，发现若严格按基本原理实现LRU算法，则开发的系统就需要额外内存空间保存LRU链表，系统运行时也会受到LRU链表操作的开销影响。

而Redis的内存资源和性能都很重要，所以Redis实现近似LRU算法：

一个算法的基本原理和算法的实际执行，在系统开发中会有一定折中，需综合考虑所开发的系统，在资源和性能方面的要求，以避免严格按照算法实现带来的资源和性能开销。

⑷ lru算法是什么

LRU是Least Recently Used的缩写，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。

该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最少使用的页面予以淘汰。

特点：

LRU 算法弊端是存在偶发性、周期性的批量操会降低缓存的命中率，对缓存造成污染，下面几个就是改进算法。

LRU-K会记录每条数据的访问历史，当达到 k 时，才将数据存放到缓存，在缓存内存回收时，缓存中越接近 k 的数据被优先删除。

Two queues（2Q）相当于 LRU-2，区别是访问历史（首次访问）数据缓存于 FIFO 队列，二次及以上的数据存放LRU缓存，FIFO 队列数据遵循该缓存的内存回收机制，LRU缓存数据遵循该缓存的内存回收机制。