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演算法：
一個演算法的基本原理和演算法的實際執行，在系統開發中會有一定折中，需綜合考慮所開發的系統，在資源和性能方面的要求，以避免嚴格按照演算法實現帶來的資源和性能開銷。