什麼是LRU(最近最少使用)

逐出最長時間未被使用的資料的快取置換方式。能充分利用時間局部性，但路數多時難以精確管理，因此會使用近似的方式。

日文名稱: LRU(Least Recently Used)

「LRU(最近最少使用)」出現在2領域的6道練習題中（記憶體階層與效能, 作業系統與硬體等）。

這個名詞所屬的領域: 記憶體階層與效能

練習LRU(最近最少使用)的題目

容量為2條快取行、採LRU替換的全相聯快取一開始為空，依A、B、A、C、B、A的順序參照區塊時，會發生幾次未命中？

  1. A4次
  2. B5次
  3. C6次
查看答案與解析

正確答案：B. 5次

依序追蹤：A（未命中，[A]）、B（未命中，[A,B]）、A（命中，A變成最近使用）、C（未命中，逐出最舊的B，[A,C]）、B（未命中，逐出最舊的A，[C,B]）、A（未命中，逐出最舊的C，[B,A]），共未命中5次。算成4次，是例如在放入C時誤以為逐出了A等的算法，在LRU中重點在於命中的A已變成最新。6次是漏看第3次A的命中所得的次數。

相對於逐出最久未被使用者的LRU，逐出今後最長時間不會被使用者的方式（最佳替換，OPT），下列說明何者正確？

  1. A是實際快取中廣泛使用、最一般的替換方式
  2. B雖然無法實現，但可作為其他方式未命中數下限的基準
  3. C無論什麼存取順序，未命中數都與LRU完全相同
查看答案與解析

正確答案：B. 雖然無法實現，但可作為其他方式未命中數下限的基準

最佳替換（Belady的OPT）假設已知未來的存取順序，逐出下次使用時間最遠的資料，未命中數在理論上最小。然而實際的硬體無法得知未來的存取，因此無法實現，而是套用到已記錄的存取序列上，用來評估LRU等方式距離最佳有多近。由於與LRU逐出的資料不同，未命中數一般也不相同。

解析中的「LRU(最近最少使用)」

出現「LRU(最近最少使用)」的題目（6題）

  1. 容量為2條快取行、採LRU替換的全相聯快取一開始為空，依A、B、A、C、B、A的順序參照區塊時，會發生幾次未命中？
  2. 相對於逐出最久未被使用者的LRU，逐出今後最長時間不會被使用者的方式（最佳替換，OPT），下列說明何者正確？
  3. 在分頁置換的時鐘演算法（第二次機會演算法）中，使用各分頁參照位元的目的為何？
  4. 在分頁置換使用FIFO方式時，即使增加了實體記憶體的分頁數，分頁錯誤有時反而會增加。這種現象稱為什麼？
  5. 在寫回（write-back）快取中，附加於各快取行的髒位元（dirty bit）的作用，下列何者正確？
  6. 附加在快取各快取行上的有效位元（valid bit）的作用，下列何者正確？

相關名詞

快取行 全相聯快取 更新(Refresh) 抖動(Jitter) 寫入時複製 失誤懲罰 平均記憶體存取時間(AMAT) 直接映射快取 空間局部性 非阻塞快取

前往名詞解釋列表