ページ置換アルゴリズム（LRU・FIFO）とは？ぺーじちかんあるごりずむ
ページ置換アルゴリズム（LRU・FIFO）とは、ページフォールト時に、主記憶のどのページを追い出して空きを作るかを決める規則。FIFOは読み込みの古い順、LRUは最後に参照されてからの時間が長い順、LFUは参照回数の少ない順に選ぶ。選び方の差がページフォールト回数、すなわち実行時間へ直接跳ね返る。
最終更新：2026-10-06
この語が出る過去問を解く →背景
仮想記憶は主記憶より大きなアドレス空間を見せる仕組みで、載りきらない分を補助記憶へ追い出すことで成り立っている。追い出す相手を誤ると、すぐ使うページを外しては読み直すスラッシングに陥り、CPUは待ちに終始する。理想は「次に使われないページを外す」ことだが未来は分からないため、過去の参照履歴から近似する——という設計判断がこの手法群の出発点になっている。
具体例
PostgreSQLやOracleのバッファ管理、Linuxのページキャッシュはいずれもクロック方式などLRUの近似で、参照時刻を厳密に記録する負担を参照ビット1個ぶんに落としている。
試験での引っ掛け
FIFOは枠を増やすとかえってページフォールトが増えるベラディの異常が起こり得る（LRU・LFUでは起きない）。「枠を増やせば必ず速くなる」は誤り。参照列を与えて方式ごとにフォールト数を数える問題では、置換が起きない参照でもLRUの順序更新が必要な点を落としやすい。
関連用語
出た過去問
出典：平成28年度 春期 応用情報技術者試験 午前 問18（IPA）
仮想記憶方式に関する記述のうち，適切なものはどれか。
正解：LRUアルゴリズムは，使用後の経過時間が最長のページを置換対象とするページ置換アルゴリズムである。
要点：LRUは最後に使ってから最も時間が経ったページを追い出す
LRU（Least Recently Used）は、最後に参照されてから最も長い時間が経過したページを追い出すアルゴリズムである。直近に使ったページは再び使われやすいという参照の局所性に基づく。
出典：平成31年度 春期 応用情報技術者試験 午前 問19（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番地に置かれる。
出典：令和5年度 春期 応用情報技術者試験 午前 問17（IPA）
仮想記憶システムにおいて、ページ置換えアルゴリズムとしてFIFOを採用して、仮想ページ参照列1, 4, 2, 4, 1, 3を3ページ枠の実記憶に割り当てて処理…
正解：3, 4, 2
要点：FIFOは参照の新旧に関係なく、最も古く入れたページを追い出す
ステップ4の4とステップ5の1はいずれも実記憶に存在するのでヒットとなり、状態は1・4・2のまま変わらない。ステップ6で3を参照するとページフォールトとなり、FIFOでは最も先に読み込んだ1が追い出される。空いた枠に3が入るため、最終状態は3・4・2となる。
出典：令和5年度 春期 応用情報技術者試験 午前 問18（IPA）
仮想記憶方式に関する記述のうち、適切なものはどれか。
正解：LRUアルゴリズムは、使用後の経過時間が最長のページを置換対象とするページ置換アルゴリズムである。
要点：LRUは最も長く使われていないページを追い出す
LRU（Least Recently Used）は、最後に使われてからの経過時間が最も長いページ、つまり最も長く使われていないページを置換対象に選ぶアルゴリズムである。直近に使われたページは再び使われやすいという参照の局所性に基づいた方式で、実装にはアクセス順の管理が必要になる。
出典：令和7年度 春期 応用情報技術者試験 午前 問15（IPA）
仮想記憶管理におけるページ置換えアルゴリズムとしてLRU方式を採用する。主記憶のページ枠が，4000，5000，6000，7000番地（いずれも16進数）の4ペ…
正解：6000
要点：LRUは最終参照が最も古いページを置換対象に選ぶ
LRUは最後に参照されてから最も時間が経ったページを追い出す方式である。初期状態は4000～7000番地にページ1～4が入っており、以降の参照を追うと、5の参照で最も古い1（4000番地）が、1の参照で4（7000番地）が、6の参照で2（5000番地）が順に置き換わる。最後に4を参照する時点で最も古いのは6000番地のページ3なので、ページ4はここにページインされる。
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。