応用情報技術者 2012年 秋期 午前2 問19
問題文
仮想記憶管理におけるページ置換えアルゴリズムとして、LRU 方式を採用する。参照かつ更新されるページ番号の順番が、1,2,3,4,1,2,5,1,2,3,65でページ枠が 4のとき、ページフォールトに伴って発生するページアウトは何回か。ここで、初期状態では、いずれのページも読み込まれていないものとする。
選択肢
ア：3
イ：4（正解）
ウ：5
エ：6
仮想記憶管理のLRUページ置換えアルゴリズム【午前2 解説】
要点まとめ
- 結論：ページ枠4でLRU方式を適用すると、ページアウトは4回発生します。
- 根拠：LRUは最も長く参照されていないページを置換え、ページフォールト時にページアウトが発生します。
- 差がつくポイント：ページアウトの発生回数はページフォールトのタイミングと置換え対象の正確な把握が鍵です。
正解の理由
選択肢イ（4回）が正解です。ページ枠4に対し、参照列1,2,3,4で最初の4ページが読み込まれますが、5番目のページ5参照時に初めてページアウトが発生します。以降、3回のページアウトが発生し、合計4回となります。LRUは最も長く使われていないページを置換えるため、正確に追跡することでページアウト回数が導けます。
よくある誤解
ページフォールト回数とページアウト回数を混同しやすい点に注意が必要です。ページアウトはページフォールト時に置換えが発生した場合のみ起こります。
解法ステップ
- ページ枠4に対し、参照列を順に読み込む。
- ページフォールトが起きたら、LRUの最も古いページを特定。
- 置換えが必要な場合はページアウトが発生する。
- 参照列全体を通してページアウト回数をカウント。
- 最終的にページアウト回数を選択肢と照合。
選択肢別の誤答解説
- ア（3回）：ページアウト回数を過小評価。5番目のページ参照時の置換えを見落とし。
- イ（4回）：正解。LRUの動作を正確に反映。
- ウ（5回）：ページアウト回数を過大評価。不要な置換えをカウント。
- エ（6回）：ページアウト回数をさらに過大評価し、誤った置換え判断をしている。
補足コラム
LRU（Least Recently Used）は仮想記憶管理で広く使われるページ置換えアルゴリズムです。実装にはスタックやカウンタ方式があり、理想的なLRUはハードウェア支援がないと高コストになるため、近似アルゴリズムも存在します。
FAQ
Q: ページアウトとページフォールトは同じですか？
A: いいえ。ページフォールトはページがメモリにない状態で参照されたこと、ページアウトは置換え時にメモリからページを追い出すことです。
A: いいえ。ページフォールトはページがメモリにない状態で参照されたこと、ページアウトは置換え時にメモリからページを追い出すことです。
Q: LRU方式はどのように最も古いページを特定しますか？
A: 直近で最も長く参照されていないページを追跡し、置換え対象とします。
A: 直近で最も長く参照されていないページを追跡し、置換え対象とします。
関連キーワード: 仮想記憶、ページ置換え、LRU, ページフォールト、ページアウト、メモリ管理
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！