LRUとは？えるあーるゆー
LRUとは、記憶領域が満杯になったとき、最後に参照されてからの経過時間が最も長いものを追い出す置換アルゴリズム。直前に使ったものはまた使われるという時間的局所性を根拠にしており、キャッシュメモリのブロック置換にも仮想記憶のページ置換にも同じ規則で使える。
最終更新：2026-10-06
この語が出る過去問を解く →背景
主記憶は有限で、必要なものすべては載らない。理想は「この先いちばん長く使われないもの」を捨てることだが、未来は分からないので、過去の参照の記録で代用したのがこの規則である。もっとも、参照のたびに順序を更新する厳密な実装は負荷が高いため、実機では参照ビットを巡回して確認するクロック方式などの近似が使われる。応用情報では、参照列とページ枠数を与えてLRUとFIFOそれぞれのページフォールト回数を数えさせる計算問題として繰り返し出題される。
具体例
キャッシュ用のデータストアでは、容量上限に達したときの追い出し方針としてこの規則を設定でき、アクセスの多い鍵だけが残るように働く。データベースのバッファプールでも同様の規則が使われるが、全表走査で読んだページに有用なページが押し出されないよう、新しい区画と古い区画に分けて扱うといった工夫が加えられている。
試験での引っ掛け
LFUとの取り違えが典型で、LRUが見るのは最後に使った時刻、LFUが見るのは使った回数である。格納が最も古いものから追い出すFIFOとも区別する。またページ枠を増やしたのにページフォールトが増えるBeladyの異常はFIFOで起きる現象であり、LRUでは起こらない。
関連用語
出た過去問
出典：平成28年度 秋期 応用情報技術者試験 午前 問18（IPA）
プログラムで使用可能な実メモリ枠が3ページである仮想記憶システムにおいて、大きさ6ページのプログラムが実行されたとき、ページフォールトは何回発生するか。ここで、…
正解：10
要点：LRUは最後に使ってから最も時間が経ったページを追い出す
実メモリ枠3ページでLRUを適用し、0,1,2,3,4,0,2,4,3,1,4,5 の順に読み込むと、最初の0・1・2で3回の欠落が起き、以降は3,4,0,2 で置換えが4回続きます。次の4は残っているのでヒットし、3,1 で2回置換え、次の4はヒット、最後の5で1回置換えとなります。ヒットしたのは2回だけなので、12回のアクセスのうちページフォールトは10回です。
出典：平成28年度 春期 応用情報技術者試験 午前 問18（IPA）
仮想記憶方式に関する記述のうち，適切なものはどれか。
正解：LRUアルゴリズムは，使用後の経過時間が最長のページを置換対象とするページ置換アルゴリズムである。
要点：LRUは最後に使ってから最も時間が経ったページを追い出す
LRU（Least Recently Used）は、最後に参照されてから最も長い時間が経過したページを追い出すアルゴリズムである。直近に使ったページは再び使われやすいという参照の局所性に基づく。
出典：平成29年度 春期 応用情報技術者試験 午前 問16（IPA）
4ブロックのキャッシュメモリC0～C3が表に示す状態である。ここで，新たに別のブロックの内容をキャッシュメモリにロードする必要が生じたとき，C2のブロックを置換…
正解：LRU
要点：LRUは最終参照時刻が最も古いブロックを置換対象にする
C2は最終参照時刻が0:05で4つの中で最も古い。参照されてから最も長く使われていないブロックを追い出すのはLRUであり、この条件でC2が置換対象となる。
出典：平成31年度 春期 応用情報技術者試験 午前 問19（IPA）
仮想記憶管理におけるページ置換えアルゴリズムとしてLRU方式を採用する。主記憶のページ枠が、4000, 5000, 6000, 7000番地(いずれも16進数)…
正解：6000
要点：LRUは最後に参照された時刻が最も古いページを置き換える
LRUは最も長く参照されていないページを追い出す。1→2→3→4で4000〜7000に順に載り、2の再参照後、5は最も古い1のいた4000へ入る。3はヒット、次の1は最も古い4のいた7000へ入り、6は最も古い2のいた5000へ入る。5はヒットするので、最後の4は残る中で最も古い3のいた6000番地に置かれる。
出典：令和5年度 春期 応用情報技術者試験 午前 問18（IPA）
仮想記憶方式に関する記述のうち、適切なものはどれか。
正解：LRUアルゴリズムは、使用後の経過時間が最長のページを置換対象とするページ置換アルゴリズムである。
要点：LRUは最も長く使われていないページを追い出す
LRU（Least Recently Used）は、最後に使われてからの経過時間が最も長いページ、つまり最も長く使われていないページを置換対象に選ぶアルゴリズムである。直近に使われたページは再び使われやすいという参照の局所性に基づいた方式で、実装にはアクセス順の管理が必要になる。
出典・参考
公式シラバスの2 コンピュータシステム ＞ 1. オペレーティングシステム ＞ (7) 記憶管理に掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。