応用情報技術者 2023年 春期 午前2 問17
問題文
仮想記憶システムにおいて、ページ置換えアルゴリズムとしてFIFOを採用して仮想ページ参照列1, 4, 2, 4, 1, 3を3ページ枠の実記憶に割り当てて処理を行った。表の割当てステップ“3”までは、仮想ページ参照列中の最初の142をそれぞれ実記憶に割り当てた直後の実記憶ページの状態を示している。残りを全て参照した直後の実記憶ページの状態を示す太枠部分に該当するものはどれか。
選択肢
ア：
イ：
ウ：（正解）
エ：
仮想記憶システムのFIFOページ置換え【午前2 解説】
要点まとめ
- 結論：FIFOアルゴリズムでは最も古くから実記憶にあるページを順に置換え、最終的なページ状態は「3, 4, 2」となる。
- 根拠：初期3ページ枠に「1, 4, 2」を割り当て、その後の参照でFIFOの順にページを置換えながら状態を更新するため。
- 差がつくポイント：ページ置換えの順序を正確に追い、ページフォールトの発生と置換え対象を見極めることが重要。
正解の理由
FIFO（First In First Out）方式は、最も先に実記憶に割り当てられたページから順に置換えます。
ステップ3までに「1, 4, 2」が実記憶にあり、ステップ4で「4」を参照しますが既に存在するため置換えなし。
ステップ5で「1」を参照、これも実記憶にあるため置換えなし。
ステップ6で「3」を参照し、実記憶にないため最も古い「1」を置換えます。
結果、実記憶は「3, 4, 2」となり、選択肢の中でウがこれに該当します。
ステップ3までに「1, 4, 2」が実記憶にあり、ステップ4で「4」を参照しますが既に存在するため置換えなし。
ステップ5で「1」を参照、これも実記憶にあるため置換えなし。
ステップ6で「3」を参照し、実記憶にないため最も古い「1」を置換えます。
結果、実記憶は「3, 4, 2」となり、選択肢の中でウがこれに該当します。
よくある誤解
FIFOは最も古いページを置換えるため、最近参照されたページを優先するLRUとは異なります。
ページが存在している場合は置換えが発生しないことを忘れがちです。
ページが存在している場合は置換えが発生しないことを忘れがちです。
解法ステップ
- ステップ1〜3で「1, 4, 2」を実記憶に割り当てる。
- ステップ4で「4」を参照、既に実記憶にあるため状態変化なし。
- ステップ5で「1」を参照、同様に状態変化なし。
- ステップ6で「3」を参照、実記憶にないため最も古い「1」を置換え。
- 最終状態は「3, 4, 2」となる。
選択肢別の誤答解説
- ア：「1, 3, 4」は「3」が最後に入ったが「2」が置換えられておりFIFOの順序と異なる。
- イ：「1, 4, 3」は「1」が置換えられていないため誤り。
- ウ：「3, 4, 2」はFIFOの置換え順序に合致し正解。
- エ：「4, 1, 3」は「1」が置換えられていないため誤り。
補足コラム
FIFOは実装が簡単で理解しやすい反面、Beladyの異常（ページ枠増加でページフォールトが増える現象）が起こることがあります。
LRUや最適置換えアルゴリズムと比較して性能が劣る場合もあるため、用途に応じて使い分けが必要です。
LRUや最適置換えアルゴリズムと比較して性能が劣る場合もあるため、用途に応じて使い分けが必要です。
FAQ
Q: FIFOとLRUの違いは何ですか？
A: FIFOは最も古くからあるページを置換え、LRUは最も長く参照されていないページを置換えます。
A: FIFOは最も古くからあるページを置換え、LRUは最も長く参照されていないページを置換えます。
Q: ページフォールトが起きたら必ず置換えが必要ですか？
A: ページフォールト時に空き枠があれば置換えは不要で、新規割当てのみ行います。
A: ページフォールト時に空き枠があれば置換えは不要で、新規割当てのみ行います。
関連キーワード: 仮想記憶、ページ置換え、FIFO, ページフォールト、メモリ管理
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！