キャッシュの置換アルゴリズム
出典: 平成29年度 春期 応用情報技術者試験 午前 問16 (IPA)
4 ブロックのキャッシュメモリ C0～C3 が表に示す状態である。ここで，新たに別のブロックの内容をキャッシュメモリにロードする必要が生じたとき，C2 のブロックを置換の対象とするアルゴリズムはどれか。
| キャッシュメモリ | ロード時刻（分：秒） | 最終参照時刻（分：秒） | 参照回数 |
|---|---|---|---|
| C0 | 0:00 | 0:08 | 10 |
| C1 | 0:03 | 0:06 | 1 |
| C2 | 0:04 | 0:05 | 3 |
| C3 | 0:05 | 0:10 | 5 |
- ア FIFO
- イ LFU
- ウ LIFO
- エ LRU
正解と解説を見る
正解: エ
- ア: FIFO ではロード時刻が最も早い C0 が置換されます。
- イ: LFU では参照回数が最も少ない C1 が置換されます。
- ウ: LIFO ではロード時刻が最も遅い C3 が置換されます。
- エ: 最終参照時刻が最も古いのは C2 (0:05) なので、LRU で C2 が置換されます。正しい答えです。
ポイント
| 方式 | 追い出すブロック | この表では |
|---|---|---|
| FIFO | ロードが最も古い | C0 (0:00) |
| LFU | 参照回数が最も少ない | C1 (1 回) |
| LIFO | ロードが最も新しい | C3 (0:05) |
| LRU | 最終参照が最も古い | C2 (0:05) |