LRU(Least Recently Used)とは
えるあーるゆー
最も長い間使われていないデータを追い出すキャッシュの置き換え方式。時間的局所性をうまく生かせるが、ウェイが多いと正確な管理が難しく、近似した方式が使われる。
この用語の分野: メモリ階層と性能
解説の中の「LRU(Least Recently Used)」
4回とするのは、Cを入れるときにAを追い出したと誤った場合などの数え方で、LRUではヒットしたAが新しくなっている点が大切です。
容量2ラインのフルアソシアティブ方式でLRU置き換えのキャッシュが最初は空のとき、ブロックをA、B、A、C、B、Aの順…しかし実際のハードウェアは未来のアクセスを知ることができないため実現できず、記録したアクセスの並びに当てはめて、LRUなどの方式がどれだけ最適に近いかを評価するのに使います。
最も長い間使われていないものを追い出すLRUに対して、今後最も長い間使われないものを追い出す方式(最適置き換え、OPT…正確なLRUはアクセスのたびに順番を更新する必要があり、ページの数が多いと手間がかかります。
ページ置き換えのクロック方式(セカンドチャンス方式)で、各ページの参照ビットを使う目的はどれか。
「LRU(Least Recently Used)」が出てくる問題(6問)
- 容量2ラインのフルアソシアティブ方式でLRU置き換えのキャッシュが最初は空のとき、ブロックをA、B、A、C、B、Aの順に参照すると、ミスは何回起こるか。
- 最も長い間使われていないものを追い出すLRUに対して、今後最も長い間使われないものを追い出す方式(最適置き換え、OPT)についての説明として正しいものはどれか。
- ページ置き換えのクロック方式(セカンドチャンス方式)で、各ページの参照ビットを使う目的はどれか。
- ページ置き換えでFIFO方式を使うと、物理メモリのページ数を増やしたのにページフォルトが増える場合がある。この現象を何と呼ぶか。
- ライトバック方式のキャッシュで、各ラインに付けるダーティビットの役割として正しいものはどれか。
- キャッシュの各ラインに付けられる有効ビット(valid bit)の役割として正しいものはどれか。
関連する用語
フルアソシアティブ方式 ページフォルト スラッシング コピーオンライト キャッシュライン 競合ミス 空間的局所性 時間的局所性 初期参照ミス セットアソシアティブ方式