Least Recently Used

出典: フリー百科事典『ウィキペディア(Wikipedia)』
2013年6月25日 (火) 21:54時点におけるKomugiko (トーク)による版 (具体的なアルゴリズム)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先: 案内検索

Least Recently Used (LRU) はキャッシュメモリ仮想メモリが扱うデータリソースへの割り当てを決定するアルゴリズムである。対義語はMost Recently Used (MRU)。

和訳すると「最も最近使われなかったもの」つまり「使われてから最も長い時間が経ったもの」「参照される頻度が最も低いもの」である。

小容量で高速な記憶装置(例えば、キャッシュメモリ)がいっぱいになったとき、その中にあるデータのうち、未使用の時間が最も長いデータを大容量で低速な記憶装置(例えば、主記憶装置)に保存する、というのが基本のアルゴリズムである。

なお、上の括弧内の例はキャッシュメモリの場合である。仮想メモリの場合は、小容量で高速な記憶装置を主記憶装置、大容量で低速な記憶装置を補助記憶装置に置き換えればよい。

具体的なアルゴリズム

それぞれのエントリごとに、「いつ使用したか」を示すデータを保存する。エントリを使用するごとにそのデータを更新していく。エントリが更新されるタイミングで、それらの時刻を全エントリに対してチェックすると、「最も使用されていないエントリ」が判明する。これが、理想的なLRUアルゴリズムである。しかし、この方法はとても処理に時間がかかる(O(n))ため、ほとんど使用されない。

多くの場合、処理を簡単化した擬似的なLRUが用いられる。たとえば、すべてのエントリに「最近使用したかどうか」を示すフラグ(dirty flag)を設ける。一度すべてをリセットし、エントリを使用するごとにそのフラグをセットする。一定のタイミング、またはエントリを更新する際にそれらのフラグをチェックすると、「最近使用されていないエントリ」が判明する。適当なタイミングで、またすべてのフラグをリセットする。 これは、完全なLRUではないが、多くの場合非常に近い性能を発揮する。

その他

LRUは、コンピュータに限らず、いわゆる「整理法」にも使われている。たとえば、読み終わった本を本棚の一番右側に戻すようにしておくと、左側に読む頻度の少ない本が集まり、処分すべき本を簡単に決めることができると言われている。

LRUは、特定のパターンの場合に極端に悪いパフォーマンスを示すことが知られている。たとえば、N個のエントリがある場合に、N+1個のエントリを順番に使用した場合、常にエントリの内容が変更されてしまう。

関連項目