lru演算法

1. lru 淘汰演算法

最佳演算法（OPT演算法）

當需要淘汰一個內存頁面時，這種演算法力圖選擇該進程內存各個頁面中永遠不再需要的頁，若找不到，則選擇最久以後才會用到的頁。這種演算法有最小的缺頁率。問題是它需要知道運行進程今後的整個訪問蹤跡，這往往難以做到，因而它只有理論上的意義。

先進先出演算法（FIFO演算法）

FIFO演算法維護一個先進先出隊列，隊列長度為分配給這個進程的頁面數M。開始時隊列是空的，裝入進程的第一頁即可啟動運行，當訪問到某個不在內存的頁面時，把它從輔存調入，加入FIFO隊列的尾部。

最久未使用淘汰演算法（LRU演算法）

LRU（least recently used）演算法維護一個後進先出棧，棧大小為分配給這個進程的頁面數M。開始時棧是空的，裝入進程的第一頁即可啟動運行，當訪問到某個不在內存的頁面時，把它從輔存調入，加入棧頂。

FIFO和LRU演算法的例子：http://osjx.8100988.net/LWR/RAM/HLM/FIFOsf.HTM

CLOCK演算法

又叫NRU（Not Recently Used）演算法，NRU又名近似的LRU置換演算法。
當一存儲塊中的頁面訪問時，其相應的「頁面訪問」位由硬體自動置「1」，而由頁面管理體制軟體周期性地（設周期為T，其值通常為幾百毫秒），把所有的頁面訪問位重新置為「0」。這樣，在時間T內，某些被訪問的頁面，其對應的訪問位為「1」而未訪問的頁面，其對應的訪問位為「0」。查尋頁面訪問位為「0」的頁面。在查找過程中，那些被訪問的頁所對應的訪問位被重新置為「0」。由此可見，實際上這種近似LRU演算法，已經退化成一種「最近不用」的演算法NRU（Not Recently Used）。

CLOCK演算法的例子：http://www.cskaoyan.com/thread-4898-1-1.html

其實這個問題我也不太會，去臨時查的資料，第一個例子是我自己算的，不知道我理解得對不對；如果有錯誤的地方還請指正，共同進步~其他的演算法的例子我都給了鏈接，你自己去看吧。

2. C++實現LRU演算法

#include<iostream>
using namespace std;
int size;
int *w;

//定義一個動態數組
struct mem
{
int num;
int count;
}memBlock[3]={0,0,0,0,0,0};

void LRU()
{
for( int i = 0; i < size; i++ )
{
int maxCount = memBlock[0].count;
int maxPos = 0;

int j = 0;
bool bFind = false;
for( j = 0; j < 3; j++ )
{
// 標記出count值最大的位置
if( maxCount < memBlock[j].count )
{
maxCount = memBlock[j].count;
maxPos = j;
}

// 將所有的count值都+1
memBlock[j].count++;

// 如果命中，將其count值置為0
if( w[i] == memBlock[j].num )
{
memBlock[j].count = 0;
bFind = true;
}
}

// 未命中，將count最大的拿來替換
if( !bFind )
{
memBlock[maxPos].num = w[i];
memBlock[maxPos].count = 0;
}

for(j = 0; j < 3; j++) //輸出
cout << memBlock[j].num << " ";
cout <<" "<< endl;
}
}

int main() //主函數
{
cout<<"請輸入需訪問的頁面數量:"<<endl;
cin>>size;
w = new int[size];
cout<<"請輸入需要訪問的頁面"<<endl;
for(int a=0;a<size;a++)
{
cin>>w[a];//輸入數組
}
cout<<endl<<"(LRU)"<<endl;
LRU();
return 0;
}
引用 ： 回答者： floxer | 三級

3. LRu演算法具體步驟

內存已有頁面 需要頁面 操作 內存結果頁面 頁面是否失效
1 加入內存 1 否
8 加入內存 18 否
1 18 否
7 加入內存 718 否
8 871 否
2 加入內存 2871 否
7 7281 否
2 2781 否
1 1278 否
8 8127 否
3 換出7 3812 是
8 8312 否
2 2831 否
1 1283 否
3 3128 否
1 1328 否
7 換出8 7132 是
1 1732 否
3 3172 否
7 7312 否

頁面失效2次。

4. lru 演算法一題

物理頁面就是一次能存放的最多頁面數，LRU演算法是淘汰最久未使用的頁面。給你具體的計算過程吧：
順序：1 2 3 4 5 6 7 8 9 10 11 12
頁面：3 5 2 3 4 7 4 9 1 3 8 3
M（5):3 5 2 3 4 7 4 9 1 3 8 3
3 5 2 3 4 7 4 9 1 3 8
3 5 2 3 3 7 4 9 1 1
5 2 2 3 7 4 9 9
5 5 2 3 7 4 4
F： + + + + + + + +
缺頁數：8（F為+代表缺頁）缺頁率：8/12

5. 什麼是lru置換演算法

LRU是Least Recently Used的縮寫，即最近最少使用頁面置換演算法，是為虛擬頁式存儲管理服務的。
LRU演算法的提出，是基於這樣一個事實：在前面幾條指令中使用頻繁的頁面很可能在後面的幾條指令中頻繁使用。反過來說，已經很久沒有使用的頁面很可能在未來較長的一段時間內不會被用到。這個，就是著名的局部性原理——比內存速度還要快的cache，也是基於同樣的原理運行的。因此，我們只需要在每次調換時，找到最近最少使用的那個頁面調出內存。這就是LRU演算法的全部內容。
這是一個相當好的演算法，它是理想演算法很好的近似。

6. lru頁面置換演算法是什麼

用雙向鏈表和哈希表來實現。

LRU演算法的提出，是基於這樣一個事實：在前面幾條指令中使用頻繁的頁面很可能在後面的幾條指令中頻繁使用。

反過來說，已經很久沒有使用的頁面很可能在未來較長的一段時間內不會被用到。這個，就是著名的局部性原理——比內存速度還要快的cache，也是基於同樣的原理運行的。因此，只需要在每次調換時，找到最近最少使用的那個頁面調出內存。這就是LRU演算法的全部內容。

一種LRU近似演算法是最近未使用演算法。

它在存儲分塊表的每一表項中增加一個引用位，操作系統定期地將它們置為0。當某一頁被訪問時，由硬體將該位置1。過一段時間後，通過檢查這些位可以確定哪些頁使用過，哪些頁自上次置0後還未使用過。就可把該位是0的頁淘汰出去，因為在之前最近一段時間里它未被訪問過。

以上內容參考：網路-頁面置換演算法

7. LRU演算法具體怎麼算的，有沒有例子

有例子 LRU（least recently used）最近最久未使用。
假設 序列為 4 3 4 2 3 1 4 2
物理塊有3個 則
首輪 4調入內存 4
次輪 3調入內存 3 4
之後 4調入內存 4 3
之後 2調入內存 2 4 3
之後 3調入內存 3 2 4
之後 1調入內存 1 3 2（因為最近最久未使用的是4，從這里向前找最近最久未使用的）
之後 4調入內存 4 1 3（原理同上）
最後 2調入內存 2 4 1

過程就是這樣的，樓主只要明白最近最久未使用這個道理，再回去參考書上的例子就明白是怎麼算的啦！呵呵！

8. 求LRU演算法流程圖！！！

一行注釋沒有，懶得看

9. lru的演算法是什麼

lru的演算法是一種常用的頁面置換演算法，選擇最近最久未使用的頁面予以淘汰。該演算法賦予每個頁面一個訪問欄位，用來記錄一個頁面自上次被訪問以來所經歷的時間 t，當須淘汰一個頁面時，選擇現有頁面中其 t 值最大的，即最近最少使用的頁面予以淘汰。

對於虛擬頁式存儲，內外存信息的替換是以頁面為單位進行的——當需要一個放在外存的頁面時，把它調入內存，同時為了保持原有空間的大小，還要把一個內種調動越少，進程執行的效率也就越高。

硬體支持

LRU置換演算法雖然是一種比較好的演算法，但要求系統有較多的支持硬體。為了了解一個進程在內存中的各個頁面各有多少時間未被進程訪問，以及如何快速地知道哪一頁是最近最久未使用的頁面，須有兩類硬體之一的支持：寄存器或棧。

寄存器

為了記錄某進程在內存中各頁的使用情況，須為每個在內存中的頁面配置一個移位寄存器，可表示為：

R = Rn-1 Rn-2 Rn-3…R2 R1 R0。

10. LRU演算法解釋

看我寫的這個,有詳細注釋
.......................................

#include <stdio.h>
#include <stdlib.h>
#define mSIZE 3//分配三個內存頁塊
#define pSIZE 12//總共12個進程
struct mem
{
int num;
int count;
}memery[3]={0,-1,0,-1,0,-1};
static int process[pSIZE] ={1,2,3,4,1,2,5,1,2,3,4,5};//頁面訪問序列
void LRU();
void get();
int main()
{
get();
printf("\n(LRU)\treplace\n");
LRU();
system("PAUSE");
return 0;
}

void get()
{
int w[12]={1,2,3,4,1,2,5,1,2,3,4,5};
int i,n;
for(i=0;i<12;i++)
{
printf("%d ",w[i]);
}
}
void LRU()
{
int i = 0, j = 0,k=0,x,y;
int replace;

for(i = 0; i<pSIZE; i++) //對輸入序列進行循環
{
x=0;y=0; //置x，y初值為0
for(j = 0; j < mSIZE; j++) //對三個內存塊進行循環，先查找有沒有與即將訪問頁號相同的
if(memery[j].num == process[i])
{ x=1;//有相同的則置x為1
replace=process[i];
memery[j].count=0;//置此塊count為0
for(k=0;k<3;k++)
if(k!=j&&memery[k].num!=0)memery[k].count++;//其他不為0頁count++
break;//跳出此次內存塊循環
}

if(x==0)//沒有與即將訪問頁號相同的內存塊
{
for(j = 0; j < mSIZE; j++)//對內存塊循環，查找有沒有空內存塊
if(memery[j].num== 0)
{
y=1;//有則置y為1
replace=0;
memery[j].num=process[i];// 置此內存塊為訪問頁號
memery[j].count=0;//置此塊count為0
for(k=0;k<3;k++)
if(k!=j&&memery[k].num!=0)memery[k].count++;//其他不為0頁count++
break;//跳出此次內存塊循環
}
}

if(x==0&&y==0)//既沒有與即將訪問頁號相同的內存塊也沒有空內存塊
{
int m=memery[0].count;
for(j = 0; j < mSIZE; j++)
{
if(memery[j].count>m)
m=memery[j].count;
}//查找出count最大的內存塊m
for(j=0;j<mSIZE;j++)//對內存塊循環，count=m的內存塊
{
if(memery[j].count==m)
{
replace=memery[j].num;
memery[j].num=process[i]; //置此內存塊為訪問頁號塊
memery[j].count=0;//置此塊count為0
}
else memery[j].count++;//其他塊count++
}
}

for(j = 0 ;j < mSIZE; j++) //列印每次訪問後的情況
printf("%d ",memery[j].num);
printf("\t%d\n",replace);
}
}