clru算法
A. 一个程序的页面走向，FIFO和LRU页面置换算法
#include"stdio.h"
#include"stdlib.h"
#include"time.h"
void FIFO(void);
void LRU(void);
char a;
int m=4,n=12,i,y[12]={1,2,3,4,1,2,5,1,2,3,4,5}; /*m为物理块数，n为要访问的页面数*/
typedef struct page{
int num;
int time;
}Page;
Page x[10];
int GetMax(page *x) /*求出那个物理块中的页面呆的时间最长，返回物理块号*/
{
int i;
int max=-1;
int tag=0;
for(i=0;i<m;i++)
{
if(x[i].time>max)
{ max=x[i].time;
tag=i;
}
}
return tag;
}
void Xunhuan()
{
printf("Please select 1:FIFO算法\n 2:LRU算法\n");
scanf("%s",&a);
printf("物理块数：4\n");
//scanf("%d",&m);
for(i=0;i<m;i++) /*将空的物理块中数据置为-1*/
{
x[i].num=-1;
}
printf("所要访问的页面数：12\n");
//scanf("%d",&n);
//srand(time(NULL));
printf("所要访问的页面号序列为：");
for(i=0;i<n;i++)
printf("%d ",y[i]);
printf("\n");
printf("页面置换步骤如下：\n");
switch(a)
{
case '1':FIFO();break;
case '2':LRU(); break;
}
}
void main()
{
char a;
Xunhuan();
while(1)
{
printf("Continue or Exit:C/Anykey:\n");
scanf("%s",&a);
if(a=='c'||a=='C')
Xunhuan();
else break;
}
exit(0);
}
void FIFO(void)
{
int i,j,u;
for(i=0;i<m;i++)
x[i].time=0;
x[0].num=y[0];
x[0].time=1;
printf(" %d \n",x[0].num);
for(i=1;i<n;i++)
{ u=0;
for(j=0;j<m;j++)
if(x[j].num==y[i])
{
u=1;
break;
}
if(u!=1&&x[m-1].num!=-1)
{
j=GetMax(x);
x[j].num=y[i];
x[j].time=0;
}
if(u!=1&&x[m-1].num==-1)
{
for(j=0;j<m;j++)
{
if(x[j].num==-1)
{x[j].num=y[i];
break;}
}
}
for(j=0;j<m;j++)
if(x[j].num!=-1)
x[j].time++;
for(j=0;j<m;j++)
if(x[j].num==-1)
printf("%2c ",32);
else
printf("%2d ",x[j].num);
printf("\n");
}
}
void LRU()
{
int i,j,u;
for(i=0;i<m;i++)
x[i].time=0;
x[0].num=y[0];
x[0].time=1;
printf(" %d \n",x[0].num);
for(i=1;i<n;i++)
{ u=0;
for(j=0;j<m;j++)
if(x[j].num==y[i]) /*物理块中存在相同页面*/
{
x[j].time=0; /*将相同的物理块的time置为0*/
u=1;
break;
}
if(u!=1&&x[m-1].num!=-1) /*物理块中无相同页面且物理块已填满*/
{
j=GetMax(x);
x[j].num=y[i];
x[j].time=0; /*将刚替换的页面所在的物理块time置为0*/
}
if(u!=1&&x[m-1].num==-1) /*物理块中无相同页面且物理块未填满*/
{
for(j=0;j<m;j++)
{
if(x[j].num==-1)
{x[j].num=y[i];
break;}
}
}
for(j=0;j<m;j++)
if(x[j].num!=-1)
x[j].time++; /*每执行完一次time加1*/
for(j=0;j<m;j++)
if(x[j].num==-1)
printf("%2c ",32);
else
printf("%2d ",x[j].num);
printf("\n"); /*格式化输出*/
}
}
B. Cache 的替换算法中，（ ）算法计数器位数多，实现困难。
【答案】：C
最常用的Cache 的替换算法有三种：（1）随机算法。这是最简单的替换算法。随机法完全竖隐不管cache块过去、现在及将来的使用情况，简单地根据一个随机数，选择一块替换掉。（2）先进先出（First In and First Out，FIFO）算法。按调入cache的先后决定淘汰的顺序，即在需要更新时，将最先进入cache的块作为被替换的块。这种方法要求为每块做一记录，记下它们进入cache的先后次序。这种方法容易实现，而且系统开销小。其缺点是可能会把一些需要经常使用的程序块（如循环程序）替庆兆换掉。（3）近期最少使用（Least Recently Used，LRU）算法。LRU算法是把CPU近期最少使用的块作为被替换的块。这种替换方法需要随时记录cache中各块的使用情况，以便确定哪个块是近期最少使用的块。LRU算法相对合理，但实现起来比较复杂，系统开销较大。通常需余差厅要对每一块设置一个称为"年龄计数器"的硬件或软件计数器，用以记录其被使用的情况。
C. 怎么样实现分页管理的缺页调度clock算法C语言代码
这个程序我做过,现在给你!!写了很久的!!
#include<stdafx.h>
#include<stdlib.h>
#include<stdio.h>
#define n 64//实验中假定主存的长度
#define m 4//实验中假定每个作业分得主存块块数
int p[m];//定义页
int head=0;
struct
{
short int lnumber;//页号
short int flag;//表示该页是否在主存，"1"表示在主存，"0"表示不在主存
short int pnumber;//该页所在主存块的块号
short int write;//该页是否被修改过，"1"表示修改过，"0"表示没有修改过
short int dnumber;//该页存放在磁盘上的位置，即磁盘块号
short int times;//被访问的次数，用于LRU算法
}page[n];//定义页表
//各个函数的实现如下：
void computer()
{
int i;
for(i=0;i<n;i++)
{
page[i].lnumber = i;
page[i].flag = 0;
page[i].pnumber = 10000;//用10000表示为空
page[i].write = 0;
page[i].dnumber = i;
page[i].times = 0;
}//初始化页表
for(i=0;i<m;i++)
{
page[i].pnumber = i;
}
for(i=0;i<m;i++)
{
p[i] = i;
page[i].flag = 1;
}//初始化页
}
void showpagelist()
{
int i;
printf("\n页号\t是否在主存中\t块 号\t是否被修改过\t磁盘块号\t访问次数\n");
for(i=0;i<n;i++)
{
printf("%d\t%d\t\t%d\t\t%d\t\t%d\t\t%d\n",page[i].lnumber,page[i].flag,page[i].pnumber,page[i].write,page[i].dnumber,page[i].times);
}
}
void showpage()
{
int i;
for(i=0;i<m;i++)
{
printf("\t%d\n",p[i]);
}
}
void transformation() //缺页中断处理
{
unsigned logicAddress,logicNumber,innerAddress,physicsAddress,physicsNumber;
int i, fail = 0;
int method,temppage=0;
short int times = 10000;
printf("请输入一个逻辑地址（四位十六进制数）:");
scanf("%x",&logicAddress);//读入逻辑地址
logicNumber = logicAddress >> 10;//得到页号
printf("页号为:%ld\n",logicNumber);
innerAddress = logicAddress & 0x03ff;//得到页内地址
printf("页内地址为:%ld\n",innerAddress);
for(i=0;i<n;i++)
{
if(logicNumber==(unsigned)page[i].lnumber)
{
if(page[i].flag == 1)
{
printf("请求的页面在主存中!\n");
page[i].times++;
physicsNumber = page[i].pnumber;//由页号得到块号
printf("请求的主存块号为:%ld\n",physicsNumber);
physicsAddress = physicsNumber << 10 |innerAddress;//得到物理地址
printf("请求的物理地址为:%ld",physicsAddress);//输出物理地址
break;
}
else
{
printf("请求的页面不在主存中! 将进行缺页中断处理!\n请选择算法!\n");
printf("1.先进先出\n2.最近最少用\n请选择置换算法:");
scanf("%d",&method);
if(method == 1) //采用先进先出算法
{
printf("采用先进先出算法!\n");
fail = p[head];
printf("第%d页将被替换!\n",fail);
p[head] = logicNumber;
head = (head+1) % m;
if(page[fail].write == 1)
printf("第%d页曾被修改过!\n",fail);
page[fail].flag = 0;
page[logicNumber].flag = 1;
page[logicNumber].write = 0;
page[logicNumber].pnumber = page[fail].pnumber;
page[fail].pnumber = 10000;
page[logicNumber].times++;
break;
}
else if(method == 2) //采用最近最少用算法
{
printf("采用最近最少用算法!\n");
for(i=0;i<n;i++)
{
if(page[i].flag == 1)
{
if(page[i].times<times)
{
times = page[i].times;
temppage = page[i].lnumber;
}
}
}
printf("第%d页将被替换!\n",temppage);
for(i=0;i<m;i++)
{
if(p[i] == temppage)
{
p[i] = logicNumber;
}
}
if(page[temppage].write == 1)
printf("第%d页曾被修改过!\n",temppage);
page[temppage].flag = 0;
page[logicNumber].flag = 1;
page[logicNumber].write = 0;
page[logicNumber].pnumber = page[temppage].pnumber;
page[temppage].pnumber = 10000;
page[logicNumber].times++;
break;
}
else
{
printf("你输入有误，即将退出!");
exit(1);
}
}
}
}
}
void main()
{
char c,d,flag='y';
printf("页表正在初始化中...，3秒钟后为你显示页和页表！\n");
computer();
showpage();
showpagelist();
while(flag == 'y' || flag == 'Y')
{
transformation();
printf("是否显示页和页表？(Y/N)");
c = getchar();
c = getchar();
if(c=='Y'||c=='y')
{
showpage();
showpagelist();
}
else
{
while(c=='N'||c=='n')
{
printf("\n是否继续进行请求分页？（Y/N）");
d = getchar();
d = getchar();
if(d=='Y'||d=='y')
{
transformation();
printf("\n是否显示页和页表？（Y/N）");
c = getchar();
c = getchar();
if(c=='Y'||c=='y')
{
showpage();
showpagelist();
}
}
else if (d=='N'||d=='n')
exit(1);
else
printf("输入错误！\n");
}
}
printf("\n是否继续进行请求分页？（Y/N）");
flag = getchar();
flag = getchar();
}
}
D. C语言用以下函数构造LRU算法，求大侠帮助
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAINMEM 3 //主存可存储的页面个数
#define QUEUEMAXLEN 30 //队列最大长度
struct LRUQueue //定义一个特殊的队列
{
int number;
int data[MAINMEM];
}lru;
void Init(); //初始化操作
void Add(int pageID); //加入队列
int Find(int pageID); //查找页面是否在主存中
void Update(int pos); //更新页所在的地址
void PrintQueue(); //输出主存内容
int main()
{
int i;
int queuelength;
int queue[QUEUEMAXLEN];
Init(); //初始雹握化操作
printf("请输入队列的长度：");
scanf("%d",&queuelength);
printf("请以此输入队列的页号：");
for(i=0;i<queuelength;i++)
{
scanf("誉肆首%d",&queue[i]);
Add(queue[i]);
PrintQueue();
}
system("pause");
return 0;
}
void Init()
{
lru.number = 0;
int i;
for(i = 0;i<MAINMEM;i++)
{
lru.data[i] = -1;
}
}
int Find(int pageID)
{
int i;
for (i=0;i<MAINMEM;i++)
{
if(lru.data[i] == pageID)
{
return i;
}
}
return 0;
}
void Update(int pos)
{
int tmp = lru.data[pos];
int i;
for(i = pos;i<lru.number;++i)
{
lru.data[i] = lru.data[i+1];
}
lru.data[lru.number-1] = tmp; //将被访问的页放在最后一位，其他的页前移，因为置换时删掉的是主存中第一块放置的页面
}
void PrintQueue()
{
printf("当前内存中的页号:\n");
int i;
putch('|');
for(i = 0;i<MAINMEM;i++)
{
if(lru.data[i] == -1)
printf(" |");
else
printf("%d |",lru.data[i]);
}
putch('\n');
}
void Add(int pageID)
{
printf("当前访问的页面：%d\n",pageID);
if(lru.number<MAINMEM) //如庆数果主存没有填满
{
int pos = Find(pageID);
if(pos)
{
Update(pos);
}
else
{
lru.data[lru.number++]=pageID;
}
}
else
{
int pos = Find(pageID);
if(pos)
{
Update(pos);
}
else
{
int i;
for(i=0;i<MAINMEM-1;i++)
{
lru.data[i]=lru.data[i+1]; //数据左移一个单位
}
lru.data[i]=pageID; //加入新数据
}
}
}
E. C语言模拟FIFO算法，随机生成320条指令，有四块物理块，为什么错了
这可是hen宝贵的啊
#include
#include
#include
#include
#define Bsize 4
typedef struct BLOCK//声明一种新类型——物理块类型
{
int pagenum;//页号
int accessed;//访问字段，其值表示多久未被访问
}BLOCK;
int pc;//程序计数器，用来记录指令的序号
int n;//缺页计数器，用来记录缺页的次数
static int temp[320];//用来存储320条随机数
BLOCK block[Bsize]; //定义一大小为4的物理块数组
//*************************************************************
void init( ); //程序初始化函数
int findExist(int curpage);//查找物理块中是否有该页面
int findSpace( );//查找是否有空闲物理块
int findReplace( );//查找应予置换的页面
void display ( );//显示
void suijishu( );//产生320条随机数,显示并存储到temp[320]
void pagestring( );//显示调用的页面队列
void OPT( );//OPT算法
void LRU( );// LRU算法
void FIFO( );//FIFO算法
//*************************************************************
void init( )
{
for(int i=0;i<Bsize;i++)
{
block[i].pagenum=-1;
block[i].accessed=0;
pc=n=0;
}
}
//-------------------------------------------------------------
int findExist(int curpage)
{
for(int i=0; i<Bsize; i++)
{
if(block[i].pagenum == curpage )
return i;//检测到内存中有该页面，返回block中的位置
}
return -1;
}
//-------------------------------------------------------------
int findSpace( )
{
for(int i=0; i<Bsize; i++)
{
if(block[i].pagenum == -1)
return i;//找到空闲的block，返回block中的位置
}
return -1;
}
//-------------------------------------------------------------
int findReplace( )
{
int pos = 0;
for(int i=0; i<Bsize; i++)
{
if(block[i].accessed >block[pos].accessed)
pos = i;//找到应予置换页面，返回BLOCK中位置
}
return pos;
}
//-------------------------------------------------------------
void display( )
{
for(int i=0; i<Bsize; i++)
{
if(block[i].pagenum != -1)
{ printf(" %02d",block[i].pagenum);}
}
cout<<endl;
}
//-------------------------------------------------------------
void suijishu( )
{ int flag=0;
cin>>pc;
cout<<"******按照要求产生的320个随机数：*******"<<endl;
for(int i=0;i<320;i++)
{
temp[i]=pc;
if(flag%2==0) pc=++pc%320;
if(flag==1) pc=rand( )% (pc-1);
if(flag==3) pc=pc+1+(rand( )%(320-(pc+1)));
flag=++flag%4;
printf(" %03d",temp[i]);
if((i+1)%10==0) cout<<endl;
}
}
//-------------------------------------------------------------
void pagestring( )
{
for(int i=0;i<320;i++)
{
printf(" %02d",temp[i]/10);
if((i+1)%10==0) cout<<endl;
}
}
//-------------------------------------------------------------
void OPT( )
{
int exist,space,position ;
int curpage;
for(int i=0;i<320;i++)
{
if(i%100==0) getch( );
pc=temp[i];
curpage=pc/10;
exist = findExist(curpage);
if(exist==-1)
{
space = findSpace ( );
if(space != -1)
{
block[space].pagenum = curpage;
display( );
n=n+1;
}
else
{
for(int k=0;k<Bsize;k++)
{
for(int j=i;j<320;j++)
{
if(block[k].pagenum!= temp[j]/10)
{
block[k].accessed = 1000;
}//将来不会用，设置为一个很大数
else
{
block[k].accessed = j;
break;
}
}
}
position = findReplace( );
block[position].pagenum = curpage;
display( );
n++;
}
}
}
cout<<"缺页次数:"<<n<<endl;
cout<<"缺页率:"<<(n/320.0)*100<<"%"<<endl;
}
//-------------------------------------------------------------
void LRU( )
{
int exist,space,position ;
int curpage;
for(int i=0;i<320;i++)
{
if(i%100==0) getch( );
pc=temp[i];
curpage=pc/10;
exist = findExist(curpage);
if(exist==-1)
{
space = findSpace( );
if(space != -1)
{
block[space].pagenum = curpage;
display( );
n=n+1;
}
else
{
position = findReplace( );
block[position].pagenum = curpage;
display( );
n++;
}
}
else block[exist].accessed = -1;//恢复存在的并刚访问过的BLOCK中页面accessed为-1
for(int j=0; j<4; j++)
{block[j].accessed++;}
}
cout<<"缺页次数:"<<n<<endl;
cout<<"缺页率:"<<(n/320.0)*100<<"%"<<endl;
}
//-------------------------------------------------------------
void FIFO( )
{
int exist,space,position ;
int curpage;
for(int i=0;i<320;i++)
{
if(i%100==0) getch( );
pc=temp[i];
curpage=pc/10;
exist = findExist(curpage);
if(exist==-1)
{
space = findSpace( );
if(space != -1)
{
block[space].pagenum = curpage;
display( );
n=n+1;
}
else
{
position = findReplace( );
block[position].pagenum = curpage;
display( );
n++;
block[position].accessed--;
}
}
for(int j=0; j<Bsize; j++)
block[j].accessed++;
}
cout<<"缺页次数:"<<n<<endl;
cout<<"缺页率:"<<(n/320.0)*100<<"%"<<endl;
}
//*************************************************************
void main( )
{
int select;
cout<<"请输入第一条指令号(0~320)：";
suijishu( );
cout<<"*****对应的调用页面队列*******"<<endl;
pagestring( );
do
{
cout<<"****************************************"<<endl;
cout<<"------1:OPT 2:LRU 3:FIFO 4:退出-----"<<endl;
cout<<"****************************************"<<endl;
cout<<" 请选择一种页面置换算法:";
cin>>select;
cout<<"****************************************"<<endl;
init( );
switch(select)
{
case 1:cout<<"最佳置换算法OPT:"<<endl;
cout<<"*****************"<<endl;
OPT( );
break;
case 2:cout<<"最近最久未使用置换算法LRU:"<<endl;
cout<<"**************************"<<endl;
LRU( );
break;
case 3:cout<<"先进先出置换算法FIFO:"<<endl;
cout<<"*********************"<<endl;
FIFO( );
break;
default: ;
}
}while(select!=4);
}
你试试可以不，应该没问题的
要注意这是用C++编写的，你改一下就可以用了
F. 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算法：
一个算法的基本原理和算法的实际执行，在系统开发中会有一定折中，需综合考虑所开发的系统，在资源和性能方面的要求，以避免严格按照算法实现带来的资源和性能开销。