LRU（Least Recently Used）とは？

LRU（Least Recently Used）の意味

領域がいっぱいになったときに、最後に参照してから最も時間が経っているものを追い出す置換え方式。直前に使われたものは近いうちにまた使われるという経験則（時間的局所性）に基づいており、キャッシュメモリの入替え、仮想記憶のページ置換え、Webブラウザのキャッシュなど、限られた領域を効率よく使う場面で広く採用されている。対になる方式には、最初に入れたものから順に追い出すFIFOがある。

LRU（Least Recently Used）の具体例

4冊しか置けない机にA・B・C・Dを置いた後、B・Aを見返してから5冊目のEを置くとき、最後に参照した時期が最も古いCを引き出しへしまう。この「机」をキャッシュ、「引き出し」を主記憶に置き換えたものがLRUの動きそのものである。

LRU（Least Recently Used）は試験でどう引っ掛けられる？

「最も古く置いたもの」を追い出すFIFOと取り違えやすい。LRUが見るのは置いた時刻ではなく最後に参照した時刻なので、途中で読み返されたものは新しい扱いに戻る。参照回数が最も少ないものを追い出すLFUとも別物である。

LRU（Least Recently Used）と関連する用語

• キャッシュメモリ
• 仮想記憶（ページング）
• キャッシュヒット率
• 記憶階層（メモリ階層構造）

LRU（Least Recently Used）が出た過去問

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

  正解：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）