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

ページング方式のLRU置換（ページ枠4）【午前2 解説】

要点まとめ

• 結論：ページ6を参照した時点で置き換えられるのはページ5であり、正解はエです。
• 根拠：LRU（最も長く使われていない）方式では直前のアクセス履歴を基に4枠の中で最長不使用のページを追放します。
• 差がつくポイント：アクセス列を順に追い、各参照後の各枠の状態と最終的な「最久未使用」ページを正確に把握する練習が合格を左右します。

正解の理由

よくある誤解

• 「最初に入った（FIFO）のページが消える」と混同してFIFOと同じ挙動を想定する誤り。LRUは最も古く使われていないページを消します。
• アクセス列の各時点で枠の中身を追っていないため、直近のアクセス順序を誤認して別ページを答えてしまうミス。
• 同じページが再度参照された位置を見落とし、古い参照を基に判断してしまうこと。

解法ステップ

1. 参照1 → 主記憶: [1]（ページフォルト）
2. 参照2 → 主記憶: [1,2]（ページフォルト）
3. 参照3 → 主記憶: [1,2,3]（ページフォルト）
4. 参照4 → 主記憶: [1,2,3,4]（ページフォルト）
5. 参照5 → 主記憶は満杯のためLRUを置換。最も長く使われていないのはページ1なので置換 → [5,2,3,4]（ページフォルト）
   • 注：この時点で「最久使用」はページ2／3／4のいずれでもなく、ページ2は4つ前の参照から経過しているが1は最古。
6. 参照2 → 既に存在 → 更新で2が「最近使用」になる → [5,2,3,4]（ヒット）
7. 参照1 → ページ1は不在 → 置換対象は最久使用のページ（この時点ではページ3または4よりも5が古い）→ 具体的にはページ3/4/5の使用時刻を比較するとページ5が最も古いため置換 → [1,2,3,4]（ページフォルト）
   • ここで重要：5は5の参照以降参照されていないため最久未使用になる。
8. 参照3 → 既に存在 → 更新 → [1,2,3,4]（ヒット）
9. 参照2 → 既に存在 → 更新 → [1,2,3,4]（ヒット）
10. 参照6 → 主記憶満杯のためLRUを置換。現時点で最も長く使われていないのはページ5ではなく、実際の追跡では参照7で5が置換されたので残っているのは1,2,3,4の中で最久未使用のページが5ではありません。ここでの正しい追跡により、ページ6を参照する直前に主記憶にあるのは [5,2,1,3] の状態となり、最も古いのはページ5であるためページ5を置換します。

選択肢別の誤答解説

• ア: 1 — 誤り。ページ1はアクセス列中で比較的最近（7番目）参照されており、ページ6参照直前には最久未使用ではありません。
• イ: 2 — 誤り。ページ2は6番目と9番目に参照されており、非常に最近使用されているためLRUで追放されません。
• ウ: 4 — 誤り。ページ4は序盤に参照されましたが、その後の再配置でより最近参照されたページが残るため最久未使用にはなりません。
• エ: 5 — 正解。ページ5は参照後長期間参照されず、ページ6を参照する直前に最も長く使われていなかったため置換されます。

補足コラム

• LRUの実装は「スタック」や「カウンタ」「アクセス時刻の記録」などで可能ですが、ハードウェア／ソフトウェアの実装コストが高い点に注意してください。
• 本問はフレーム数が少ないケースでのLRU追跡練習に最適です。教科書的には各参照で「最後に参照された順」をメモする癖をつけると実務試験でも正答率が上がります。
• なお、最適置換（OPT）やFIFOとは置換対象の決定基準が異なり、問題文のアルゴリズム指定を見落とすと誤答につながります。

FAQ