LRUとは？最後に参照した時刻でページ置換えを判断する考え方【基本情報技術者試験】

まず結論

LRUとは、最後に参照された時刻が最も古いページを置換対象にするページ置換えアルゴリズムです。

LRUは、Least Recently Used の略です。

基本情報技術者試験では、LRUは 最後に参照した時刻 というキーワードで判断しやすいです。

LRU
→ Recently
→ 最近いつ使ったかを見る
→ 最後に参照した時刻を使う

試験でLRUアルゴリズムのページ置換え判断基準を聞かれたら、最後に参照した時刻 を選びます。

直感的な説明

LRUは、机の上の資料整理に似ています。

机の上には、資料を4冊しか置けないとします。

新しい資料を置きたいのに机がいっぱいなら、どれか1冊を片付ける必要があります。

このとき、LRUでは、一番長い間使っていない資料 を片付けます。

最近使った資料
→ また使うかもしれないので残す

長く使っていない資料
→ 使う可能性が低そうなので追い出す

ページ置換でも同じです。

最近参照されたページは、近いうちにまた参照される可能性があると考え、長く参照されていないページを置換対象にします。

判断に使うのは、回数ではなく 最後に参照した時刻 です。

定義・仕組み

ページ置換えとは、主記憶に必要なページがないときに、どのページを主記憶から追い出すかを決める処理です。

仮想記憶では、プログラムが使うページの一部だけを主記憶に置きます。

主記憶のページ枠がいっぱいの状態で、新しいページを読み込む必要があると、どれかのページを追い出さなければなりません。

このとき、どのページを追い出すかを決める方法が、ページ置換アルゴリズムです。

用語	意味
ページ	仮想記憶で扱う固定サイズの単位
ページ枠	主記憶上でページを入れる場所
ページフォールト	必要なページが主記憶にない状態
ページ置換	主記憶のページを入れ替えること
LRU	最後の参照時刻が最も古いページを置き換える方式

LRUでは、ページが参照されるたびに、そのページを「最近使った」として扱います。

ページ枠がいっぱいで新しいページを入れるときは、枠内にあるページのうち、最後に参照された時刻が最も古いページ を置き換えます。

例えば、次のような状態を考えます。

ページ	最後に参照された時刻	LRUでの見方
A	10:01	比較的新しい
B	09:50	最も古いので置換候補
C	10:05	新しい

この例では、最後に参照された時刻が最も古いBが置換候補になります。

このテーマは、基本情報技術者試験の「コンピュータシステム」や「オペレーティングシステム」と関係する内容です。公式の出題範囲やシラバスは、IPA：基本情報技術者試験から確認できます。

LFU・FIFOとの違い

LRUは、LFUやFIFOと混同しやすいです。

方式	見るもの	判断の合図
LRU	最後に参照した時刻	最近いつ使ったか、最後に参照
LFU	参照頻度	単位時間当たりの参照頻度、Least Frequently Used
FIFO	読み込まれた順番	最初に入ったページを先に出す
参照回数方式	累積の参照回数	これまで何回使われたか

LRUとLFUは名前が似ています。

LRU
→ Recently
→ 最近
→ 最後に参照した時刻

LFU
→ Frequently
→ 頻繁
→ 参照頻度

FE試験では、時刻ならLRU、頻度ならLFU と切ると分かりやすいです。

また、LRUとFIFOも間違えやすいです。

FIFO
→ 先に入ったものを先に出す

LRU
→ 最近使われていないものを出す

古くからページ枠にあるページでも、直前に参照されていれば、LRUでは置換対象になりにくいです。

科目Aでどう出る？

科目Aでは、LRU方式の説明や、ページ置換えアルゴリズムの判断基準として出題されやすいです。

判断するときは、次の表で切ります。

問題文の表現	選びたい方式
最後に参照した時刻が最も古いページを置き換える	LRU
最近使われていないページを置き換える	LRU
単位時間当たりの参照頻度が低いページを置き換える	LFU
最初に読み込まれたページを置き換える	FIFO
これから最も長く使われないページを置き換える	OPT
累積の参照回数が少ないページを置き換える	参照回数系の方式

似た選択肢は、次のように切ります。

選択肢の方向性	判断
最後に参照した時刻	LRU
最初に参照した時刻	LRUではない。FIFO系と混同しやすい
単位時間当たりの参照頻度	LFU
累積の参照回数	LRUではない。回数を見る方式

決め手は、Recently = 最近 です。

LRU
→ 最近いつ参照したかを見る
→ 最後に参照した時刻

どんな場面で使う？

問題文では、ページ参照列を順に追って、ページ枠の中身を更新する問題でLRUの考え方が役立ちます。

基本手順は次のとおりです。

ページ参照列を左から順に見る
参照ページがページ枠にあれば、置換はしない
ただし、そのページは「最近使った」として更新する
参照ページがページ枠になければ、ページフォールトになる
空き枠があれば、そのまま入れる
空き枠がなければ、最後の参照が最も古いページを置き換える

例えば、ページ枠が3つで、次の順に参照するとします。

1, 2, 3, 2, 4

途中の状態を簡単に追うと、次のようになります。

参照	ページ枠	考え方
1	1	空き枠に入れる
2	1, 2	空き枠に入れる
3	1, 2, 3	空き枠に入れる
2	1, 2, 3	2を最近使った扱いにする
4	4, 2, 3	最後の参照が最も古い1を置き換える

ここで、ページ2を参照した後に、ページ2を古いままと考えると間違えます。

LRUでは、ヒットしたページも参照時刻を更新する のがポイントです。

よくある誤解・混同

LRUでは、次の混同がよく起こります。

混同	正しい切り分け
LRUは参照回数を見る	LRUは最後に参照した時刻を見る
LRUは最初に参照した時刻を見る	LRUは最後に参照した時刻を見る
LFUとLRUを同じだと思う	LFUは頻度、LRUは最近使った時刻
累積の参照回数が少ないものを必ず置換する	LRUでは回数ではなく、最後に使った時刻を見る
最近よく使ったページを捨てる	LRUは最近使われていないページを捨てる
ページ枠にあるページを見たら何もしない	置換はしないが、参照時刻は更新する
数字が小さいページを追い出す	ページ番号の大小は関係ない

さらに注意したいひっかけ

LRUでは、次のひっかけにも注意します。

ひっかけ表現	なぜ注意する？
最初に参照した時刻	LRUではなく、古い順やFIFO系の考え方に近い
単位時間当たりの参照頻度	LFUの判断基準
累積の参照回数	回数を見る方式で、LRUとは違う
使用頻度の低いページを置き換える	LFUの説明になりやすい
ページサイズが小さいものを置き換える	LRUの判断基準ではない

LRUは、最近使われたかどうか だけを見ます。

古くから存在しているページでも、直前に参照されていれば置換対象にはなりにくいです。

まとめ（試験直前用）

LRUは、Least Recently Used の略
LRUは、最後に参照された時刻が最も古いページを置換する
判断の合図は「最後に参照した時刻」「最近使われていない」
LFUは、単位時間当たりの参照頻度を見る
FIFOは、最初に読み込まれた順番を見る
LRUは参照回数ではなく、最後に使ったタイミングを見る
ページ枠にヒットした場合も、参照時刻は更新する
FE試験では、用語の切り分けとページ参照順の確認に役立つ

主記憶管理やページングは、用語の役割をつなげて整理すると覚えやすくなります。

🔗 関連記事

🏠 基本情報技術者トップに戻る