lru算法？LRU算法的設(shè)計原則是：如果一個數(shù)據(jù)最近一段時間沒有被訪問過，那么它在將來就不太可能被訪問。換言之，當(dāng)有限的空間充滿數(shù)據(jù)時，應(yīng)該消除最長時間未被訪問的數(shù)據(jù)。執(zhí)行LRU1。使用數(shù)組存儲數(shù)據(jù)，

lru算法？

LRU算法的設(shè)計原則是：如果一個數(shù)據(jù)最近一段時間沒有被訪問過，那么它在將來就不太可能被訪問。換言之，當(dāng)有限的空間充滿數(shù)據(jù)時，應(yīng)該消除最長時間未被訪問的數(shù)據(jù)。

執(zhí)行LRU

1。使用數(shù)組存儲數(shù)據(jù)，用訪問時間戳標(biāo)記每個數(shù)據(jù)項。插入新數(shù)據(jù)項時，首先增加數(shù)組中現(xiàn)有數(shù)據(jù)項的時間戳，將新數(shù)據(jù)項的時間戳設(shè)置為0，然后將其插入數(shù)組中。每次訪問數(shù)組中的數(shù)據(jù)項時，所訪問數(shù)據(jù)項的時間戳都設(shè)置為0。當(dāng)數(shù)組空間已滿時，時間戳最大的數(shù)據(jù)項將被刪除。

2. 使用鏈表實現(xiàn)，每次插入新數(shù)據(jù)時，將新數(shù)據(jù)插入鏈表的頭部；每次緩存命中時，將數(shù)據(jù)移動到鏈表的頭部（即訪問數(shù)據(jù)）；然后在鏈表已滿時丟棄鏈表末尾的數(shù)據(jù)。

3. 使用鏈表和HashMap。當(dāng)需要插入新數(shù)據(jù)項時，如果新數(shù)據(jù)項存在于鏈表中（通常稱為hit），請將節(jié)點移動到鏈表的頭部。如果不存在，則創(chuàng)建一個新節(jié)點并將其放在鏈表的頭部。如果緩存已滿，請刪除鏈表的最后一個節(jié)點。在訪問數(shù)據(jù)時，如果鏈表中存在該數(shù)據(jù)項，則節(jié)點會移到鏈表的頭，否則返回-1。這樣，鏈表末尾的節(jié)點就是最近不可訪問的數(shù)據(jù)項。

對于第一種方法，需要連續(xù)維護(hù)數(shù)據(jù)項的訪問時間戳。另外，在插入數(shù)據(jù)、刪除數(shù)據(jù)和訪問數(shù)據(jù)時，時間復(fù)雜度為O（n）。對于第二種方法，鏈表的時間復(fù)雜度為O（n）。所以一般來說，第三種方法是實現(xiàn)LRU算法。

最佳頁面淘汰算法是怎樣計算的？

1 50%指令序列執(zhí)行225%前地址部分指令均勻走行325%后地址部分指令均勻走行：命中率=1-頁面失敗次數(shù)（僅使用2的冪次）/葉地址流長度算法：opt FIFO RLU（定義）（至少有兩種算法）程序流程圖開始：根據(jù)假設(shè)生成給定長度的指令地址流-> set initial calculation size=1~8（1，2，4，8）（第頁）real memory=4~32（4，8，16，32）->輸入消除算法->A->alg=FIFO（或）（LRU）->fifo->使用FIFO計算命中率->使用LRU計算命中率->輸出結(jié)果->結(jié)束算法定義：理想消除算法-在最佳頁面算法（OPT）之后不再需要或?qū)⒃谧钸h(yuǎn)的將來使用的頁面被淘汰了。FIFO選擇內(nèi)存中駐留時間最長的頁并將其消除。LRU從當(dāng)前時間中選擇最后一次訪問時間最長的頁面并消除它LRU是最近最少使用的頁面替換算法，即首先消除最長未使用的頁面！LFU是使用頻率最低的頁面替換算法，即在一定時間內(nèi)消除最少訪問的頁面！例如，如果主存儲器塊是3，并且所需的頁方向是21234，則第二方法的周期T是10分鐘。請注意，調(diào)用第4頁時會發(fā)生缺頁中斷。根據(jù)LRU算法，第1頁應(yīng)該被替換（第1頁的使用時間最長），但是第3頁應(yīng)該根據(jù)LFU算法被替換（第3頁每十分鐘才使用一次）?？梢钥闯觯琇RU的關(guān)鍵是查看從上次使用頁面到調(diào)度的時間，而LFU的關(guān)鍵是查看某段時間內(nèi)使用頁面的頻率！