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

lru算法？

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

執(zhí)行LRU

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

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

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

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

LFU算法LFU算法過(guò)程是什么，呵LRU算？

LRU是最近最少使用的頁(yè)面替換算法（最近最少使用），即首先消除最長(zhǎng)未使用的頁(yè)面！LFU是最近使用最少的頁(yè)面替換算法（最少頻繁使用），即在一定時(shí)間內(nèi)消除最少訪問(wèn)的頁(yè)面！例如，第二方法的周期T是10分鐘。如果每分鐘分頁(yè)一次，則內(nèi)存塊為3，如果所需的頁(yè)方向?yàn)?121234，請(qǐng)注意，調(diào)用第4頁(yè)時(shí)會(huì)出現(xiàn)缺頁(yè)。根據(jù)LRU算法，第1頁(yè)應(yīng)該被替換（第1頁(yè)的使用時(shí)間最長(zhǎng)），但是第3頁(yè)應(yīng)該根據(jù)LFU算法被替換（第3頁(yè)每十分鐘才使用一次）。可以看出，LRU的關(guān)鍵是看頁(yè)面從上次使用到調(diào)度的時(shí)間，而LFU的關(guān)鍵是看頁(yè)面在一定時(shí)間段內(nèi)的使用頻率

最佳頁(yè)面淘汰算法是怎樣計(jì)算的？

1 50%指令序列執(zhí)行225%前地址部分指令均勻走行325%后地址部分指令均勻走行：命中率=1-頁(yè)面失敗次數(shù)（僅使用2的冪次）/葉地址流長(zhǎng)度算法：opt FIFO RLU（定義）（至少有兩種算法）程序流程圖開(kāi)始：根據(jù)假設(shè)生成給定長(zhǎng)度的指令地址流-> set initial calculation size=1~8（1，2，4，8）（第頁(yè)）real memory=4~32（4，8，16，32）->輸入消除算法->A->alg=FIFO（或）（LRU）->fifo->使用FIFO計(jì)算命中率->使用LRU計(jì)算命中率->輸出結(jié)果->結(jié)束算法定義：理想消除算法-在最佳頁(yè)面算法（OPT）之后不再需要或?qū)⒃谧钸h(yuǎn)的將來(lái)使用的頁(yè)面被淘汰了。FIFO選擇內(nèi)存中駐留時(shí)間最長(zhǎng)的頁(yè)并將其消除。LRU從當(dāng)前時(shí)間中選擇最后一次訪問(wèn)時(shí)間最長(zhǎng)的頁(yè)面，首先進(jìn)行消頁(yè)，LRU是最近一次未使用的消頁(yè)算法。他的想法是刪除那些沒(méi)有被訪問(wèn)時(shí)間最長(zhǎng)的頁(yè)面。LFU是最新的最少使用頁(yè)面消除算法，其思想是：永遠(yuǎn)把當(dāng)前使用最少的頁(yè)面去掉。

從字面上看，似乎這兩種算法是相似的，很難理解。但是讓我們舉個(gè)例子，你可以完全理解它：

例如，內(nèi)存可以存儲(chǔ)6頁(yè)，現(xiàn)在內(nèi)存中的頁(yè)是2，1，1，1，3，2

使用LRU：下一個(gè)要?jiǎng)h除的頁(yè)是1，因?yàn)樗罱鼪](méi)有被使用過(guò)

使用LFU：要?jiǎng)h除的頁(yè)是3，因?yàn)?至少只被使用過(guò)一次說(shuō)到緩存，必須考慮兩點(diǎn)

緩存數(shù)據(jù)和目標(biāo)數(shù)據(jù)的一致性。

緩存過(guò)期策略（機(jī)制）。

其中，緩存過(guò)期策略涉及消除算法。常用的消去算法如下：

FIFO:先進(jìn)先出

LRU:最近最少使用

LFU:最近最少使用

注意LRU和LFU的區(qū)別。LFU算法根據(jù)數(shù)據(jù)項(xiàng)在一段時(shí)間內(nèi)的使用次數(shù)來(lái)選擇使用最少的數(shù)據(jù)項(xiàng)，即根據(jù)使用次數(shù)的不同來(lái)確定。LRU根據(jù)使用時(shí)間的不同而確定。