LRU 簡易シミュレーション

手元に置ける量は決まっています。空きが無いのに新しいものを置きたくなったら、何かを捨てるしかありません。問題は、どれを捨てるかです。選び方ひとつで、次に取りに行く回数が変わります。

全部は載らない

OSはメモリを一定の大きさのページに分けて管理します。ここではディスク上のデータを、必要なページだけメモリへ載せる場面を考えます。載っていないページを使うと、ディスクから読むために待つことになります。この場面のページフォルトを、キャッシュのミスに対応させて数えます。

置ける枚数が限られるなら、次に使いそうなページを残したいところです。ただし未来のアクセスは分かりません。そこで過去の使われ方を手がかりにします。

最後に使った時点で順番を決める

LRUは Least Recently Used の略で、最も長いあいだ使われていないものを捨てる決め方です。「最近使ったものは、また使うかもしれない」という傾向を頼りにしています。最初に入れた順ではなく、最後に使った順を見る点が大切です。

順番の左を古い側、右を新しい側と決めると、動きを紙で追えます。ヒットなら、そのページを右端へ移すだけです。ミスなら回数を1増やし、満杯のときだけ左端を捨てて、新しいページを右端へ置きます。空きがあれば何も捨てません。

RedisにはLRUに近い追い出し方針があり、ブラウザの画像の控えにも、使われた時点を基準に残す考え方が役立ちます。ただし実際の製品では、厳密なLRUではなく近似した方法を使う場合もあります。

容量とアクセスの並びも見る

容量2でA、B、Cを順に繰り返すと、LRUでは次に必要なページを追い出し続け、毎回ミスになります。この状態なら、容量を増やすことや、アクセスの並びを見直すことを考えます。

必要なページの種類が容量より多いからといって、どんな方式でも毎回ミスになるわけではありません。同じページを続けて使えばヒットします。容量の数字だけでなく、実際の並びを見ます。

例題で確かめる

最初は空、容量2で、A、B、A、C、Bの順にアクセスします。表の中身は左が古く、右が新しい順です。

ミスは4回です。3手目のAで順番が変わるので、4手目ではBを捨てます。ヒットでも順番が動くことを、この1行から確かめられます。