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

LRUアルゴリズムで、ページ置換えの判断基準に用いられる項目はどれか。【午前2 解説】

要点まとめ

• 結論：LRU（Least Recently Used）は各ページの「最後に参照した時刻」を基準に、最も長く参照されていないページを置換する方式であるため正解は最後に参照した時刻です。
• 根拠：LRUは「直近の参照が再利用の強い指標」という経験則に基づき、参照の新しさ（recency）を重視して置換対象を決めます。
• 差がつくポイント：最初に参照した時刻や累積参照回数、参照頻度はLFUや統計的手法に関係し、LRUとは評価基準が異なる点を押さえてください。

正解の理由

よくある誤解

• 「参照回数が多いページは残すべき」と考えLFUと混同する誤り：LRUは頻度ではなく直近の参照時刻を見る方式です。
• 「最初に参照した時刻が古い＝使われていない」と誤解すること：最初に参照した時刻は寿命（age）を示すのみで、直近の利用状況を反映しません。
• 実装上は厳密な時刻を管理する必要があると考える誤り：ハードウェアやOSでは近似（参照ビットやCLOCK）で実現する場合が多いです。

解法ステップ

1. 問題文からキーワード「LRU（Least Recently Used）」を確認する。
2. LRUの意味：直近（recently）の使用状況を基に最も最近使われていないものを置換する方式であると理解する。
3. 選択肢を照合する：直近の使用＝最後に参照した時刻が該当するのでアを選ぶ。
4. 他選択肢は頻度や初回時刻に関するものなのでLRUの定義と合致しないと判断する。

選択肢別の誤答解説

• ア: 正解 — 「最後に参照した時刻」を基準にして最も古い（長く使われていない）ページを置換するのがLRUの定義です。
• イ: 誤り — 「最初に参照した時刻」はページの生存期間や作成時刻の指標であり、直近の再利用性を示す指標ではないためLRUの判断基準ではありません。
• ウ: 誤り — 「単位時間当たりの参照頻度」はアクセス頻度を扱う指標でLFU（Least Frequently Used）や統計的手法に関連し、LRUの基準とは異なります。
• エ: 誤り — 「累積の参照回数」も頻度ベースの指標であり、直近の参照タイミングを見て置換するLRUとは評価軸が違います。

補足コラム

• LRUの実装手法：厳密なLRUは各参照でスタックやタイムスタンプを更新する必要がありコストが高いです。実運用では参照ビット（Rビット）を周期的にクリアして近似するCLOCKアルゴリズムや、セグメント化したキャッシュなどで性能とコストを両立します。
• 性能特性：LRUは「局所性（temporal locality）」が強いワークロードで有効です。逆に頻度重視のワークロードではLFUの方が良い場合があります。
• 理論的性質：LRUはスタックアルゴリズムの一種であり、スタック距離が短いほどページフォールト率が低下します。スタックアルゴリズムはメモリサイズが増えると必然的にフォールト数が減る性質を持ちます（Beladyの異常を起こしにくい）。

FAQ