キャッシュの置換アルゴリズム（LRU・FIFO・LFU）とは？
キャッシュの置換アルゴリズム（LRU・FIFO・LFU）とは、キャッシュが満杯のときに、どのブロックを追い出すかを決める規則。LRUは最後に使われてからの時間が最も長いもの、FIFOは最も古く格納されたもの、LFUは参照回数が最も少ないものを追い出す。局所性を前提とすると一般にLRUが有利で、ハードウェアでは近似実装が使われる。
応用情報技術者試験の過去問では9回出題されています（2016年度〜2025年度）。
きゃっしゅのちかんあるごりずむ
キャッシュの置換アルゴリズム（LRU・FIFO・LFU）の意味
キャッシュが満杯のときに、どのブロックを追い出すかを決める規則。LRUは最後に使われてからの時間が最も長いもの、FIFOは最も古く格納されたもの、LFUは参照回数が最も少ないものを追い出す。局所性を前提とすると一般にLRUが有利で、ハードウェアでは近似実装が使われる。
キャッシュの置換アルゴリズム（LRU・FIFO・LFU）の具体例
3ブロック分のキャッシュにA→B→C→A→D の順で参照が来た場合、LRUではDを入れる時点で最も長く使われていないBが追い出される。FIFOなら最初に入ったAが追い出され、直後にAを再参照すると無駄なミスになる。この差がヒット率の計算問題で問われる。
キャッシュの置換アルゴリズム（LRU・FIFO・LFU）は試験でどう引っ掛けられる？
LRUとLFUの取り違えに注意。LFUは「回数」なので、初期に大量参照された後に不要になったブロックが居座り続ける欠点がある。またLRUの完全実装は履歴管理のコストが高く、実機では擬似LRUで代用されている。
キャッシュの置換アルゴリズム（LRU・FIFO・LFU）と関連する用語
キャッシュの置換アルゴリズム（LRU・FIFO・LFU）が出た過去問
プログラムで使用可能な実メモリ枠が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／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。