キャッシュの置換アルゴリズム
出典: 令和7年度 秋期 応用情報技術者試験 午前 問19 (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 は参照回数が最も少ないものを追い出すので、参照回数 1 回の C1 が対象になります。
- ウ: LIFO は最後にロードしたものを追い出すので、ロード時刻が最も遅い C3 が対象になります。
- エ: LRU は最終参照時刻が最も古いものを追い出します。C2 の 0:05 が最も古いので正しい答えです。
ポイント
それぞれの方式で置換の対象になるブロックは次のとおりです。
| 方式 | 選ぶブロック | この表では |
|---|---|---|
| FIFO | 最も早くロードされたもの | C0 (0:00) |
| LFU | 参照回数が最も少ないもの | C1 (1回) |
| LIFO | 最も遅くロードされたもの | C3 (0:05) |
| LRU | 最後に参照されてから最も時間がたったもの | C2 (0:05) |