応用情報技術者 2019年 春期 午前2 問19
問題文
仮想記憶管理におけるページ置換えアルゴリズムとしてLRU方式を採用する。主記憶のページ枠が、4000, 5000, 6000, 7000番地(いずれも16進数)の4ページ分で、プログラムが参照するページ番号の順が、1 → 2 → 3 → 4 → 2 → 5 → 3 → 1 → 6 → 5 → 4のとき、最後の参照ページ4は何番地にページインされているか。ここで、最初の 1 → 2 → 3 → 4の参照で、それぞれのページは4000, 5000, 6000, 7000番地にページインされるものとする。
選択肢
ア：4000
イ：5000
ウ：6000（正解）
エ：7000
仮想記憶管理のLRUページ置換え問題【午前2 解説】
要点まとめ
- 結論：最後に参照されたページ4は、6000番地にページインされています。
- 根拠：LRU方式は最も長く使われていないページを置換えるため、ページの参照履歴を正確に追う必要があります。
- 差がつくポイント：ページ番号とページ枠の対応を正確に管理し、置換えタイミングを見誤らないことが重要です。
正解の理由
問題の初期状態でページ1～4はそれぞれ4000～7000番地に割り当てられています。参照順にLRUでページ置換えを行うと、最後のページ4は元の6000番地の枠に再度ページインされます。これは、ページ4が置換えられた後、再度参照された際に空いた6000番地の枠に戻るためです。
よくある誤解
ページ番号とページ枠の対応を固定と誤解し、置換え後のページ枠の変動を考慮しないことが多いです。LRUは参照履歴に基づくため、単純な番号順ではありません。
解法ステップ
- 初期状態でページ1～4を4000～7000番地にページインする。
- 参照順にページ番号を追い、ページヒットかミスかを判定する。
- ページミス時はLRUで最も古いページを置換え、対応するページ枠を更新する。
- 最後のページ4の参照時点で、どのページ枠にページ4があるかを確認する。
選択肢別の誤答解説
- ア: 4000
ページ1が最初に割り当てられた枠ですが、LRUで置換えられているため最後はここにページ4はありません。 - イ: 5000
ページ2の枠ですが、途中で置換えられており最後のページ4はここにありません。 - ウ: 6000
ページ3の枠で、最後のページ4が再度ここにページインされるため正解です。 - エ: 7000
ページ4の初期枠ですが、置換えにより一時的に空きます。最後は6000番地に戻るため誤りです。
補足コラム
LRU（Least Recently Used）方式は、最も長く使われていないページを置換えるアルゴリズムで、実装には参照履歴の管理が必要です。ページ枠の物理アドレスは固定ではなく、置換えにより動的に変わるため、ページ番号と枠の対応を正確に追うことが重要です。
FAQ
Q: LRU方式でページ枠の物理アドレスは固定ですか？
A: いいえ、ページ枠は物理メモリの位置であり、ページ置換えにより割り当てが変わります。
A: いいえ、ページ枠は物理メモリの位置であり、ページ置換えにより割り当てが変わります。
Q: ページ番号とページ枠の対応は常に一定ですか？
A: いいえ、ページ置換えによりページ番号は異なる枠に割り当てられることがあります。
A: いいえ、ページ置換えによりページ番号は異なる枠に割り当てられることがあります。
関連キーワード: 仮想記憶、LRU, ページ置換え、ページフォールト、メモリ管理
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！