FIFO方式とは？先に入ったページを先に置き換える方法【基本情報技術者試験】

まず結論

FIFO方式とは、ページ置換が必要になったときに、主記憶に先に入ったページから順に追い出す方式です。

FIFOは、First In First Out の略です。

基本情報技術者試験では、FIFO方式は 「先に入ったものを先に出す」ページ置換方式 と考えると判断しやすいです。

LRU方式と違って、ページが途中で参照されても、主記憶に入った順番は更新しない ところが重要です。

FIFO方式は、行列に並ぶイメージです。

先に並んだ人から順番に呼ばれるように、FIFO方式では、先に主記憶へ入ったページから順番に置き換えられます。

先に入ったページ → 先に出る
あとから入ったページ → あとで出る

例えば、ページ枠に次の順でページが入ったとします。

1 → 2 → 3 → 4

ページ枠がいっぱいの状態で新しいページ5を入れる必要がある場合、FIFO方式では、最初に入ったページ1を置き換えます。

ここで、途中でページ2やページ3が参照されても、FIFOでは「入った順番」だけを見ます。

仮想記憶では、プログラムが使うページの一部だけを主記憶に置きます。

主記憶のページ枠がいっぱいの状態で、主記憶にないページを読み込む必要があると、どれかのページを置き換える必要があります。

このとき、どのページを追い出すかを決める方法が、ページ置換アルゴリズムです。

FIFO方式では、ページ枠にページが入った順番を記録します。

ページ枠がいっぱいの状態で新しいページを入れるときは、最も古く主記憶に入ったページ を置き換えます。

このテーマは、基本情報技術者試験の「コンピュータシステム」や「オペレーティングシステム」と関係する内容です。公式の出題範囲やシラバスは、IPA：基本情報技術者試験から確認できます。

科目Aでは、FIFO方式の説明や、ページ参照列を使った計算問題として出題されやすいです。

判断するときは、次の表現を見ます。

表現	判断
最初に主記憶へ入ったページを置き換える	FIFO方式
先入れ先出し	FIFO方式
最後に参照されてから最も時間がたったページを置き換える	LRU方式
これから最も長く使われないページを置き換える	OPT方式
使用頻度が最も低いページを置き換える	LFU方式

特に、LRU方式との違いが大切です。

方式	見るもの	置き換えるページ
FIFO	主記憶に入った順番	最初に入ったページ
LRU	最後に参照された時刻	最近使われていないページ

FIFOでは、ページが参照されても、入った順番は変わりません。

LRUでは、ページが参照されると「最近使ったページ」として扱いが更新されます。

問題文では、ページ参照列を順に追って、ページ枠の中身を更新する問題でFIFO方式の考え方が役立ちます。

基本手順は次のとおりです。

例えば、ページ枠が3つで、次の順に参照するとします。

1, 2, 3, 2, 4

途中の状態を簡単に追うと、次のようになります。

この例では、途中でページ2を参照しています。

しかし、FIFO方式ではページ2を「最近使った」として順番更新しません。

ここがLRU方式との大きな違いです。

FIFO方式でよくある誤解は、途中で参照されたページを新しい扱いにしてしまうこと です。

特に、次の切り分けを覚えておくと強いです。

FIFO：入った順番を見る
LRU：最後に使った時刻を見る

FIFOでは、ページ枠にヒットしたときは「置換しない」だけです。

LRUのように、最近使ったページとして順番を並べ替える必要はありません。