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

LRUページ置換え方式【午前解説】

正解の理由

解法ステップ

1. 問題文の「LRU制御方式はどれか」をキーワードに定義を思い出す：Least Recently Used＝最近使われていないものを置換。
2. 各選択肢の述語を「最後に参照された時刻」「参照フラグ」「到着時刻」「無作為」のどれに基づくかで分類する。
3. 「最後に参照された時刻」を基準にしている選択肢があればそれがLRUなので正解とする。
4. 他選択肢はそれぞれ FIFO、ランダム、NRU（または改良版）などと判別し、理由を確認して誤りを説明する。

選択肢別の誤答解説

• ア: 各ページに参照フラグと変更フラグを付加して管理し、参照なしかつ変更なしのページを優先して置き換える。
  解説：これは NRU（Not Recently Used）や改良型の置換戦略（参照フラグ／変更フラグを使った優先度分類）に近い説明であり、LRU の定義ではありません。参照フラグは最近参照されたかを示すだけで、最後参照時刻の完全な順序を保持しているわけではありません。よって誤りです。
• イ: 主記憶にある全てのページを同一の確率でランダムに選択し、置き換える。
  解説：これはランダム置換法（Random Replacement）で、参照履歴を全く使わない方式です。LRU とは無関係なので誤りです。
• ウ: 最も長い間参照されていないページを置き換える。
  解説：これが LRU の定義そのものであり正解です。
• エ: 最も長い間主記憶にあったページを置き換える。
  解説：これは到着時刻（主記憶に入ってからの滞在時間）を基準にする FIFO（First-In First-Out）に相当します。LRU とは基準が異なるため誤りです。

よくある誤解

• 「参照フラグが使われている＝LRU」と思う誤解：参照フラグは簡易的な参照情報（最近参照されたか否か）を示すだけで、正確なLRUとは異なります。
• 「長く主記憶にある＝古い参照＝LRU」と混同する誤解：長く居た（到着が古い）ページを置換するのは FIFO 系であり、LRU の基準は「最後に参照された時刻」です。
• 「ランダムはLRUの一種」と考える誤解：ランダムは完全に確率的で参照履歴を参照しないため全く別の方式です。

補足コラム

• LRU の実装方法：正確な LRU を実装するには各ページの参照時刻を保持するか、スタック（連結リスト）で参照順を管理しますがハードウェア／オーバーヘッドが高く現実には近似法（参照ビットを用いた Second Chance / Clock アルゴリズム、カウンタを周期的に更新する方式など）が多用されます。
• LRU は理想（過去参照が未来参照を予測する）に基づく合理的戦略で、最適アルゴリズム OPT（未来を知る最良解）に近い性能を示すことがありますが、完全最適ではありません。
• 教科書的用語：NRU、FIFO、ランダム、LRU、Clock（Second Chance）などの違いを押さえておくと午前問題で速く解けます。

from collections import OrderedDict

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

    def get(self, key):
        if key not in self.cache:
            return -1
        # 最近使ったので末尾に移動
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            # 最も長く使われていないものを先頭から削除
            self.cache.popitem(last=False)

FAQ