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

仮想記憶管理のページ入替え方式（最後に使われてからの経過時間が最も長いページを入れ替えるものはどれか）【午前2 解説】

要点まとめ

• 結論→ 最後に使われてからの経過時間が最も長いページを入れ替える方式は LRU（Least Recently Used）であり正解は エ です。
• 根拠→ 「最後に使われてからの経過時間」が示すのは“最近の使用の新しさ（recency）”で、LRUはこれを基準に置換を行います。
• 差がつくポイント→ FIFO は投入順、LFU は使用頻度、LIFO は直近投入を優先する点を混同しないことが高得点の鍵です。

正解の理由

よくある誤解

• FIFO と混同してしまう：FIFO は「最初に入った（oldest loaded）ページ」を追い出す方式で、使用の最近性（最後に参照された時間）を見ているわけではありません。
• LFU と誤認する：LFU は「参照回数（frequency）」が最小のページを外す方式で、直近に使われたかどうかは関係ありません。
• LRU が常に最良だと思い込む：LRU は現実的かつ優れた方式ですが、最適（未来を知る OPT）ではなく、実装コストや特定のワークロードでの挙動に注意が必要です。

解法ステップ

1. 問題文からキーワードを拾う：「最後に使われてからの経過時間」→「最後に参照された時刻（recency）」。
2. 各方式の定義を確認：FIFO（投入順）、LFU（参照回数）、LIFO（最終投入順）、LRU（最終参照時刻）。
3. 「recency」に対応する方式は LRU であると判断する。
4. 選択肢から エ を選ぶ。

選択肢別の誤答解説

• ア: FIFO — ページをメモリに入れた順序（先入れ）で追い出す方式。参照の「最後の使用時刻」は考慮しません。
• イ: LFU — 一定期間内や累積で参照回数が最も少ないページを置換します。頻度（frequency）基準であり「最終使用からの経過時間」は対象にしません。
• ウ: LIFO — スタックのように「最後に入れた（または最後に使った）ものを先に出す」方式で、問題文の条件とは逆の概念です。実運用ではほとんど使われません。
• エ: LRU — 最後に使われてからの経過時間（recency）が最も長いページを置換する方式で、設問の定義に完全に一致します。

補足コラム

• 実装上の工夫：完全な LRU を高速に実装するにはコストが高く、参照ビットや CLOCK アルゴリズム、エイジング（aging）などで近似することが多いです。
• スタックアルゴリズム性：LRU はスタックアルゴリズムの一種で、メモリフレーム数を増やしてもページフォールト数が減少する性質（包含性）を持ち、Belady の異常を起こしません。対して FIFO は Belady の異常を起こす場合があります。
• 実際の OS では：完全な LRU はコスト面で不利なため、近似手法（Clock、2nd-chance、LRU-K 等）が用いられます。

FAQ