メモリ階層と性能
容量2ラインのフルアソシアティブ方式でLRU置き換えのキャッシュが最初は空のとき、ブロックをA、B、A、C、B、Aの順に参照すると、ミスは何回起こるか。
- A4回
- B5回
- C6回
答えと解説を見る
正解：B. 5回
順に追うと、A(ミス、[A])、B(ミス、[A,B])、A(ヒット、Aが最近)、C(ミス、最も古いBを追い出し[A,C])、B(ミス、最も古いAを追い出し[C,B])、A(ミス、最も古いCを追い出し[B,A])となり、ミスは5回です。4回とするのは、Cを入れるときにAを追い出したと誤った場合などの数え方で、LRUではヒットしたAが新しくなっている点が大切です。6回は3回目のAのヒットを見落とした数です。
- A. 4回は追い出すブロックを誤った数え方です。
- B. 正しい。ヒットは3回目のAだけで、ミスは5回です。
- C. 6回は3回目のAのヒットを見落とした数です。