基本情報 平成21年度 秋期 問20：テクノロジ系に関する問題

答えは b です。

キャッシュメモリは「最近使ったデータをためておく速い棚」。でも棚がいっぱいになったら、何かを捨てて新しいものを入れる必要があります。そのとき「最近一番使われてないやつから捨てよう」というルールがLRU（Least Recently Used）です。

つまり「最後に使われてから最も長く時間が経ったブロック」が次の置換対象。

👉 覚え方：LRU=「Least Recently Used」=「一番ご無沙汰なやつ」を捨てる。

ほかの選択肢：a「一定時間使ってない」だけだと判定基準が曖昧／c「参照頻度の最も低い」=LFU（別方式）／d「読み込んでから時間が経った」=FIFOで使う考え方（最近の参照を見ない）。

なぜこれが正解か

正解は b。LRU（Least Recently Used、最低使用頻度）は「最後に参照されてからの経過時間が最も長いブロック」を置換対象とするアルゴリズム。プログラムの参照局所性（最近使ったデータは近未来にも使われる傾向）に基づき、近未来に使われない可能性が高いブロックを追い出す合理性がある。

各選択肢の解説

• a「一定時間参照されていない」：基準時間が曖昧でLRUの定義と異なる。
• c「参照頻度の最も低い」=LFU（Least Frequently Used）。回数カウントで判定する別アルゴリズム。
• d「読み込んでから最も長い時間が経ったブロック」=FIFO（First In First Out）。読込み時刻で判定し、最近の使用状況を無視する。

覚え方・ひっかけ注意

置換アルゴリズムの比較：FIFO（古い順、単純）、LRU（最終参照時刻、ヒット率高）、LFU（使用頻度、長期常用データ向き）、ランダム（実装簡単、ハード実装多）、OPT/Belady（理論最適、未来を予知=理論値）。「LRUは最終使用時刻」「LFUは使用回数」を間違えないこと。

理論的背景

LRUは局所性原理（時間的局所性：最近使った場所は再アクセスされる傾向、空間的局所性：近接アドレスもアクセスされる傾向）に基づく経験則。厳密なLRUの実装には全エントリの最終使用時刻を管理するオーバーヘッドが大きいため、ハードキャッシュでは疑似LRU（PLRU、二分木で近似）、NRU（Not Recently Used、参照ビットR・更新ビットMで4クラス分類）が実装される。OSの仮想記憶ページ置換ではClock（Second Chance）アルゴリズム、Working Set Model、WSClock、LinuxはActive/Inactive LRUリスト＋reclaim watermarkで実装。理論上限のOPT/Beladyとの差をミスレートで測る評価が古典的研究テーマ。

実務での使われ方

CPUキャッシュ：L1〜L3はセットアソシアティブ方式（4-way、8-way、16-way等）＋PLRUが一般的。Webキャッシュ：Squid、VarnishはLRU-K（K回目の参照時刻を見る）やARC（Adaptive Replacement Cache、IBM特許）を採用。CDNはTinyLFU＋SLRUの組合せ（Caffeineライブラリで有名）。データベース：PostgreSQLは2Q（2-Queue）派生、MySQL InnoDBは改良LRU（midpoint insertion）でフルテーブルスキャンによるキャッシュ汚染を防ぐ。

試験での位置づけ

FE科目Aで置換アルゴリズム識別問題が頻出。応用情報・データベーススペシャリスト・エンベデッドシステムスペシャリストではキャッシュヒット率計算、Beladyのアノマリ（FIFOで容量増やすとミス増える現象）、Working Set計算、TLB（Translation Lookaside Buffer）との関連が問われる。

選択肢の発展補足

仮想記憶のページ置換：FIFO、LRU、LFU、OPT、Clock、Aging（参照ビット履歴を世代加算）。マルチレベルキャッシュではL1ミス→L2探索→L3探索→主記憶のヒット率階層計算、平均アクセス時間=T_L1+m_L1×(T_L2+m_L2×(T_L3+m_L3×T_mem)) のような式が頻出。Write Policy（Write-Through vs Write-Back、Write-Allocate vs No-Write-Allocate）、Coherence Protocol（MESI、MOESI、ディレクトリ方式）はマルチコア時代の必須知識。AIワークロードでは行列演算用にTensor Core＋専用キャッシュ階層が設計され、メモリ帯域がボトルネックになる「メモリウォール」問題が再燃している。