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

LRUページ置換アルゴリズム【午前解説】

正解の理由

解法ステップ

1. 問題文からキーワードを抽出：「LRU」「ページ置換」「判断基準」→ 最近性を問う問題と認識。
2. 各選択肢を「最近性」「頻度」「初回参照」に分類する。
3. LRUは「最近性（最後に参照した時刻）」を使うアルゴリズムと即断する。
4. 正答として ア を選択する。試験ではキーワード一致が最も確実です。

選択肢別の誤答解説

• ア：正解。最後に参照した時刻（または直近の参照履歴）で最も古いページを置換するのがLRUの本質です。
• イ：最初に参照した時刻はページの導入順や生存期間を示すだけで、最近性の評価には用いません。FIFO（先入れ先出し）では導入順が関係しますが、これは最初参照時刻と単純には一致しません。
• ウ：単位時間当たりの参照頻度は「最近の頻度」を測る指標で、LFU（Least Frequently Used）や頻度ベースの手法に関係します。LRUは頻度を直接使いません。
• エ：累積の参照回数もLFU的な基準であり、長期的なアクセス回数が少ないページを置換する方針です。LRUとは評価軸が異なります。

よくある誤解

• 「参照回数が少ない＝LRUの置換対象」と誤認する：参照回数（累積や単位時間当たりの頻度）はLFUや頻度ベースの手法の基準です。
• 「最初に参照した時刻が古い＝LRU」と混同する：初回参照時刻はそのページの生存期間を示すだけで、最近性評価には使わないことが多いです。
• 実装方式（タイムスタンプ vs リスト）を混同して、挙動の定義を誤る：実装は複数ありますが、判断基準は常に「最近使われたか否か」です。

補足コラム

• 双方向連結リスト＋ハッシュ（参照でノードを先頭へ移動）…O(1)で更新可能。
• タイムスタンプ（アクセス時に現在時刻を記録）…比較は簡単だが更新コストや精度に注意。
• 時計（Clock）アルゴリズム…LRUの近似で実装コストを下げる方法。
  参考としてPythonのcollections.OrderedDictを使った簡易LRU例を示します。

from collections import OrderedDict

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

    def access(self, key, value=None):
        # アクセスがあれば最新に移動
        if key in self.cache:
            self.cache.move_to_end(key)  # 末尾を最新とする
        else:
            if len(self.cache) >= self.cap:
                self.cache.popitem(last=False)  # 先頭（最も古い）を削除
            self.cache[key] = value

FAQ