応用情報技術者 2017年 春期 午前2 問16
問題文
4ブロックのキャッシュメモリCO〜C3が表に示す状態である。ここで、新たに別のブロックの内容をキャッシュメモリにロードする必要が生じたとき、C2のブロックを置換の対象とするアルゴリズムはどれか。
選択肢
ア：FIFO
イ：LFU
ウ：LIFO
エ：LRU（正解）
4ブロックのキャッシュメモリ置換アルゴリズム【午前2 解説】
要点まとめ
- 結論：C2のブロックを置換対象とするのは「LRU（Least Recently Used）」アルゴリズムです。
- 根拠：LRUは「最も長く参照されていない」ブロックを置換するため、最終参照時刻が最も古いC2が対象となります。
- 差がつくポイント：参照回数やロード時刻ではなく「最終参照時刻」を基準に判断する点が重要です。
正解の理由
LRUは「最後に参照された時刻が最も古いデータを置換する」アルゴリズムです。
表を見ると、C2の最終参照時刻は0:05で、他のブロックよりも古いため、C2が置換対象となります。
FIFOはロード時刻が最も古いC0、LFUは参照回数が最も少ないC1、LIFOは最後にロードされたC3を置換するため、該当しません。
表を見ると、C2の最終参照時刻は0:05で、他のブロックよりも古いため、C2が置換対象となります。
FIFOはロード時刻が最も古いC0、LFUは参照回数が最も少ないC1、LIFOは最後にロードされたC3を置換するため、該当しません。
よくある誤解
最終参照時刻ではなく参照回数やロード時刻で判断しがちですが、LRUは「最終参照時刻」が基準です。
また、LIFOは「最後に入れたものを置換」と誤解されやすいですが、キャッシュ置換では一般的に使われません。
また、LIFOは「最後に入れたものを置換」と誤解されやすいですが、キャッシュ置換では一般的に使われません。
解法ステップ
- 表の各ブロックの「最終参照時刻」を確認する。
- 最も古い（最終参照時刻が最も早い）ブロックを探す。
- そのブロックが置換対象となる。
- 選択肢のアルゴリズムの特徴と照らし合わせて正解を選ぶ。
選択肢別の誤答解説
- ア: FIFO（First In First Out）
→ 最も古くロードされたC0（0:00）が置換対象となるため不正解。 - イ: LFU（Least Frequently Used）
→ 参照回数が最も少ないC1（1回）が対象であり、C2ではない。 - ウ: LIFO（Last In First Out）
→ 最後にロードされたC3（0:05）が対象であり、C2ではない。 - エ: LRU（Least Recently Used）
→ 最終参照時刻が最も古いC2（0:05）が正しく置換対象となる。
補足コラム
キャッシュ置換アルゴリズムは性能に大きく影響します。
- FIFOは実装が簡単ですが、参照頻度を考慮しないため効率が落ちることもあります。
- LFUは頻繁に使われるデータを残すため効率的ですが、参照回数の管理が必要です。
- LRUは「最近使われたものは今後も使われる可能性が高い」という仮定に基づき、実用的で広く使われています。
FAQ
Q: LRUはどのように実装されることが多いですか？
A: 一般的にはスタックやリンクリスト、またはハッシュマップと組み合わせて最終参照時刻を管理します。
A: 一般的にはスタックやリンクリスト、またはハッシュマップと組み合わせて最終参照時刻を管理します。
Q: LFUとLRUの違いは何ですか？
A: LFUは参照回数の少なさで置換対象を決め、LRUは最終参照時刻の古さで決めます。
A: LFUは参照回数の少なさで置換対象を決め、LRUは最終参照時刻の古さで決めます。
Q: LIFOはキャッシュ置換に適していますか？
A: 一般的には適していません。最後に入れたものをすぐ置換するため効率が悪いです。
A: 一般的には適していません。最後に入れたものをすぐ置換するため効率が悪いです。
関連キーワード: キャッシュメモリ、置換アルゴリズム、LRU, FIFO, LFU, LIFO, 最終参照時刻、参照回数
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！