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