最終更新日：2026年8月2日

fe fe-technology computer-architecture cache-memory

まず結論

LRUとは、最後に参照されてから最も長い時間が経過したデータを置き換える方式です。

LRUは、Least Recently Usedの略です。

基本情報技術者試験では、次の対応で切り分けます。

最後に参照されてから最も長い
→ LRU

参照回数が最も少ない
→ LFU

最初に読み込まれた
→ FIFO

最近使われていない
→ NRU

覚える一文はこれです。

LRUは最後に使ってから最も時間が経ったものを追い出す。

直感的な説明

机の上に、よく使う資料だけを置いていると考えます。

机がいっぱいの状態で、新しい資料を置きたいとします。

このとき、

最近使った資料
→ また使う可能性が高いので残す

長い間使っていない資料
→ すぐには使わない可能性が高いので片付ける

と考えます。

これがLRUです。

LRUは、「最近使われたものは、また近いうちに使われやすい」という考え方を利用しています。

定義・仕組み

LRUの意味

LRUは、置換候補の中から、最後に参照された時刻が最も古いものを選びます。

最後の参照が新しい
→ 残す

最後の参照が古い
→ 置換候補

ここで重要なのは、読み込まれた時刻ではなく、最後に使われた時刻を見ることです。

キャッシュ置換とは

キャッシュメモリには容量の上限があります。

新しいブロックを読み込みたいのに空きがない場合、既に入っているブロックのどれかを主記憶側へ追い出す必要があります。

このとき、どのブロックを置き換えるかを決める方式を、キャッシュ置換方式といいます。

キャッシュに空きがある
→ そのまま格納

キャッシュに空きがない
→ 置換対象を選ぶ

ページ置換との関係

LRUは、キャッシュメモリだけでなく、仮想記憶のページ置換でも使われる考え方です。

キャッシュメモリ
→ ブロックを置き換える

仮想記憶
→ ページを置き換える

対象は異なりますが、「最も長く使われていないものを追い出す」という判断は同じです。

時間的局所性

LRUは、時間的局所性を利用しています。

時間的局所性とは、最近使ったデータは、近いうちに再び使われる可能性が高いという性質です。

最近使った
→ また使う可能性が高い

長く使っていない
→ 当面使わない可能性が高い

LRUは、この性質を前提に置換対象を決めます。

このテーマは、基本情報技術者試験のキャッシュメモリや仮想記憶に関係する内容です。公式の出題範囲やシラバスは、IPA：基本情報技術者試験 から確認できます。

科目Aでどう出る？

科目Aでは、LRUの説明として正しいものを選ぶ問題が出題されます。

判断キーワード

次の表現があれば、LRUを考えます。

最後に参照されてから
最も長い時間が経過
最近最も使われていない
最終参照時刻が最も古い

特に、

最後に参照されてから最も長い

が決め手です。

FIFOとの違い

FIFOは、First In First Outの略です。

最初に読み込まれたものを、最初に置き換えます。

読み込んだ順番を見る
→ FIFO

最後に参照した時刻を見る
→ LRU

例えば、A、B、Cの順に読み込まれ、その後Aが何度も参照されたとします。

FIFO
→ 最初に入ったAを置き換える

LRU
→ 最近使われたAは残す
→ BまたはCのうち、最後の参照が古い方を置き換える

LFUとの違い

LFUは、Least Frequently Usedの略です。

参照された回数が最も少ないものを置き換えます。

最後に使った時刻
→ LRU

使われた回数
→ LFU

過去に多く使われたが、最近は使われていないデータがある場合、LRUとLFUでは判断が異なることがあります。

NRUとの違い

NRUは、Not Recently Usedの略です。

最近使われたかどうかを基準に、置換候補を分類します。

最も長く使われていないものを特定
→ LRU

最近使われていないものから選ぶ
→ NRU

LRUの方が、参照順序を細かく管理します。

参照列から判断する方法

LRUでは、各ブロックの「最後に使われた順番」を追います。

例えば、キャッシュに3ブロック格納でき、参照列が次のとおりだとします。

A → B → C → A → D

最初にA、B、Cが入ります。

[A, B, C]

その後Aが再び参照されます。

この時点で、最後に使われた順番は次のようになります。

最も新しい
A

その次
C

最も古い
B

次にDを入れるとき、キャッシュは満杯です。

そのため、最後に参照されてから最も時間が経ったBを置き換えます。

[A, D, C]

書き方のコツ

参照列の問題では、各参照のたびに順番を書き直すと安全です。

A参照
→ A

B参照
→ A, B

C参照
→ A, B, C

A参照
→ B, C, A

D参照
→ C, A, D

左を最も古い、右を最も新しいとして並べると、左端が置換対象です。

どんな場面で使う？

キャッシュメモリ

CPUがよく使うデータを高速なキャッシュへ置いておく場合に、どのブロックを入れ替えるか判断します。

仮想記憶

主記憶に空きがない場合、どのページを補助記憶へ追い出すか判断します。

ソフトウェアのキャッシュ

Webブラウザ、データベース、アプリケーションなどでも、限られたキャッシュ領域を管理するためにLRUの考え方が使われます。

よくある誤解・混同

読み込んでから最も長いものがLRU

誤りです。

それはFIFOの考え方です。

読み込んだ時刻
→ FIFO

最後に参照した時刻
→ LRU

参照回数が少ないものがLRU

誤りです。

参照回数を見るのはLFUです。

時間
→ LRU

回数
→ LFU

一定時間使われていないものがLRU

似ていますが、試験ではNRUと切り分けます。

最近使われていないかを分類
→ NRU

最終参照時刻を比較して最も古いものを選ぶ
→ LRU

最初に入ったものは必ず最初に出る

これはFIFOです。

LRUでは、途中で再び参照されれば、そのデータは最近使われたものとして残りやすくなります。

LRUは常に最良の方式

LRUは時間的局所性を利用できる有効な方式ですが、参照順序の管理が必要です。

そのため、実装コストや管理負荷とのバランスを考える必要があります。

LRUはキャッシュメモリだけで使う

違います。

仮想記憶のページ置換や、ソフトウェアのキャッシュ管理でも使われます。

科目Bでどう使う？

科目Bでは、参照順序を配列やリストで管理する処理として出題される可能性があります。

考え方は次のとおりです。

データが既にある
→ いったん取り除いて末尾へ移動

データがない
→ 空きがあれば追加

空きがない
→ 先頭の最も古いデータを削除して追加

Pythonで単純に表すと、次のようになります。

capacity = 3
cache = []

references = ["A", "B", "C", "A", "D"]

for item in references:
    if item in cache:
        cache.remove(item)
        cache.append(item)
    else:
        if len(cache) >= capacity:
            cache.pop(0)
        cache.append(item)

    print(cache)

左端を最も古く、右端を最も新しい参照として管理しています。

まとめ（試験直前用）

  • LRUはLeast Recently Usedの略
  • 最後に参照されてから最も時間が経ったものを置き換える
  • LRUは最後の参照時刻を見る
  • FIFOは読み込まれた順番を見る
  • LFUは参照回数を見る
  • NRUは最近使われたかどうかを見る
  • LRUは時間的局所性を利用する
  • キャッシュ置換とページ置換の両方で使われる
  • 参照列問題では、最後に使われた順番を毎回更新する
  • 「時間・回数・読込み順」のどれを見ているかで切り分ける

LRUは最後に使った時刻、LFUは使用回数、FIFOは読み込んだ順番。

© 2024-2026 stemtazoo. All rights reserved.