基本情報技術者 2009年 春期 午前（科目A） 問20

LRU置換方式【午前解説】

正解の理由

解法ステップ

1. 設問文のキーワードを確認：「最後に参照されてから最も長い時間」→ 時間経過に基づく「最も最近参照されていない」。
2. 各方式の特徴を照合する：
   • LRU：最も長く参照されていない（最近使われていない）ものを置換
   • LFU：参照頻度が最も低いものを置換
   • FIFO：読み込まれてから最も長いもの（到着順）を置換
   • タイムアウト/アイドル：参照が無く一定時間経過したものを置換（閾値による）
3. キーワードの一致でイを選ぶ。

# OrderedDict を使ったLRUキャッシュの骨子
from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.data = OrderedDict()

    def access(self, key, value=None):
        if key in self.data:
            # 最近使ったので末尾に移動
            self.data.move_to_end(key)
        else:
            if len(self.data) >= self.cap:
                # 先頭が最長未使用（LRU）
                self.data.popitem(last=False)
            self.data[key] = value

選択肢別の誤答解説

• ア: 一定時間参照されていないブロック
  「一定時間」を閾値として切る場合は、TTL（タイムアウト）やアイドル時間ベースの追放に相当します。これは時間閾値に基づくポリシーであり、LRUの定義（相対的に最も長く参照されていないものを選ぶ）とは異なります。MRU（Most Recently Used）とは無関係です。
• イ: 最後に参照されてから最も長い時間が経過したブロック
  LRUの定義そのもので正解です。各ブロックの最終参照時刻（または参照順序）を比較して最古のものを置換します。
• ウ: 参照頻度の最も低いブロック
  これはLFU（Least Frequently Used）です。参照回数の累積を基準にする方式で、LRUとは基準が「頻度」か「直近性」かで異なります。
• エ: 読み込んでから最も長い時間が経過したブロック
  これはFIFO（First-In First-Out）に近い考え方です。キャッシュに入った順序（到着順）を基準にして追い出す方式で、参照が行われたかどうかは無視します。LRUとは明確に異なります。

よくある誤解

• 「一定時間参照されていない＝LRU」と混同する誤り
  一定時間無参照だから追い出す方式は、閾値（TTL）に基づく固定時間のルールであり、LRUの「相対比較（どれが最も長く未参照か）」とは別物です。実装や評価基準が変わります。
• MRUとLRUの混同
  MRU（Most Recently Used）は「最近使われたものを追い出す」方式で、LRUの反対です。用途は限定的であり混同しないように注意してください。

補足コラム

• 実装上の工夫と近似アルゴリズム
  真のLRUは全ブロックの最終参照情報を管理する必要がありコストが高い場合があります。OSやハードウェアでは簡易化した近似方式（CLOCKアルゴリズム＝参照ビットを使う擬似LRU）がよく使われます。CLOCKは参照ビットを巡回して0のものを置換することで、LRUに近い振る舞いを低コストで実現します。
• 適用場面
  LRUは「最近使われたものは近い将来も使われる」という局所性の仮定が成立するワークロードで効果的です。一方、参照パターンが巡回的（ストリーミング）な場合はFIFOやその他の策略が有利になることがあります。

FAQ