ページ置換アルゴリズム（FIFO）

📌

FIFOとは

FIFOは First In First Out の略で、最初に主記憶へ読み込んだページから順に追い出すページ置換アルゴリズムです。ページ置換とは、フレーム（＝ページを置く主記憶の枠）が満杯のとき、どのページを追い出して新しいページを入れるかを決める仕組みのことです。

身近な例で考えると、食品の賞味期限管理に似ています。冷蔵庫に入れた順に手前から使い、古いものから先に消費していきますよね。読み込んだ順番だけで追い出すページを決めるのがFIFOの特徴です。

上のツールで▶ボタンを押すと、ページ参照列を1つずつ処理しながら、最も古く読み込んだページ（紫色の「最古」）が追い出され、累計ページフォールト数が増えていく様子を確認できます。

⚙️

アルゴリズムの仕組み

FIFOはページを読み込んだ順にキュー（＝先に入れたものが先に出る列）で管理します。新しく読み込んだページは列の末尾に並び、追い出すときは列の先頭（最も古いページ）から取り出します。

処理の流れは次のとおりです。
・ヒット時：参照したページがフレームにあれば何もしない（順番は変えない）
・フォールトで空きあり：補助記憶から読み込み、キューの末尾に並べる
・フォールトで満杯：キューの先頭（最も古く読み込んだページ）を追い出し、新しいページを末尾に並べる

注目したいのは、ヒットしても順番を変えない点です。LRUは「使った瞬間に最新扱い」にしますが、FIFOは「読み込んだ順」だけを見ます。そのため最近よく使うページでも、古ければそのまま追い出されてしまいます。実装は読込順を覚えるだけなのでとても単純です。上のツールで紫色の「最古」が次に追い出される候補だと確認してみてください。

⚖️

他方式との比較

FIFOは実装が簡単なのが最大の利点です。一方で、「最近よく使うページ」でも古ければ追い出してしまうという弱点があります。よく比較されるLRUは「最後に使った時刻」を見るので、よく使うページは残りやすくなります。

さらにFIFOには面白い性質があります。普通はフレーム数を増やせばページフォールトは減ると考えますが、FIFOではフレーム数を増やすとかえってフォールトが増えてしまうことがあります。これをベラディの異常（Belady's anomaly）と呼びます。LRUではこの異常は起こりません。上のツールでFIFOの総ページフォールト数を確認し、LRUページの結果と比べてみてください。

💡

なぜFIFOが使われるのか

FIFOが使われる理由は「実装がとても簡単で、追加の管理コストがほぼゼロ」だからです。読み込んだ順番をキューで覚えるだけでよく、「どのページをいつ使ったか」という情報を一切記録しなくていいのです。

なぜ管理コストが低いことが重要なのでしょうか。主記憶の管理はコンピュータの中で非常に頻繁に行われる処理です。そのため「賢いが重い」アルゴリズムより「多少精度が落ちても軽い」アルゴリズムが有利な場面が多くあります。
・FIFO：キューに「追加」「先頭から取り出す」の2操作だけ。余分なデータ不要
・LRU（＝最近最も使われていないページを追い出す方式）：全ページの「最後に使った時刻」を常に更新し続ける必要がある

つまり、「完璧ではないが速くて軽い」という実用上のバランスがFIFOの価値です。シンプルな仕組みだからこそ、学習の入り口として理解しやすく、ページ置換の基本を学ぶのにも最適なアルゴリズムです。

⚠️

ベラディの異常とはなにか

ベラディの異常（Beladyの異常）とは、フレーム数（＝ページを置く枠の数）を増やしたのに、ページフォールトがかえって増えてしまう現象のことです。FIFOでだけ起こります。

なぜこんな不思議な現象が起きるのか。FIFOは「読み込んだ順番」しか見ないため、フレームが増えると追い出される順番が変わり、たまたまよく使うページが残りにくい並びになってしまうことがあるからです。フレームを増やせばよいとは限らない、という反直感的な例として有名です。

LRUでは「最後に使った時刻」を基準にするため、フレームを増やせば必ず以前より多くの履歴が残せます。そのためLRUではベラディの異常は起こりません。「FIFOでだけ起こる」という点がポイントです。

🎯

基本情報技術者 練習問題