LRU 簡易シミュレーション

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

全部は載らない

メモリは有限なので、OS はディスク上のページを必要な分だけメモリに載せます。載っていないページを触ると、そこで一度止まってディスクから読み直しになります。これがページフォルトで、キャッシュで言う miss です。載せられる枚数を増やせない以上、どれを追い出すかの判断がそのまま速さになります。

どれを捨てるかで、次に困る回数が変わる

LRU は Least Recently Used の略で、一番長いあいだ使われていないものを捨てる決め方です。根拠は経験則で、しばらく触っていないものはこの先も当分触られない、という観察に立っています。容量 2 で A B A C B の順に触ると、次のように動きます。

外れたのは 4 回です。3 手目で A を使っていなければ、捨てられるのは A だったので、その後の流れは変わっていました。過去の使われ方が、未来の捨て方を決めています。

この決め方は、名前を変えていろいろな場所に住んでいます。Redis の追い出し方針、ブラウザが持っている画像の控え、スマホで裏に回したアプリが落とされる順番も、おおむね同じ考え方です。

使っただけでも順番は動く

ここが一番間違えやすいところです。新しく入れたときだけ順番を更新すると、それは先に入れたものから捨てる決め方になり、名前だけ LRU の別物になります。すでに手元にあるものを使ったときにも、今使った、と記録し直します。列のいちばん後ろへ移す操作は、いったん抜いてから足すだけです。

配列で書くと、探すたびに端から見ていくことになります。学ぶあいだはこれで十分ですが、本物の OS や Redis は、連想配列と双方向のリストを組み合わせて、探す手間を一定にしています。

容量が足りないと、何を捨てても外れる

同時に触りたいものの数が、置ける枚数より多いときは、どんな決め方をしても毎回外れます。1 2 3 を繰り返し触るのに 2 枚しか置けない状態がそれで、追い出した直後にまたそれを取りに行く堂々巡りになります。追い出し方を変える前に、置ける量が足りているかを疑います。

1. lruMisses という名前の関数を実装すること
2. LRU 方式でミス回数を正しく数えること
3. ヒットしたページもキャッシュ内で最新に更新すること