情報処理試験を勉強していると、「LFUって何？LRUとどう違うの？」と混乱しがちです。この記事ではLFUの仕組みを日常の例え話で噛み砕き、試験での出題パターンまで一気に押さえます。
対象試験と出題頻度
LFU（Least Frequently Used）は、応用情報技術者試験で出題されるテーマです。
ページ置換アルゴリズムの比較問題として、FIFO・LIFO・LRUと並んで選択肢に登場します。
単独で深掘りされるより、4つのアルゴリズムをまとめて問う形式が定番です。
詳細をクリックして確認
応用情報技術者
★★★☆☆
ランクC（応用）余裕があれば覚える
用語の定義
LFU（Least Frequently Used）とは、一言で言うと
「使用回数が最も少ないデータを優先的に追い出すページ置換アルゴリズム」
のことです。
イメージとしては、「図書館の棚整理」です。
棚がいっぱいになったとき、貸出回数が最も少ない本を書庫に移して新刊のスペースを作る。LFUはまさにこの発想です。「何回使われたか」の累計カウントだけを見て、最も出番の少なかったデータを入れ替え対象にします。
📊 LFUの基本情報
| 項目 | 内容 |
|---|---|
| 英語名 | Least Frequently Used |
| 日本語の意味 | 最も使用頻度（回数）が少ないもの |
| 分類 | ページ置換アルゴリズム / キャッシュ置換アルゴリズム |
| 判断基準 | 各データの参照回数（累計カウント） |
解説
なぜページ置換アルゴリズムが必要なのか
記憶階層において、キャッシュメモリや主記憶は容量に限りがあります。新しいデータをロードする空きがなくなったとき、「どのデータを追い出すか」を決めるルールがページ置換アルゴリズムです。
代表的なアルゴリズムにはFIFO・LIFO・LRU・LFUの4種類があり、それぞれ追い出し対象の選び方が異なります。LFUは「参照回数」に着目する点が最大の特徴です。
LFUの動作フロー
LFUの処理は3ステップで完結します。
LFUの動作フロー
※参照回数が同数のブロックが複数ある場合の処理は問題文で指定される
図解：LFUによる置換の具体例
キャッシュメモリC0〜C3に4つのブロックが格納されている状態を考えます。
新たなブロックをロードする必要が生じたとき、LFUはどのブロックを追い出すのか、参照回数の棒グラフで視覚的に確認してください。
キャッシュメモリの状態
| ブロック | ロード時刻 | 最終参照時刻 | 参照回数 |
|---|---|---|---|
| C0 | 100 | 180 | 5 |
| C1 | 120 | 190 | 1 |
| C2 | 130 | 160 | 3 |
| C3 | 150 | 200 | 8 |
参照回数の比較（棒グラフ）
▲ LFUは参照回数が最小の C1 を追い出し対象とする
ここがポイントです。LRUなら「最終参照時刻が最も古い C2」が追い出されますが、LFUは最終参照時刻を見ません。あくまで累計の参照回数だけで判断します。
4つのアルゴリズム比較
LFUを正しく位置づけるには、他の3つと「何を基準に追い出すか」で整理するのが近道です。
| アルゴリズム | 正式名称 | 追い出し基準 | 上の例での対象 |
|---|---|---|---|
| FIFO | First In First Out | ロード時刻が最も古い | C0 |
| LIFO | Last In First Out | ロード時刻が最も新しい | C3 |
| LRU | Least Recently Used | 最終参照時刻が最も古い | C2 |
| LFU | Least Frequently Used | 参照回数が最も少ない | C1 |
ここだけは確実に押さえてください。LRUは「最後にいつ使ったか（時刻）」、LFUは「合計何回使ったか（回数）」です。英語の”Recently”と”Frequently”の違いがそのまま判断基準の違いに直結しています。
では、この用語が試験でどのように出題されるか見ていきましょう。
💡 LFUの核心を3行で
・「参照回数」が最小のデータを追い出すアルゴリズム
・LRU（最終参照時刻）やFIFO（ロード順）とは判断基準が異なる
・英語の Frequently（頻度）がそのままキーワード
試験ではこう出る！
LFUは、応用情報技術者の午前問題でページ置換（キャッシュ置換）アルゴリズムの比較問題として繰り返し出題されています。LFU単独で正解になるパターンは少なく、4つのアルゴリズムの中から条件に合うものを選ばせる形式が大半です。
📊 過去問での出題実績
| 試験回 | 出題内容 | 問われたポイント |
|---|---|---|
| AP R7秋 午前 問19 |
C0〜C3のキャッシュメモリでC2を置換対象とするアルゴリズムを選ぶ問題。 | ・正解はLRU（最終参照時刻が最古のC2） ・LFUなら参照回数最小のC1が対象 |
| AP H29春 午前 問16 |
上記R7秋 問19と同一構成の問題（流用）。 | ・FIFO/LFU/LIFO/LRUの4択は試験回をまたいで繰り返し出題される定番パターン |
| AP H22春 午前 問18 |
同一形式。キャッシュブロックの状態表を見て、指定ブロックを追い出すアルゴリズムを選ばせる。 | ・3回にわたって同一問題が流用されている ・表の読み方を練習すれば確実に得点できる |
📝 出題パターンと攻略法
パターン：「指定ブロックを置換対象とするアルゴリズムはどれか」
ロード時刻・最終参照時刻・参照回数の3列がある表を読み、FIFO/LIFO/LRU/LFUのどれが該当するかを選ぶ形式です。各アルゴリズムが「どの列」を見るかさえ分かっていれば、表を上から照合するだけで正解にたどり着けます。
ひっかけポイントは、LRUとLFUの混同です。「Recently（最近）＝時刻」「Frequently（頻繁に）＝回数」と英単語で覚えておけば間違えません。試験ではここまででOKです。
【確認テスト】理解度チェック
ここまでの内容を理解できたか、簡単なクイズで確認してみましょう。
Q. キャッシュメモリのブロック置換アルゴリズムにおいて、LFU方式の説明として最も適切なものはどれでしょうか？
- A. 置換え対象の中で、参照された回数が最も少ないブロックを置換え対象とする。
- B. 置換え対象の中で、最後に参照された時刻が最も古いブロックを置換え対象とする。
- C. 置換え対象の中で、最も先にロードされたブロックを置換え対象とする。
正解と解説を見る
正解：A
解説：
LFU（Least Frequently Used）は、参照回数の累計が最も少ないブロックを追い出し対象とするアルゴリズムです。”Frequently”が「頻度＝回数」を意味する点がそのまま判断基準になっています。
選択肢BはLRU（Least Recently Used）の説明です。LRUは「最終参照時刻」が最も古いものを対象とするため、回数ではなく時刻を基準にしている点がLFUとは異なります。選択肢CはFIFO（First In First Out）の説明です。FIFOは「ロード順」だけで判断するため、参照時刻も参照回数も考慮しません。
よくある質問（FAQ）
Q. LFUで参照回数が同じブロックが複数ある場合はどうなりますか？
LFUの仕様だけでは一意に決まりません。実際のOS実装ではLRUと組み合わせて「参照回数が同数なら最終参照時刻が最も古いものを追い出す」とする方式や、FIFOで先にロードされた方を追い出す方式があります。IPA試験では、参照回数の同数が発生しないように表が設計されているか、問題文で追加ルールが明記されるため、深追いは不要です。
Q. LFUは仮想記憶のページ置換だけで使われるのですか？
いいえ。LFUはキャッシュメモリの置換、Webブラウザのキャッシュ管理、CDN（Content Delivery Network）のキャッシュポリシーなど、「限られた容量にデータを保持し、溢れたら入れ替える」あらゆる場面で使われます。IPA試験ではキャッシュメモリまたは仮想記憶の文脈で出題されますが、考え方はどの場面でも同じです。
Q. LFUにはデメリットはありますか？
あります。LFUは過去の参照回数を「累計」で記録するため、かつて大量に参照されたが今は使われていないデータがいつまでもキャッシュに残り続ける問題（キャッシュ汚染）が起こり得ます。この弱点を補うために、一定時間ごとにカウンタを減衰させる「エージング」や、参照回数の代わりに直近の一定期間内の参照頻度を使う改良版（LFU-DA, Window-LFUなど）が実務では採用されています。
Q. 基本情報技術者試験でもLFUは出題されますか？
出題されます。FE H25春 午後問2ではページ置換アルゴリズムとしてLFUが登場し、参照列に基づいてページフォルト回数を計算させる問題が出ました。また、FE H17秋 午前問27やFE H21春 午前問20でもFIFO・LRUとセットで選択肢に含まれています。応用情報の過去問がそのまま基本情報に流用されるケースも多いため、対策は共通です。
