キャッシュの置換アルゴリズム（LRU・FIFO・LFU）とは？

キャッシュの置換アルゴリズム（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）が出た過去問

• 仮想記憶方式に関する記述のうち，適切なものはどれか。

  正解：LRUアルゴリズムは，使用後の経過時間が最長のページを置換対象とするページ置換アルゴリズムである。

  要点：LRUは最長未使用ページを置換する。局所性が前提

  LRU（Least Recently Used）は最後に参照されてから最も時間が経ったページ、すなわち最長未使用のページを追い出すアルゴリズムである。参照の局所性から、直近に使われていないページは今後も使われにくいという前提に立つ。ページ置換方式としてFIFOより一般にヒット率が高い。

  出典：平成28年度 春期 高度共通_午前I試験 am1 問6（IPA）

• 4ブロックのキャッシュメモリC0〜C3が表に示す状態である。ここで，新たに別のブロックの内容をキャッシュメモリにロードする必要が生じたとき，C2のブロックを置換…

  正解：LRU

  要点：LRUは最終参照が最古、FIFOはロードが最古を追い出す

  C2は最終参照時刻が0:05で4つの中で最も古く、最後に使われてから最も長く放置されている。最長未使用のブロックを追い出すのはLRUである。FIFOならロード時刻が最も古いC0、LIFOなら最も新しいC3、LFUなら参照回数が最少のC1が対象になる。

  出典：平成29年度 春期 高度共通_午前I試験 am1 問6（IPA）

• 4ブロックのキャッシュメモリC0〜C3が表に示す状態である。ここで、新たに別のブロックの内容をキャッシュメモリにロードする必要が生じたとき、C2のブロックを置換…

  正解：LRU

  要点：LRUは最終参照時刻が最も古いブロックを置き換える

  LRU（Least Recently Used）は最終参照時刻が最も古いブロックを追い出す方式である。表の最終参照時刻はC0が0:08、C1が0:06、C2が0:05、C3が0:10なので、最も古いC2が置換対象になる。

  出典：令和7年度 秋期 高度共通_午前I試験 am1 問6（IPA）

• 仮想記憶管理におけるページ置換えアルゴリズムとしてLRU方式を採用する。主記憶のページ枠が、4000, 5000, 6000, 7000番地（いずれも16進数）…

  正解：6000

  要点：LRUは最後に参照してから最も時間が経ったページを追い出す

  LRUは最後に参照されてから最も時間が経ったページを追い出す。初期状態は4000＝1、5000＝2、6000＝3、7000＝4である。5の参照で最も古い1（4000番地）が置き換わり、次の1の参照で4（7000番地）が、6の参照で2（5000番地）が置き換わる。最後の4の参照時に最も古いのは3（6000番地）なので、ページ4は6000番地にページインされる。

  出典：令和7年度 春期 高度共通_午前I試験 am1 問6（IPA）