基本情報技術者試験「ページ置換アルゴリズム」の問題
主記憶に割り当てられたページ枠が3つあり、最初は全て空である。ページ参照が 1,2,3,4,1,2,5,1,2 の順で発生したとき、FIFO(先入れ先出し)方式での置換を行うと、発生するページフォルトは合計何回か。
ア7回発生する
イ5回
ウ全部で6回となる
エ9回すべてフォルト
正解
ア．7回発生する
FIFOは最も先に入ったページを追い出す。参照を順に追うと1F2F3F(枠満杯)、4で最古の1を追出しF、続く1で最古の2を追出しF、2で3を追出しF、5でF、最後の1・2はヒット。フォルトは7回で正しい。
?選択肢ごとの解説
ア ○FIFOは最も先に入ったページを追い出す。参照を順に追うと1F2F3F(枠満杯)、4で最古の1を追出しF、続く1で最古の2を追出しF、2で3を追出しF、5でF、最後の1・2はヒット。フォルトは7回で正しい。
イ ×5回は再フォルトとなる中盤の1・2の置換を見落とし、初回3回と一部のみ数えた過少な値である。
ウ ×全部で6回は4・5の置換のいずれか1回を数え漏らした誤りで、追い出した古いページが直後に再参照される様子を追えていない。
エ ×9回すべてフォルトは末尾の1・2がヒットすることを見落とし、全参照をミスと数えた誤りである。
✎くわしく
FIFOは実装が単純だが参照局所性を考慮しないため、追い出した直後のページを再参照すると無駄なフォルトを招く。枠数を増やすとフォルトが増えるベラディの異常が起こりうる点もFIFO特有の欠点である。
✓本番での押さえどころ
試験のコツ
枠の中身を表で更新しながら、参照ごとにヒットかフォルトかを記録する。FIFOは『入った順』のみで追い出し対象を決める。
覚え方
FIFO=『行列の先頭から退場』。一番古く並んだ人(ページ)が真っ先に出される、と覚える。
よくある誤り
追い出すページを『最も古く入った』ではなく『最後に使われたのが古い』(これはLRU)と取り違える、再フォルトを数え漏らす誤りが多い。
コンピュータ構成要素の他の問題
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-a3-0161