エンベデッドシステムスペシャリスト 2013年午前2 問07

問題文

仮想記憶システムにおいて、ページ置換えアルゴリズムとしてFIFOを採用して、仮想ページ参照列1、4、2、4、1、3を3ページ枠の実記憶に割り当てて処理を行った。表の割当てステップ“3”までは、仮想ページ参照列中の最初の1、4、2をそれぞれ実記憶に割り当てた直後の実記憶ページの状態を示している。残りを全て参照した直後の実記憶ページの状態を示す太枠部分に該当するものはどれか。

🖊️ 解答を隠して解いてみる

選択肢

ア：

イ：

ウ：（正解）

エ：

🔒 解説は解答すると表示されます

FIFOページ置換え【午前2解説】

正解の理由

参照列は 1、4、2、4、1、3 です。最初の3ページ（1、4、2）を実記憶に格納した後、ページ4とページ1はすでに実記憶にあるため、実記憶の状態は変わりません。

最後にページ3を参照すると、実記憶にページ3がないためページ置換えが発生します。FIFOでは、最も早く実記憶に格納されたページを置き換えます。最初に格納されたページ1をページ3に置き換えるので、最終状態は左から 3、4、2 です。したがって、該当するのはウです。

解法ステップ

ステップ1〜3：最初の3ページを格納します。
ページ1、4、2の順に格納され、実記憶の状態は左から「1、4、2」です。FIFOの格納順も「1 → 4 → 2」です。
ステップ4：ページ4を参照します。
ページ4は実記憶にあるため、ページ置換えは発生しません。状態は「1、4、2」のままです。
ステップ5：ページ1を参照します。
ページ1も実記憶にあるため、状態は「1、4、2」のままです。
ステップ6：ページ3を参照します。
ページ3は実記憶にありません。FIFOでは最も早く格納されたページ1を置き換えるため、状態は「3、4、2」になります。

選択肢別の誤答解説

ア（1、3、4）：ページ1が残り、ページ2がなくなっています。FIFOで置き換えるべき最古のページはページ1なので、この状態にはなりません。
イ（1、4、3）：ページ2が置き換わり、ページ1が残っています。ページ2はページ1より後に格納されたため、FIFOの置換対象ではありません。
ウ（3、4、2）：最も早く格納されたページ1がページ3に置き換わった状態です。
エ（4、1、3）：ページ3への置換えは行われていますが、ページ2ではなくページ1が置き換わった状態になっていません。また、実記憶の枠の順序も問題の割当てに沿っていません。

よくある誤解

ページを参照した順にFIFOの順番も変わると思うこと
FIFOで管理するのはページの格納順です。ページを再参照しても、格納順は変わりません。
実記憶にあるページを参照したときも置換えると思うこと
ページ4やページ1のように、参照したページがすでに実記憶にあればページ置換えは発生しません。
最後に参照されたページを置き換えると思うこと
FIFOが置き換えるのは最も早く格納されたページです。最後に参照したページではありません。

補足コラム

FIFOは「First In, First Out」の略で、最初に格納されたページを最初に追い出す方式です。参照頻度や直近の使用状況は考慮しません。そのため、何度も参照されたページでも、格納時期が最も古ければ置換えの対象になることがあります。

FAQ

Q. ページ4を再参照したとき、FIFOの順番はどうなりますか？
A. 変わりません。FIFOの順番はページを実記憶に格納した順で決まり、再参照では更新されません。

Q. この問題では、どのページを置き換えるかだけ分かれば解けますか？
A. はい。最初の格納順が「1、4、2」で、ページ4とページ1の参照では状態が変わらないため、ページ3の参照時に最古のページ1を置き換えると判断できます。

関連キーワード: FIFO、ページ置換え、仮想記憶、実記憶、ページフォールト

← 前の問題へこの年度をクイズで解く次の問題へ →

\ せっかくなら /

エンベデッドシステムスペシャリストを
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！