【応用情報対策】LRUとは？「机が狭い！」を解決する、仮想記憶とページ置換えを徹底解説

2025年11月11日

応用情報技術者試験の午前問題では、OSの根幹をなす「仮想記憶」の仕組みを問う、良質な問題がよく出題されます。

例えば、以下のような問題です（令和7年度春期午前問9より）。

【問題】
仮想記憶管理におけるページ置換えアルゴリズムとしてLRU方式を採用する。主記憶のページ枠が4ページ分（4000, 5000, 6000, 7000番地）ある。

プログラムが参照するページ番号の順が
1 → 2 → 3 → 4 → 2 → 5 → 3 → 1 → 6 → 5 → 4
のとき、最後の参照ページ「4」は、どの番地にページインされるか？

（ただし、最初の1 → 2 → 3 → 4の参照で、それぞれ4000, 5000, 6000, 7000番地にページインされるものとする。）

ア 4000
イ 5000
ウ 6000
エ 7000

「ページ置換え」「LRU」「ページイン」…こうした用語に圧倒されてしまうかもしれませんが、「小さな机と大きな本棚」の例え話で考えれば、何も難しくありません。

そもそも「仮想記憶」とは？ (机と本棚の例え)

この問題は、「コンピュータの小さな（でも高速な）机」と「巨大な（でも低速な）本棚」を、どう効率よく使うか、という話です。

メモリ、HDD/SSD、CPUの関係

主記憶 (メモリ): 高速だが容量が小さく高価な「机」
補助記憶 (HDD/SSD): 低速だが大容量で安価な「本棚」
プログラム (CPU): 「あなた」。あなたは机の上にある資料（ページ）しか作業できません

プログラム（あなた）が1000ページの資料（＝巨大なプログラム）を使って作業をしたいとします。
しかし、あなたの机（主記憶）には、たった4ページ分の資料しか置けません（これが問題文の「4ページ分」です）。

【問題発生】
机が4ページでいっぱいの時に、本棚（補助記憶）にある5ページ目の資料が必要になったら、どうしますか？

【解決策】
机の上にある資料のうち、どれか1つを本棚に戻し、空いたスペースに新しい5ページ目の資料を持ってくるしかありません。

ページイン: 本棚から机に、新しい資料（ページ）を持ってくること。
ページ置換え: 机がいっぱいの時に、どれかを本棚に戻して場所を空けること。

ルールが必要だ！「LRU」という整理術

机がいっぱいの時、どの資料を本棚に戻せばよいでしょうか？適当に戻していると、次の瞬間に「あ！今戻した資料、やっぱり必要だった！」と、また本棚に取りに行く羽目になり、非常に非効率です。

そこで、「どの資料（ページ）を追い出すか」を決める賢いルールが必要になります。これがページ置換えアルゴリズムです。

問題文にあるLRU (Least Recently Used)は、そのルールの名前です。

LRU: 「“最近”、最も使われていない（Least Recently Used）資料（ページ）を本棚に戻す」というルール。

「最後に触ってから、一番時間が経っている資料」は、たぶんもう使わないだろう、という賢い予測に基づいたルールです。

【過去問解説】実際に机の上の資料を入れ替えてみよう

令和7年度応用情報技術者試験春期午前問9より

それでは、この「LRU」ルールを使って、問題の作業（ページ参照）をシミュレーションしてみましょう。

情報を整理

机のスペース (ページ枠): 4つ（4000番地, 5000番地, 6000番地, 7000番地）
ルール: LRU (一番最近使っていないものを追い出す)
作業の順番 (参照順): 1 → 2 → 3 → 4 → 2 → 5 → 3 → 1 → 6 → 5 → 4

机（主記憶）の様子を、順番に見ていきましょう。
「LRU」とは「最も古い（使っていない）」もの、「MRU」とは「最も新しい（使った）」ものです。

参照	4000番地	5000番地	6000番地	7000番地	備考 (LRU ← 古い … 新しい → MRU)
1	1	(空)	(空)	(空)	ページイン。 [ 1 ]
2	1	2	(空)	(空)	ページイン。 [ 1, 2 ]
3	1	2	3	(空)	ページイン。 [ 1, 2, 3 ]
4	1	2	3	4	ページイン。机がいっぱい。 [ 1, 2, 3, 4 ]
2	1	2	3	4	ヒット！ (机の上にあった)。「2」が最新になる。[ 1, 3, 4, 2 ]
5	5	2	3	4	置換え！ (5が無い) LRUは「1」。1を追い出し、4000番地に5を入れる。[ 3, 4, 2, 5 ]
3	5	2	3	4	ヒット！「3」が最新になる。[ 4, 2, 5, 3 ]
1	5	2	3	1	置換え！ (1が無い) LRUは「4」。4を追い出し、7000番地に1を入れる。[ 2, 5, 3, 1 ]
6	5	6	3	1	置換え！ (6が無い) LRUは「2」。2を追い出し、5000番地に6を入れる。[ 5, 3, 1, 6 ]
5	5	6	3	1	ヒット！「5」が最新になる。[ 3, 1, 6, 5 ]
4	5	6	4	1	置換え！ (4が無い) LRUは「3」。3を追い出し、6000番地に4を入れる。[ 1, 6, 5, 4 ]