キャッシュの置換アルゴリズム（LRU・FIFO・LFU）とは？きゃっしゅのちかんあるごりずむ
キャッシュの置換アルゴリズム（LRU・FIFO・LFU）とは、キャッシュが満杯になったとき、追い出す一本を選ぶ基準の違い。最後に使った時刻で選ぶのがLRU、入った順で選ぶのがFIFO、使われた回数で選ぶのがLFUである。直前に使ったものはまた使われるという時間的局所性が働く環境では時刻を基準にするLRUが外しにくく、実機では実装コストから近似される。
最終更新：2026-10-06
応用情報を最短で暗記・合格する →背景
キャッシュは高速な素子を使うぶん容量あたりの単価が高く、主記憶や補助記憶の全体を載せることは原理的にできない。満杯になった後に何を残すかという選択は必ず発生し、その選び方がヒット率をそのまま左右する。過去の参照履歴から次に使われるものを推し量るしかない、という予測の問題として設計されている。応用情報ではヒット率と実効アクセス時間の計算とセットで問われる。
具体例
3ブロック分のキャッシュにA→B→C→A→Dの順で参照が来ると、Dを入れる時点でLRUは最も長く使われていないBを追い出す。FIFOなら最初に入ったAを追い出し、直後にAを再参照して無駄なミスを招く。実機側では、LinuxのページキャッシュがアクティブとインアクティブのリストでLRUを近似している。
試験での引っ掛け
LRUとLFUの取り違えに注意する。基準が時間なのがLRU、回数なのがLFUで、LFUは初期に大量参照されたあと不要になったブロックが回数の貯金で居座り続けるという欠点を持つ。またLRUの完全実装は参照履歴の管理コストが高いため、CPUのキャッシュでは擬似LRUで代用されており、「実機が厳密なLRUで動く」と読ませる選択肢は誤りである。
関連用語
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。