平成21年度 春期 ITパスポート試験 問85 解説 LRUアルゴリズム

机の上の空き枠を管理する際、最も古く参照されたファイルを優先的に入れ替えるルールを適用します。問題文にあるアクセス順序に沿って、机の上の状況がどう変化するかを4つの枠（スロット）で追いかけるのが最短の解法です。

最も古いファイルを入れ替えるLRUアルゴリズム

この問題は、OSのメモリ管理などで用いられるLRU（Least Recently Used）アルゴリズムを机の上のファイル整理に例えたものです。LRUとは、最後に使用してからの経過時間が最も長いもの、つまり最も長い間使われていないものを追い出す手法を指します。

今回の手順を追いかけると、以下のようになります。

1. A, B, C, Dの順でアクセス：机が満杯になります。（机：A, B, C, D）
2. Bにアクセス：Bが最新になります。（机：A, B, C, D）
3. Aにアクセス：Aが最新になります。（机：A, B, C, D）
4. Eにアクセス：机が満杯なので、最も古いCを追い出してEを入れます。（机：A, B, D, E）
5. Aにアクセス：Aが最新になります。（机：A, B, D, E）
6. Bにアクセス：Bが最新になります。（机：A, B, D, E）
7. Fにアクセス：机が満杯なので、現在入っているA, B, D, Eのうち、最も長い間使われていないDを追い出してFを入れます。（机：A, B, E, F）

この結果、最後に引き出しにしまったファイルはDとなります。

効率的なリソース管理の考え方

限られたリソース（今回は机の上のスペース）を最大限に活用するために、すべてのアイテムを等しく扱うのではなく「最近使ったものほど、またすぐに使う可能性が高い」という経験則に基づいています。

もし、最後に使ったものを残すルールではなく、適当なファイルを捨てていたとしたら、次に使うファイルがたまたま捨てられてしまい、また引き出しから取り出す手間が発生します。LRUは、この「再利用されるまでの間隔」を予測することで、作業効率を最適化する仕組みです。

コンピュータシステムの基盤を支える知識

この考え方は、ITパスポートの範囲を超えて、実際のコンピュータの性能に直結する非常に重要な概念です。コンピュータの主記憶装置（メモリ）は、CPUと比較すると処理速度が遅いため、より高速なキャッシュメモリという領域を使います。キャッシュメモリは容量が限られているため、LRUなどのアルゴリズムを用いて、どのデータをメモリ上に保持し、どのデータを破棄するかを常に判断しています。

試験では、単純なパズル問題として出題されますが、本質的には「限られた枠をいかに賢く運用して、処理全体の効率を上げるか」という、システム設計におけるリソース管理の基礎を学んでいることになります。この考え方を理解しておくと、OSがどのように動いているのか、あるいはなぜブラウザのキャッシュをクリアすると表示が遅くなることがあるのかといった、技術的な背景がより深く納得できるようになります。

参考リンク

• 【ITパスポート】LRU方式（ページ置換アルゴリズム）
• LRUアルゴリズムを実装して理解する
• ページ置換アルゴリズム - Wikipedia