LRU【Least Recently Used】LRU方式/LRU制御方式

CPUのキャッシュメモリやオペレーティングシステム（OS）の仮想記憶では、高速だが容量の小さい記憶装置を効率よく使い回しながら、その時々の処理に必要なデータを用意しなければならない。

空き領域がない状態で新たなデータを格納する必要が生じると、一定の規則に従って既存のデータを削除するか、より低速・大容量な記憶装置へ退避させて領域を確保する。この処理を「キャッシュ置換」または「ページ置換」という。

LRUでは、各データが最後に参照された時刻を記録しておき、置換が必要になった時点でその時刻が最も古いものを追い出し対象とする。直近に参照されたデータは近い将来も再び参照される可能性が高いという「局所参照性」の考え方に基づいている。

キャッシュの命中率を高める上で実績のある方式として、CPUのキャッシュメモリやOSの仮想記憶のほか、データベースやWebサーバなど様々な場面で採用されている。ただし、全アクセス履歴を正確に管理するには記憶領域と処理負荷が伴うため、実際のCPUキャッシュでは履歴管理を簡略化した「疑似LRU」（Pseudo-LRU）などの近似方式が用いられることも多い。

LRUと対比される置換方式として、最も最近参照されたデータを優先して削除する「MRU」（Most Recently Used）や、格納順に削除する「FIFO」（First In, First Out）、参照頻度の低いものを削除する「LFU」（Least Frequently Used）などがある。データの参照パターンやシステムの特性に応じて使い分けられ、例えばMRUはデータベースのフルスキャンのように同一データへの連続アクセスが起きにくい状況で有効とされる。