ある計算機が16個の32バイトからなるブロック (M0～M15) で構成されている主記憶を持っているとする。この計算機は、4個の32バイトからなるブロック (C0～C3) で構成されるキャッシュを持っており、次のようなセットアソシアティブ (Set Associative) 方式で制御されているとする。
「キャッシュブロックC0とC2は偶数メモリブロック (M0, M2, ..., M14) を格納することができ、キャッシュブロックC1とC3は奇数メモリブロック (M1, M3, ..., M15) を格納することができる。」
この計算機のCPUが次のようなメモリブロックのアクセスを行うとき、キャッシュの追い出しにLRU (Least Recently Used) アルゴリズムを用いた場合のキャッシュの最終状態を①～⑤の中から選べ。ただし、キャッシュブロックへの格納はC0
→ C2、C1 → C3の順に行われるものとする。
アクセス順 M0, M1, M2, M3, M0, M1, M4, M5, M4, M5, M1, M3
① C0:M4, C1:M3, C2:M2, C3:M1
② C0:M4, C1:M5, C2:M2, C3:M3
③ C0:M0, C1:M1, C2:M4, C3:M3
④ C0:M0, C1:M3, C2:M4, C3:M5
⑤ C0:M0, C1:M1, C2:M4, C3:M5
③
LRU (Least Recently Used) は、参照されていない時間が最も長いページを置換対象とするアルゴリズムである。
メモリブロックへのアクセス順にキャッシュブロックの状態は以下の通りとなる。
M0 C0:M0, C1:--, C2:--, C3:--
M1 C0:M0, C1:M1, C2:--, C3:--
M2 C0:M0, C1:M1, C2:M2, C3:--
M3 C0:M0, C1:M1, C2:M2, C3:M3
M0 C0:M0, C1:M1, C2:M2, C3:M3
M1 C0:M0, C1:M1, C2:M2, C3:M3
M4 C0:M0, C1:M1, C2:M4, C3:M3
M5 C0:M0, C1:M1, C2:M4, C3:M5
M4 C0:M0, C1:M1, C2:M4, C3:M5
M5 C0:M0, C1:M1, C2:M4, C3:M5
M1 C0:M0, C1:M1, C2:M4, C3:M5
M3 C0:M0, C1:M1, C2:M4, C3:M3
| Ⅳ－１１ | 目次 | Ⅳ－１３ |