応用情報技術者 2011年 春期 午前2 問21
問題文
仮想記憶方式のコンピュータにおいて、実記憶に割り当てられるページ数は3とし、追い出すページを選ぶアルゴリズムは、FIFOとLRUの二つを考える。あるタスクのページのアクセス順序が
1, 3, 2, 1, 4, 5, 2, 3, 4, 5
のとき、ページを置き換える回数の組合せとして適切なものはどれか。
選択肢
ア：
イ：（正解）
ウ：
エ：
仮想記憶のページ置換アルゴリズム【午前2 解説】
要点まとめ
- 結論：ページ置換回数はFIFOが3回、LRUが6回となり、正解はイです。
- 根拠：実記憶3ページに対し、アクセス順序に基づきFIFOとLRUでページフォールトを計算しました。
- 差がつくポイント：LRUは直近使用されていないページを追い出すため、アクセスパターンによってはFIFOより置換回数が増えることもあります。
正解の理由
FIFOは最も古くから存在するページを追い出す単純な方式で、今回のアクセス順序では3回のページ置換が発生します。一方、LRUは最も長く使われていないページを追い出すため、アクセスパターンによっては置換回数が増え、今回のケースでは6回となります。選択肢イの「FIFO: 3、LRU: 6」がこれに該当するため正解です。
よくある誤解
FIFOは単純だから常に置換回数が多いと思いがちですが、アクセスパターンによってはLRUの方が多くなることもあります。LRUが必ず優れているわけではありません。
解法ステップ
- 実記憶のページ数（3ページ）を確認する。
- アクセス順序（1, 3, 2, 1, 4, 5, 2, 3, 4, 5）を順に処理する。
- FIFO方式でページフォールトが起きるたびに最も古いページを追い出し、置換回数をカウント。
- LRU方式でページフォールトが起きるたびに最も長く使われていないページを追い出し、置換回数をカウント。
- 両方式の置換回数を比較し、選択肢と照合する。
選択肢別の誤答解説
- ア（FIFO:3、LRU:2）：LRUの置換回数が少なすぎて誤り。実際は6回。
- イ（FIFO:3、LRU:6）：正解。計算通りの置換回数。
- ウ（FIFO:4、LRU:3）：FIFOの置換回数が多すぎ、LRUが少なすぎ。
- エ（FIFO:5、LRU:4）：両方とも実際より多い。
補足コラム
ページ置換アルゴリズムは仮想記憶管理の基本で、性能に大きく影響します。FIFOは実装が簡単ですが、Beladyの逆説のように必ずしも最適ではありません。LRUは理論的に優れていますが、実装コストが高い場合があります。
FAQ
Q: FIFOとLRUの違いは何ですか？
A: FIFOは最も古くからあるページを追い出し、LRUは最も長く使われていないページを追い出します。
A: FIFOは最も古くからあるページを追い出し、LRUは最も長く使われていないページを追い出します。
Q: なぜLRUの置換回数が多くなることがあるのですか？
A: アクセスパターンによっては、直近使われていないページが頻繁に変わり、LRUが頻繁に置換を行うためです。
A: アクセスパターンによっては、直近使われていないページが頻繁に変わり、LRUが頻繁に置換を行うためです。
関連キーワード: 仮想記憶、ページ置換、FIFO, LRU, ページフォールト、メモリ管理
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！