情報処理試験を勉強していると、「LRU・FIFO・LFU…ページ置換アルゴリズムが多すぎて、どれがどれだか分からない」と混乱しがちです。
対象試験と出題頻度
LRU（Least Recently Used）は、基本情報技術者・応用情報技術者で出題されるテーマです。
キャッシュメモリのブロック置換や仮想記憶のページ置換で、FIFO・LFU・LIFOとの違いを正確に判別できるかが問われます。
詳細をクリックして確認
基本情報技術者
応用情報技術者
★★★☆☆
ランクB（標準）覚えておくと有利
用語の定義
LRU（Least Recently Used）とは、一言で言うと
「最も長い間参照されていないデータを優先的に追い出す、ページ置換アルゴリズム」
のことです。
イメージとしては、「冷蔵庫の奥で一番長く放置されている食材から処分する」という整理法です。
冷蔵庫がいっぱいになったとき、「最後に手に取ったのが一番昔の食材」を捨てて新しい食材を入れる。
LRUはまさにこの考え方で、メモリ上のデータを管理します。
📊 LRUの基本情報
| 項目 | 内容 |
|---|---|
| 英語名 | Least Recently Used |
| 分類 | ページ置換アルゴリズム（キャッシュ置換アルゴリズム） |
| 判断基準 | 最後に参照されてからの経過時間（最も古いものを追い出す） |
| 使われる場面 | 仮想記憶のページ置換、キャッシュメモリのブロック置換 |
解説
なぜLRUが必要なのか
コンピュータのメモリには容量の上限があります。
仮想記憶では主記憶に載せきれないページが発生し、キャッシュでもブロック数に限りがあります。新しいデータを読み込むには、既存のデータのどれかを追い出す必要があり、「どれを追い出すか」を決めるルールがページ置換アルゴリズムです。
プログラムには「最近使ったデータは近い将来も使われやすい」という性質（時間的局所性）があります。
LRUはこの性質を利用し、「最後の参照が最も古いデータ＝今後も使われにくい」と判断して追い出します。理論上の最適解（OPT）には及ばないものの、実用性と置換精度のバランスに優れた方式です。
LRUの動作を図解で理解する
ページ枠が3つ、参照順序が「1→2→3→4→2→5」の場合を追跡します。
LRU ページ置換の動作例（ページ枠3つ）
| ステップ | 参照ページ | 枠1 | 枠2 | 枠3 | 置換発生？ | 追い出し対象 |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | – | – | なし（空きあり） | – |
| 2 | 2 | 1 | 2 | – | なし（空きあり） | – |
| 3 | 3 | 1 | 2 | 3 | なし（空きあり） | – |
| 4 | 4 | 2 | 3 | あり | ページ1（最古参照） | |
| 5 | 2 | 4 | 2 | 3 | なし（既存） | – |
| 6 | 5 | 4 | 2 | あり | ページ3（最古参照） |
▲ ステップ4：1,2,3のうち最後の参照が最も古いのは1 ／ ステップ6：4,2,3のうち最古は3（ステップ3以来未参照）
ポイントは「ページインした時刻」ではなく「最後に参照された時刻」で判断する点です。ステップ5でページ2が参照されたため、2の「最終参照時刻」が更新されています。
これがFIFO（先入れ先出し）との決定的な違いです。
FIFO・LFUとの比較
LRUを正しく位置づけるには、他の主要なアルゴリズムと「何を基準に追い出すか」で整理するのが近道です。
| アルゴリズム | 正式名称 | 追い出し基準 | 見分けキーワード |
|---|---|---|---|
| LRU | Least Recently Used | 最後に参照されてからの経過時間が最も長いもの | 「最後の参照が最古」 |
| FIFO | First In First Out | ページインしてからの時間が最も長いもの | 「最初に入ったもの」 |
| LFU | Least Frequently Used | 参照回数が最も少ないもの | 「使用頻度（回数）」 |
| LIFO | Last In First Out | 最も新しくページインしたもの | 「最後に入ったもの」 |
ページ置換アルゴリズム 判別フローチャート
※ 試験で迷ったら「回数 or 時刻？」→「参照時刻 or 搬入時刻？」の2段階で判別
では、この用語が試験でどのように出題されるか見ていきましょう。
💡 LRUの核心を3行で
・「最後に参照されてからの経過時間が最も長い」データを追い出す方式
・FIFOとの違いは「参照済みデータの最終参照時刻が更新される」点
・LFUは「回数」で判断するのに対し、LRUは「時刻」で判断する
試験ではこう出る！
LRUは、FE・APの科目A（午前）でキャッシュメモリのブロック置換や仮想記憶のページ置換として繰り返し出題されています。出題パターンは大きく2つに分かれます。
📊 過去問での出題実績
| 試験回 | 出題内容 | 問われたポイント |
|---|---|---|
| FE R4免除 問18 |
LRUの説明として正しい記述を選ぶ問題。 | ・正解は「最も長い間参照されていないページを追い出す」 ・FIFO・LIFOの説明がひっかけ |
| FE R4免除 問17 |
LRU方式でページ参照順序をたどり、最後の参照ページが何番地にあるかを求める計算問題。 | ・各ステップで「最終参照が最古のページ」を追い出す手順を追跡 ・AP H31春 問19と同一構成 |
| FE H29春 問19 |
FIFOとLRUの両方でページ置換回数を求め、正しい組合せを選ぶ問題。 | ・FIFOとLRUを同じ参照列で比較 ・両方の追跡結果を間違えずに出せるかが鍵 |
| AP H29春 午前 問16 |
キャッシュメモリC0～C3の状態表から、LRUで置換対象となるブロックを選ぶ問題。 | ・最終参照時刻が最古のブロックを表から読み取る ・FIFO・LFU・LIFOとの違いも選択肢に登場 |
📝 IPA試験での出題パターン
パターン1：「LRUの説明を選べ」（知識問題）
FIFO・LFU・LIFO・LRUの説明文が並び、LRUに該当するものを選ぶ形式。ひっかけとして「ページインしてからの時間が最も長い」（FIFO）、「参照回数が最も少ない」（LFU）が紛れ込む。キーワードは「最後に参照されてからの時間が最も長い」。
パターン2：「置換の追跡計算」（計算問題）
参照ページの順序とページ枠数が与えられ、各ステップでどのページが追い出されるかを追跡する形式。ここだけは確実に押さえてください。紙に表を書いて各ステップの「最終参照時刻」を管理すれば確実に解けます。
試験ではここまででOKです。LRUの内部実装（タイムスタンプ方式やスタック方式など）の詳細まで問われることはないので、深追いは不要です。
【確認テスト】理解度チェック
ここまでの内容を理解できたか、簡単なクイズで確認してみましょう。
Q. 仮想記憶におけるページ置換アルゴリズムの一つであるLRUの説明として、最も適切なものはどれでしょうか？
- A. 最も長い間参照されていないページを、置換えの対象とする。
- B. 主記憶に存在している時間が最も長いページを、置換えの対象とする。
- C. 参照された回数が最も少ないページを、置換えの対象とする。
正解と解説を見る
正解：A
解説：
LRU（Least Recently Used）は、最後に参照されてからの経過時間が最も長いページを追い出す方式です。「Recently Used（最近使われた）」の「Least（最も少ない）」、つまり「最も最近使われていない」ものを対象とします。
選択肢Bは FIFO（First In First Out）の説明です。FIFOは「ページインした時刻」の古さで判断するため、途中で再参照されても追い出し順位が変わりません。選択肢Cは LFU（Least Frequently Used）の説明です。LFUは「参照回数」で判断するアルゴリズムであり、時刻ではなく累積回数に着目する点がLRUとは異なります。
よくある質問（FAQ）
Q. LRUは実際のOSやソフトウェアでも使われていますか？
使われています。LinuxカーネルのページキャッシュはLRUを改良した「2リスト方式（Active/Inactiveリスト）」を採用しています。また、WebブラウザのキャッシュやデータベースのバッファプールでもLRUベースの管理が広く使われています。純粋なLRUそのままではなく、実装コストを抑えた近似LRU（Clock方式など）が採用されるケースも多いです。
Q. LRUの計算問題を解くコツはありますか？
紙にページ枠分の列を作り、各ステップで「最終参照時刻」を列の横にメモしていく方法が確実です。参照のたびに該当ページの時刻を現在ステップ番号に書き換え、置換が必要になったら時刻が最も小さい（古い）ページを選びます。FIFOとの比較問題では同じ表を2つ作り、FIFOは「ページインした時刻」、LRUは「最後に参照した時刻」とラベルを分けて管理すると混同を防げます。
Q. OPT（最適ページ置換）とLRUの違いは何ですか？
OPT（Optimal Page Replacement）は「将来最も長く使われないページ」を追い出す理論上の最適アルゴリズムです。ただし未来の参照列を事前に知る必要があるため、実システムでは実装できません。LRUは「過去の参照履歴」を使って将来を推測する現実的な近似手法であり、OPTに近い性能を出せることが知られています。IPA試験では、OPTが選択肢に登場することはまれですが、「実現不可能な理想的方式」として区別できれば十分です。
Q. LRUはキャッシュメモリと仮想記憶のどちらで出題されますか？
両方で出題されます。キャッシュメモリの文脈では「ブロック置換」として、仮想記憶の文脈では「ページ置換」として登場します。アルゴリズムの考え方はどちらも同じで、「最終参照が最も古いものを追い出す」というルールは変わりません。AP H29春 問16はキャッシュメモリ、FE R4免除 問17は仮想記憶という具合に、出題側がどちらの文脈でも使ってくるため、両方の場面で適用できるようにしておくと安心です。
