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

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

正解の理由

解法ステップ

1. フレーム数（空き枠）を4で初期化し、すべて空とする。
2. 各参照を時刻順に処理し、ヒットならそのページの最終使用時刻を更新、ミスなら最終使用時刻が最も古いページを置換して新ページを挿入する。
3. 最終的にページ6を参照する直前の各ページの最終使用時刻を比べ、最も古いものを置換候補とする。

• t1: 1 → [1:1]
• t2: 2 → [1:1, 2:2]
• t3: 3 → [1:1, 2:2, 3:3]
• t4: 4 → [1:1, 2:2, 3:3, 4:4]
• t5: 5 → ページフォルト。最終使用が最も古いのは1(=t1) → 1を置換 → [5:5, 2:2, 3:3, 4:4]
• t6: 2 → ヒット。2の最終使用を更新 → [5:5, 2:6, 3:3, 4:4]
• t7: 1 → ミス。最も古いのは3(=t3) → 3を置換 → [5:5, 2:6, 1:7, 4:4]
• t8: 3 → ミス。最も古いは4(=t4) → 4を置換 → [5:5, 2:6, 1:7, 3:8]
• t9: 2 → ヒット。2の最終使用を更新 → [5:5, 2:9, 1:7, 3:8]
• t10: 6 → ミス。最も古いのは5(=t5) → 5を置換して6を挿入

選択肢別の誤答解説

• ア: 1
  t5で最初に1は置換されますが、その後t7で再ロードされます。t10直前の最終使用時刻は t7 であり、5の方が古いため置換対象にはなりません。よって不正解。
• イ: 2
  ページ2はt9で直近に参照されており（最終使用時刻が最新）置換対象にはなりません。よって不正解。
• ウ: 4
  ページ4はt8で既に置換されており、t10時点ではメモリに存在していません（t8で3に置換）。したがって置換対象にはなり得ません。よって不正解。
• エ: 5
  t5以降5は再参照されておらず最も古い最終使用時刻（t5）のままです。したがってページ6参照時の置換対象はページ5であり、選択肢の中では エ が正しい。

よくある誤解

• 最終使用時刻を更新し忘れる：ヒット時にそのページの「最終使用時刻」を必ず更新しないと誤った置換対象を選んでしまいます。
• FIFOと混同する：LRUは「最も古く最後参照された時刻」を基準にするので、挿入順（FIFO）とは結果が異なる場合があります。
• フレームの並びをそのままLRU順と誤解する：フレームリストの物理的な並びは意味を持たないことがあり、判断はあくまで最終使用時刻で行います。

補足コラム

# LRUシミュレータ（教育用）
def lru_replace(accesses, frames_count):
    frames = {}  # page -> last_use_time
    time = 0
    for a in accesses:
        time += 1
        if a in frames:
            frames[a] = time
        else:
            if len(frames) < frames_count:
                frames[a] = time
            else:
                # 最小の最終使用時刻を持つページを削除
                lru_page = min(frames, key=lambda p: frames[p])
                del frames[lru_page]
                frames[a] = time
        print(f"t{time}: access {a} -> frames {frames}")
    return frames

accesses = [1,2,3,4,5,2,1,3,2,6]
lru_replace(accesses, 4)

FAQ