基本情報技術者 2014年秋期午前（科目A）問16

問題文

キャッシュメモリと主記憶との間でブロックを置き換える方式にLRU方式がある。この方式で置換えの対象になるブロックはどれか。

選択肢

ア：一定時間参照されていないブロック

イ：最後に参照されてから最も長い時間が経過したブロック（正解）

ウ：参照頻度の最も低いブロック

エ：読み込んでから最も長い時間が経過したブロック

キャッシュ置換方式のLRUとは何か【午前2 解説】

要点まとめ

結論→LRU方式は「最後に参照されてから最も長い時間が経過したブロック」を置換対象とするため、選択肢イが正解です。
根拠→LRUは Least Recently Used の略で、参照の「新しさ（直近性）」を基準に置換対象を決めるアルゴリズムだからです。
差がつくポイント→「参照頻度」や「読み込んでからの経過時間」と混同しないこと。LRUはあくまで直近の参照時刻を評価します。

正解の理由

LRU（Least Recently Used）は、直近で参照されていない時間が最も長いブロックを置換する方式です。問題文の選択肢のうち「最後に参照されてから最も長い時間が経過したブロック」をその定義どおり表しているため正解になります。LRUは「いつ最後に参照されたか」を記録しておき、置換時に最も古い参照時刻のものを選びます。

よくある誤解

「一定時間参照されていないブロック（ア）」＝LRUと考える誤り：閾値を用いる意味合いになり、LRUは閾値による判定ではありません。
「参照頻度が低いもの（ウ）」＝LRUと混同する誤り：これはLFU（Least Frequently Used）で、LRUとは基準が異なります。
「読み込んでからの経過時間（エ）」＝FIFOと混同する誤り：読み込み順（到着順）を基準にするのはFIFOであり、参照の直近性ではありません。

解法ステップ

問題のキーワードを確認：「最後に参照されてから」や「参照頻度」など。
LRUの定義を思い出す：「Least Recently Used＝直近の参照の新しさで置換を決める」。
各選択肢を定義と照合し、直近性を表す選択肢を選ぶ（イを選択）。

選択肢別の誤答解説

ア: 一定時間参照されていないブロック
→ 閾値による「一定時間未参照」を基準にしており、LRUの定義とは異なります。タイムアウト方式に近く誤りです。
イ: 最後に参照されてから最も長い時間が経過したブロック
→ LRUの定義そのものです。最後の参照時刻が最も古いブロックを置換するため正解です。
ウ: 参照頻度の最も低いブロック
→ 参照回数を基準にするのはLFUであり、LRUとは基準が異なります。誤りです。
エ: 読み込んでから最も長い時間が経過したブロック
→ 読み込み（到着）順を基準にする方式はFIFOであり、LRUではありません。よって誤りです。

補足コラム

LRUは理にかなった置換方針で、多くのキャッシュ実装で用いられますが、完全な最適解ではありません。実装コスト（すべての参照時刻を更新する必要）や大規模キャッシュでの管理オーバーヘッドが問題になり、ハードウェアやOSでは近似手法（CLOCKアルゴリズムやセグメント化したLRU、スタックアルゴリズムなど）が使われます。また、FIFOではベラディの異常（キャッシュサイズが増えるとミス率が増える現象）が起き得ますが、LRUはその点でより安定した振る舞いを示すことが多いです。

FAQ

Q1: LRUとLFUのどちらが良いですか？
A1: ワークロード次第です。最近参照されたデータにまた参照が来やすい場合はLRUが有利で、一定の頻度で長期的に参照されるデータが多い場合はLFUが有利です。実用上は両者を組み合わせた手法もあります。

Q2: LRUの実装は難しいですか？
A2: 単純には参照のたびにタイムスタンプ更新やリストの再配置が必要でオーバーヘッドがあります。ハッシュ＋双方向リストでO(1)に実装する方法や、近似アルゴリズム（CLOCKなど）で軽量化する手法が一般的です。

Q3: 「読み込んでからの経過時間」はいつ使う？
A3: 読み込み順を基準にするのはFIFOで、到着順で古いページを追い出す場面で使います。I/O到着順に特化したケースで採用されますが、参照の直近性を無視するためミスが増えることがあります。

関連キーワード: キャッシュメモリ、LRU、キャッシュ置換、参照履歴、主記憶、FIFO、LFU、CLOCK、置換アルゴリズム

← 前の問題へ次の問題へ →

\ せっかくなら /

基本情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！