基本情報技術者 2017年 春期 午前（科目A） 問19

ページ置換アルゴリズムの比較【午前解説】

正解の理由

解法ステップ

1. 問題の定義を確認：実記憶フレーム数 = 3、参照列 = 1,3,2,1,4,5,2,3,4,5、置換回数は「追い出し（eviction）の回数」か確認。
2. FIFO のシミュレーション：挿入順をキューとして管理し、参照ごとにフレーム内かを確認。満杯でミスならキューの先頭を追い出して新しいページを入れ、追い出し回数をカウント。
3. LRU のシミュレーション：最近参照された順（MRU）を更新して管理し、満杯でミスなら最も古く参照された（LRU）ページを追い出して新しいページを入れ、追い出し回数をカウント。
4. 両者の追い出し回数を比較して選択肢と照合する。

• FIFO は挿入順 [1,3,2] が中盤以降に 1→3→2 の順で追い出され、追い出しは合計 3 回。
• LRU は参照更新により最終的に頻繁に「もっとも古い」ページが入れ替わり続け、追い出しは合計 6 回。

選択肢別の誤答解説

• ア：FIFO = 3、LRU = 2
  • FIFO の 3 は正しいが、LRU = 2 は過小評価です。中盤以降のミス連続で少なくとも 6 回の追い出しが発生するため誤りです。
• イ：FIFO = 3、LRU = 6（正解）
  • FIFO は挿入順管理により追い出し 3 回、LRU は参照で再配置するため追い出し 6 回になります。
• ウ：FIFO = 4、LRU = 3
  • FIFO の 4 はシミュレーションと合わず過大評価、LRU の 3 は過小評価です。どちらも参照の順序変化を正確に追えていません。
• エ：FIFO = 5、LRU = 4
  • 両方とも過大評価／過小評価が混在しており、実際の逐次シミュレーション結果とは一致しません。特に FIFO の 5 は明らかに多すぎます。

よくある誤解

• 「ページフォールト＝置き換え回数」と考える誤り：空フレームに初回ロードされるときのフォールトは置き換え（追い出し）には含めない問題設定が多く、問題文の意図を確認する必要があります。
• 「ヒットで順序が変わるのは FIFO だ」と勘違いする人がいる：ヒット時に参照順を更新するのは LRU であり、FIFO はヒットでも挿入順を変えません。
• 参照履歴を追わずに直感で判断する：短い列でも挿入順や最終参照順が複雑に絡むため、必ずステップごとに状態を追うことが必要です。

補足コラム

• Belady の異常（Belady's anomaly）：FIFO はフレーム数を増やしてもページフォールトが増える場合があり得る（Belady の異常）。一方、LRU はスタック制約を満たすためそのような異常は起きません。本問はフレーム数固定の比較問題であり、異常の有無を尋ねるものではありませんが、アルゴリズムの性質を理解する上で重要な概念です。
• 「置換回数」に関しては、問題によっては初期ロードもカウントする場合があるため、設問文や採点基準に合わせて扱いを確認してください。本問は「追い出すページを選ぶアルゴリズム」であるため、実質的に追い出しの回数を数えます。

FAQ