ページ置換アルゴリズム（LRU）

📌

LRUとは

LRUは Least Recently Used の略で、最後に参照されてから最も時間が経った（最も長く使われていない）ページを置換対象にするページ置換アルゴリズムです。ページ置換とは、主記憶のフレーム（＝ページを置く枠）が満杯のとき、どのページを追い出して新しいページを入れるかを決める仕組みのことです。

身近な例で考えると、机の上の本の整理に似ています。机が本でいっぱいになったら、最近まったく開いていない本から棚に戻しますよね。最近よく開く本は手元に残す。これがLRUの考え方です。

上のツールで▶ボタンを押すと、ページ参照列を1つずつ処理しながら、ヒット・フォールト・置換が起こる様子と、累計ページフォールト数が増えていく様子を確認できます。

⚙️

アルゴリズムの仕組み

LRUは各ページが最後に使われた時刻（最終使用時刻）を管理します。そして、ページフォールトでフレームが満杯のときは、その時刻が最も古いページ＝最も長く使われていないページを追い出します。

処理の流れは次のとおりです。
・ヒット時：参照したページがフレームにあれば、そのページの最終使用時刻を「今」に更新する
・フォールトで空きあり：補助記憶から読み込み、空きフレームへ入れる
・フォールトで満杯：最終使用時刻が最も古いページを追い出し、新しいページを入れる

この方式が効くのは、「最近使われたものは今後も使われやすい」という参照の局所性がプログラムにはよく見られるからです。だから「しばらく使っていないページ」を追い出せば、近い将来また必要になる可能性が低く、ムダなフォールトを減らせます。上のツールのヒット時に、参照したページがそのままフレームに残る様子を確認してみてください。

⚖️

他方式との比較

代表的な比較相手がFIFO（First In First Out＝最初に読み込んだページから順に追い出す方式）です。FIFOは「いつ読み込んだか」だけを見ますが、LRUは「いつ最後に使ったか」を見ます。

まとめると、LRUはFIFOより局所性を活かせるためページフォールトが少なくなる傾向があります。ただし、その分「どのページをいつ最後に使ったか」を常に記録しておく必要があり、管理コストがかかります。上のツールでは同じ参照列でLRUを動かすと総ページフォールト数が表示されるので、FIFOページの結果と見比べてみてください。

🔍

参照の局所性とは

参照の局所性（＝ローカリティ）とは、プログラムが短期間のうちに参照するデータやコードは、特定の範囲に集中する傾向があるという性質です。LRUはこの性質を前提として設計されています。

局所性には主に2種類あります。
・時間的局所性：最近使ったデータは、近い将来また使われやすい（例：ループ内で同じ変数を何度も読む）
・空間的局所性：あるアドレスを参照したら、その近くのアドレスも続けて参照されやすい（例：配列を先頭から順に処理する）

なぜLRUがうまく動くか。時間的局所性のおかげで、「最近使ったページは近い将来また使われる可能性が高い」と言えます。だから「最近使っていないページ」を追い出しても、しばらく必要になりにくいのです。逆にFIFOは局所性を考慮しないため、まだ頻繁に使われているページを「単純に古いから」追い出してしまうことがあります。

📊

FIFOとLRUを具体例で比べる

同じ参照列・同じフレーム数でも、どのアルゴリズムを使うかで追い出すページが変わり、ページフォールトの回数も変わります。具体的に何が違うかを整理します。

・FIFO：ページを「読み込んだ順のキュー（待ち行列＝先入れ先出しの列）」として管理し、先頭（最も古く読み込んだもの）から追い出す。管理が単純だが、まだよく使われているページを追い出すことがある
・LRU：「最後に使った時刻」を各ページに記録し、最も古いものを追い出す。参照の局所性を活かせる分だけフォールトが少なくなる傾向があるが、時刻を記録する処理が必要

どちらが必ずよいわけではなく、参照パターンによって差が出ます。上のツールの参照列でLRUのフォールト数を確認し、FIFOページと比べると理解が深まります。

🎯

基本情報技術者 練習問題