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

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

正解の理由

解法ステップ

1. 初期は空（枠数 = 4）。アクセスを順に処理し、ヒットなら最終参照時刻を更新、ミスなら最も古いページを置換します。
2. 各アクセスごとのフレーム状態（参照時刻の古い順を明示）を求めると理解しやすいです。以下に時刻 t=1..10 を対応させて示します。
3. アクセス列とフレーム更新（時刻順）:
   • t1: 1 → [1]
   • t2: 2 → [1,2]
   • t3: 3 → [1,2,3]
   • t4: 4 → [1,2,3,4]
   • t5: 5 → 置換(最も古い = 1) → [5,2,3,4]
   • t6: 2 → ヒット（2の時刻更新） → [5,2,3,4]
   • t7: 1 → ミス、置換(最も古い = 3) → [5,2,1,4]
   • t8: 3 → ミス、置換(最も古い = 4) → [5,2,1,3]
   • t9: 2 → ヒット（2の時刻更新） → [5,2,1,3]
   • t10: 6 → ミス、置換(最も古い = 5) → [6,2,1,3]
4. よって t10（ページ6アクセス時）に置換されるのはページ5、すなわち選択肢エです。

選択肢別の誤答解説

• ア: 1 — 初期ロード直後に置換されたが、その後再度ロードされており t7 に参照されているため t10 時点では最古ではありません。
• イ: 2 — ページ2 はアクセス t9 で最近参照されており、最終参照時刻が新しいため置換対象になりません。
• ウ: 4 — ページ4 は t8 より前に既に置換されており、t10 の時点では主記憶に存在しません（したがって置換候補にもならない）。
• エ: 5 — 正解。最後に参照されたのは t5 で、その後は参照がなく t10 時点で最も古い参照時刻のため置換されます。

よくある誤解

• 「出現回数で判断する」誤解: 参照回数が少ないページが置換されるとは限らず、LRU は最終参照時刻を基準にする点を見落としがちです。
• 「初期ロード順がそのまま残る」誤解: ヒット時に参照時刻が更新されるため、初期にロードされた順序だけで置換候補を決めてはいけません。
• 「FIFO と混同」: FIFO と LRU は異なり、FIFO は最初に入れたページを置換するため結果が異なる場合があります（Belady の異常が起こることもあるが、LRU はスタックアルゴリズムで回避されます）。

補足コラム

• LRU は「スタックアルゴリズム」に属し、フレーム数を増やすと必ずミス数が減る（Belady の異常が起きない）性質があります。
• 実装方法としては各ページにタイムスタンプを付ける方法や、参照順を保持する双方向リスト＋ハッシュでの実装、または近似アルゴリズムとして CLOCK（Second Chance）法がよく使われます。
• 試験で素早く処理するコツは「最新アクセス順を追う」こと。ヒット時にそのページを最も新しい扱いにするのを忘れないでください。

FAQ