ページ置換アルゴリズム（LRU・FIFO）とは？
ページ置換アルゴリズム（LRU・FIFO）とは、主記憶に空きページ枠が無いとき、どのページを追い出すかを決める規則。LRUは最後に参照された時刻が最も古いページを、FIFOは最も早く読み込まれたページを、LFUは参照回数が最も少ないページを追い出す。実際のOSは実装コストを抑えたLRU近似（参照ビットを用いるクロック方式）を使うことが多い。応用情報では参照列を与えられ、方式ごとのページフォールト回数を数える問題が定番。
応用情報技術者試験の過去問では9回出題されています（2016年度〜2025年度）。
ぺーじちかんあるごりずむ
ページ置換アルゴリズム（LRU・FIFO）の意味
主記憶に空きページ枠が無いとき、どのページを追い出すかを決める規則。LRUは最後に参照された時刻が最も古いページを、FIFOは最も早く読み込まれたページを、LFUは参照回数が最も少ないページを追い出す。実際のOSは実装コストを抑えたLRU近似（参照ビットを用いるクロック方式）を使うことが多い。応用情報では参照列を与えられ、方式ごとのページフォールト回数を数える問題が定番。
ページ置換アルゴリズム（LRU・FIFO）の具体例
枠が3で参照列が1,2,3,1,4のとき、4を入れる場面でFIFOは最初に入った1を追い出すが、LRUは直前に1が参照されているため2を追い出す。この差がそのまま実行時間に効くため、DBのバッファプールは多くがLRU系を採用する。
ページ置換アルゴリズム（LRU・FIFO）は試験でどう引っ掛けられる？
FIFOは枠を増やすとかえってページフォールトが増える「ベラディの異常」が起こり得る。LRUやLFUでは起きない。「枠を増やせば必ず速くなる」と決めつけると誤る。
ページ置換アルゴリズム（LRU・FIFO）と関連する用語
ページ置換アルゴリズム（LRU・FIFO）が出た過去問
プログラムで使用可能な実メモリ枠が3ページである仮想記憶システムにおいて、大きさ6ページのプログラムが実行されたとき、ページフォールトは何回発生するか。ここで、…
正解：10
要点：LRUは最後に使ってから最も時間が経ったページを追い出す
実メモリ枠3ページでLRUを適用し、0,1,2,3,4,0,2,4,3,1,4,5 の順に読み込むと、最初の0・1・2で3回の欠落が起き、以降は3,4,0,2 で置換えが4回続きます。次の4は残っているのでヒットし、3,1 で2回置換え、次の4はヒット、最後の5で1回置換えとなります。ヒットしたのは2回だけなので、12回のアクセスのうちページフォールトは10回です。
出典：平成28年度 秋期 応用情報技術者試験 午前 問18（IPA）多数のクライアントが，LANに接続された1台のプリンタを共同利用するときの印刷要求から印刷完了までの所要時間を，待ち行列理論を適用して見積もる場合について考える…
正解：印刷の緊急性や印刷量の多少にかかわらず，先着順に印刷する。
要点：M/M/1はポアソン到着・指数サービス・無限長FIFOが前提
M/M/1モデルは、到着がポアソン分布、サービス時間が指数分布、窓口が1つ、待ち行列は無限長で先着順（FIFO）に処理される、という条件を前提とする。先着順に印刷するという運用はこのFIFOの前提に合致する。
出典：平成28年度 春期 応用情報技術者試験 午前 問3（IPA）仮想記憶方式に関する記述のうち，適切なものはどれか。
正解：LRUアルゴリズムは，使用後の経過時間が最長のページを置換対象とするページ置換アルゴリズムである。
要点：LRUは最後に使ってから最も時間が経ったページを追い出す
LRU（Least Recently Used）は、最後に参照されてから最も長い時間が経過したページを追い出すアルゴリズムである。直近に使ったページは再び使われやすいという参照の局所性に基づく。
出典：平成28年度 春期 応用情報技術者試験 午前 問18（IPA）4ブロックのキャッシュメモリC0～C3が表に示す状態である。ここで，新たに別のブロックの内容をキャッシュメモリにロードする必要が生じたとき，C2のブロックを置換…
正解：LRU
要点：LRUは最終参照時刻が最も古いブロックを置換対象にする
C2は最終参照時刻が0:05で4つの中で最も古い。参照されてから最も長く使われていないブロックを追い出すのはLRUであり、この条件でC2が置換対象となる。
出典：平成29年度 春期 応用情報技術者試験 午前 問16（IPA）仮想記憶管理におけるページ置換えアルゴリズムとしてLRU方式を採用する。主記憶のページ枠が、4000, 5000, 6000, 7000番地(いずれも16進数)…
正解：6000
要点：LRUは最後に参照された時刻が最も古いページを置き換える
LRUは最も長く参照されていないページを追い出す。1→2→3→4で4000〜7000に順に載り、2の再参照後、5は最も古い1のいた4000へ入る。3はヒット、次の1は最も古い4のいた7000へ入り、6は最も古い2のいた5000へ入る。5はヒットするので、最後の4は残る中で最も古い3のいた6000番地に置かれる。
出典：令和1年度 春期 応用情報技術者試験 午前 問19（IPA）
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。