応用情報技術者 2012年 秋期 午前2 問19
問題文
仮想記憶管理におけるページ置換えアルゴリズムとして、LRU方式を採用する。参照かつ更新されるページ番号の順番が、1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 6, 5でページ枠が4のとき、ページフォールトに伴って発生するページアウトは何回か。ここで、初期状態では、いずれのページも読み込まれていないものとする。
選択肢
ア：3
イ：4（正解）
ウ：5
エ：6
🔒 解説は解答すると表示されます
LRUページ置換【午前2解説】
正解の理由
LRU（Least Recently Used）方式では、ページ枠が全て埋まっているときにページフォールトが起きると、最も長く参照されていないページを追い出します。本問のページは「参照かつ更新される」ので、追い出されるページは必ず書き戻され、ページアウトが発生します。参照列 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 6, 5 をページ枠4で追跡すると、ページアウトは4回発生するので、イが正解です。
解法ステップ
参照列: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 6, 5（ページ枠＝4、初期状態は空）
ページ枠の中身を、左が最も長く参照されていないページになるように並べて追跡します。
- 1 → [1]（フォールト、空き枠に読込み）
- 2 → [1, 2]（フォールト、空き枠に読込み）
- 3 → [1, 2, 3]（フォールト、空き枠に読込み）
- 4 → [1, 2, 3, 4]（フォールト、空き枠に読込み）
- 1 → [2, 3, 4, 1]（ヒット）
- 2 → [3, 4, 1, 2]（ヒット）
- 5 → [4, 1, 2, 5]（フォールト、3を追い出す → ページアウト1回目）
- 1 → [4, 2, 5, 1]（ヒット）
- 2 → [4, 5, 1, 2]（ヒット）
- 3 → [5, 1, 2, 3]（フォールト、4を追い出す → ページアウト2回目）
- 6 → [1, 2, 3, 6]（フォールト、5を追い出す → ページアウト3回目）
- 5 → [2, 3, 6, 5]（フォールト、1を追い出す → ページアウト4回目）
ページフォールトは8回ですが、最初の4回は空き枠への読込みでページアウトは発生しません。したがってページアウトは4回です。
選択肢別の誤答解説
- ア: 3 — 最後の参照（5）でのページアウトを数え漏らすと3回になります。
- イ: 4 — LRUで正しく追跡したときのページアウトの回数です。
- ウ: 5 — ヒットしたときに参照順を更新し忘れるなど、追跡を誤ると多くなります。
- エ: 6 — 空き枠への読込みの一部までページアウトと数えるなど、数え方を誤った場合の値です。
よくある誤解
- ページフォールトとページアウトを混同すること。ページフォールトは参照したページが主記憶にない事象で、ページアウトは追い出すページを補助記憶に書き戻す動作です。空き枠があるうちはページフォールトが起きてもページアウトは発生しません。
- ヒットしたときに参照順を更新し忘れること。LRUでは、ヒットしたページも「最も最近参照されたページ」になります。
補足コラム
全てのページが参照かつ更新される場合、初期状態が空なら「ページアウトの回数＝ページフォールトの回数－ページ枠数」になります（ページフォールトがページ枠数以上のとき）。本問では 8－4＝4 回です。
FAQ
Q: 参照されるだけで更新されないページでも、ページアウトは発生しますか？
A: 更新されていないページは補助記憶の内容と同じなので、書き戻さずに破棄できます。本問は「参照かつ更新される」ので、追い出すたびにページアウトが発生します。
A: 更新されていないページは補助記憶の内容と同じなので、書き戻さずに破棄できます。本問は「参照かつ更新される」ので、追い出すたびにページアウトが発生します。
Q: FIFO方式なら結果は変わりますか？
A: FIFO方式は最も早く読み込んだページを追い出すので、追い出すページが変わり、回数も変わることがあります。方式ごとに追跡し直す必要があります。
A: FIFO方式は最も早く読み込んだページを追い出すので、追い出すページが変わり、回数も変わることがあります。方式ごとに追跡し直す必要があります。
関連キーワード: 仮想記憶、ページ置換、LRU、ページアウト、ページフォールト
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！