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

この問題は、LRU（Least Recently Used：最も長い間使われていないものを追い出す）アルゴリズムの動きを追跡するシミュレーション問題です。机上の空きがなくなった状態で新しいファイルが必要になったとき、過去の参照履歴の中で一番古いものがどれかを特定するのがポイントです。

ステップ・バイ・ステップで追い出すファイルを特定する

机の上には最大4冊までファイルが置けます。参照の順序に従って、机上の状態を左から古い順（最後に参照してからの時間が長い順）に並べて変化を追います。

1. A, B, C, D を参照：机上は [A, B, C, D]
2. E を参照：机上は満杯なので、最も古いAを追い出し、Eを追加 [B, C, D, E]
3. C を参照：既に机上にあるので順序を更新。Cが最新になる [B, D, E, C]
4. B を参照：既に机上にあるので順序を更新。Bが最新になる [D, E, C, B]
5. D を参照：既に机上にあるので順序を更新。Dが最新になる [E, C, B, D]
6. F を参照：机上は満杯なので、最も古いEを追い出し、Fを追加 [C, B, D, F]

この手順で最後に引き出しにしまわれたファイルはEとなります。

LRUアルゴリズムとは何か

LRUはメモリ管理やキャッシュメモリの制御において非常によく使われるアルゴリズムです。コンピュータは処理速度を上げるために、よく使うデータを高速なメモリ（キャッシュ）に一時保存します。しかし、保存できる容量には限りがあるため、新しいデータを読み込む際には、不要になった古いデータを捨てる必要があります。

このとき「人間は一度使ったデータを、しばらくしてもう一度使う可能性が高い」という経験則に基づき、「一番長い間使っていないデータは、今後もしばらく使わないだろう」と予測して置き換えを行うのがLRUの考え方です。

実社会での活用と教育的意図

この概念は、身近なところではWebブラウザのキャッシュ機能に活用されています。例えば、頻繁に閲覧するWebサイトの画像やスクリプトを端末内に保存しておき、次回アクセス時に通信量を減らして高速表示させる仕組みです。ここでLRUが働くことで、最近見ていない古いキャッシュから順に破棄され、効率的なストレージ管理が実現されています。

また、ITパスポート試験でこの問題が出題される背景には、ITシステムの「効率化」に対する考え方を理解してほしいという意図があります。メモリやCPU、ネットワーク帯域といった限られた資源を最適に運用するためのアルゴリズムを学ぶことは、システムエンジニアとして基礎的な教養となります。

参考リンク

• 【ITパスポート】LRU方式のキャッシュメモリの仕組みを解説
• LRUキャッシュをPythonで実装して遊んでみる
• ページ置換アルゴリズム - Wikipedia