応用情報技術者 2010年 春期 午前2 問18
問題文
表のような状態の4ブロック分のキャッシュメモリ CO 〜C3がある。ここで、新たに別のブロックの内容をキャッシュメモリにロードする必要が生じたとき、C2の内容を置換の対象とするアルゴリズムはどれか。
選択肢
ア：FIFO
イ：LFU
ウ：LIFO
エ：LRU（正解）
キャッシュメモリの置換アルゴリズム【午前2 解説】
要点まとめ
- 結論：C2の内容を置換対象とするのは「LRU（Least Recently Used）」アルゴリズムです。
- 根拠：LRUは最終参照時刻が最も古いブロックを置換するため、最終参照時刻が0:05のC2が選ばれます。
- 差がつくポイント：FIFOやLFUは参照順序や参照回数に基づくため、最終参照時刻を正しく理解し区別できるかが重要です。
正解の理由
LRUは「最も長い間参照されていないデータを置換する」アルゴリズムです。
表の最終参照時刻を見ると、C2は0:05で他のブロックよりも古いため、C2が置換対象となります。
FIFOはロード時刻順、LFUは参照回数順、LIFOは最後にロードされた順で置換するため、C2は該当しません。
表の最終参照時刻を見ると、C2は0:05で他のブロックよりも古いため、C2が置換対象となります。
FIFOはロード時刻順、LFUは参照回数順、LIFOは最後にロードされた順で置換するため、C2は該当しません。
よくある誤解
FIFOは「最初に入ったものを置換」と誤解されがちですが、参照履歴は考慮しません。
LFUは参照回数が少ないものを置換しますが、最終参照時刻は無視します。
LFUは参照回数が少ないものを置換しますが、最終参照時刻は無視します。
解法ステップ
- 表の各ブロックの「ロード時刻」「最終参照時刻」「参照回数」を確認する。
- 置換アルゴリズムの特徴を整理する（FIFO、LFU、LIFO、LRU）。
- 問題文の条件「C2が置換対象」となるアルゴリズムを特定する。
- 最終参照時刻が最も古いC2を選ぶLRUが正解と判断する。
選択肢別の誤答解説
- ア: FIFOはロード時刻が最も古いC0（0:00）を置換するため不正解。
- イ: LFUは参照回数が最も少ないC1（1回）を置換するため不正解。
- ウ: LIFOは最後にロードされたC3（0:05）を置換するため不正解。
- エ: LRUは最終参照時刻が最も古いC2（0:05）を置換するため正解。
補足コラム
LRUはキャッシュ置換アルゴリズムの中でも最も直感的で広く使われています。
実装には参照履歴の管理が必要で、ハードウェアやソフトウェアで工夫されています。
一方、LFUは参照頻度を重視し、FIFOは単純な順序管理、LIFOはスタック構造に似ています。
実装には参照履歴の管理が必要で、ハードウェアやソフトウェアで工夫されています。
一方、LFUは参照頻度を重視し、FIFOは単純な順序管理、LIFOはスタック構造に似ています。
FAQ
Q: LRUとFIFOの違いは何ですか？
A: FIFOは「最初に入ったもの」を置換し、LRUは「最も長く使われていないもの」を置換します。
A: FIFOは「最初に入ったもの」を置換し、LRUは「最も長く使われていないもの」を置換します。
Q: 参照回数が多いブロックは置換されにくいですか？
A: LFUでは参照回数が多いほど置換されにくいですが、LRUでは参照回数は関係ありません。
A: LFUでは参照回数が多いほど置換されにくいですが、LRUでは参照回数は関係ありません。
関連キーワード: キャッシュメモリ、置換アルゴリズム、LRU, FIFO, LFU, LIFO, 最終参照時刻
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！