FIFO（置換アルゴリズム）とは？
FIFO（置換アルゴリズム）とは、FIFO（First In First Out：先入れ先出し）による置換アルゴリズムは、主記憶（メモリ）やキャッシュメモリに空きが無く、新しいデータを入れるために何かを追い出すとき、いちばん先に読み込んだものから追い出す方式。仮想記憶のページング方式（プログラムを「ページ」という一定の大きさに区切り、必要なページだけを主記憶に読み込む方式）では、必要なページが主記憶に無いこと（ページフォールト）が起きるたびに、どのページを追い出すかを決める必要があり、その決め方の1つがFIFOである。よく比べられるのは、最後に使われてから最も時間がたったページを追い出すLRU（Least Recently Used）と、使われた回数が最も少ないページを追い出すLFU（Least Frequently Used）。FIFOは読み込んだ順番だけを覚えておけばよく仕組みが単純だが、よく使うページでも古ければ追い出してしまう。試験では、ページを参照する順番と主記憶の枠の数が与えられ、ページフォールトの回数を数える問題が出る。
最終更新：2026-10-09
この語が出る過去問を解く →背景
主記憶は補助記憶より小さいため、プログラムのすべてのページを置いておけない。新しいページを読み込むたびに何かを追い出す必要があり、「どれを追い出せば後で困らないか」を決める規則が要った。理想は「この先いちばん長く使わないもの」を追い出すことだが、未来は分からない。そこで、手元ですぐ分かる「来た順」で決める単純な規則として使われてきた。
具体例
主記憶の枠が3つ、ページを参照する順番が 1, 2, 3, 1, 4, 2 のとき、FIFOで1つずつ追う。 1：枠に1を読み込む（フォールト）→ [1] 2：2を読み込む（フォールト）→ [1, 2] 3：3を読み込む（フォールト）→ [1, 2, 3] 1：枠にあるのでそのまま → [1, 2, 3] 4：空きが無い。最初に読み込んだ1を追い出す（フォールト）→ [2, 3, 4] 2：枠にあるのでそのまま → [2, 3, 4] フォールトは4回。直前に使ったばかりの1が追い出されている点がFIFOらしさである。LRUなら直前に使った1は残し、いちばん長く使われていない2を追い出すので、最後の2の参照でもう1回フォールトが起き、5回になる。どちらが少なくなるかは参照の順番で変わる。
試験での引っ掛け
FIFOが見るのは「主記憶に読み込んだ順番」であり、「最後に使った時刻」ではない。読み込んだ後に何度参照されても順番は入れ替わらない（使うたびに順番を入れ替えるのはLRU）。また、FIFOでは主記憶の枠を増やすと、かえってページフォールトが増える場合がある（Beladyの異常と呼ばれる）。参照の順番が 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 のとき、枠3つでは9回、枠4つでは10回になる。「枠を増やせば必ず減る」は誤り。
関連用語
出た過去問
出典：平成29年度 春期 基本情報技術者試験 午前 問19（IPA）
仮想記憶方式のコンピュータにおいて，実記憶に割り当てられるページ数は3とし，追い出すページを選ぶアルゴリズムは，FIFOとLRUの二つを考える。あるタスクのペー…
正解：FIFO:3／LRU:6
要点：FIFOは古い順、LRUは最後の使用が古い順に追い出す
FIFOは最も古く読み込んだページを追い出します。1,3,2を読み込んだ後、4で1を、5で3を、3で2を追い出す3回の置換で済みます。LRUは最後に使われてから最も時間が経ったものを追い出すため、4以降は毎回置換が起き、4・5・2・3・4・5の6回となり、組合せはFIFO3回・LRU6回です。
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。