キャッシュアルゴリズムは喫茶店で考えるとすぐ分かる！
FIFO・LRU・LFUを3人席で理解しよう
基本情報技術者試験では、キャッシュメモリの置換アルゴリズムとして
- FIFO
- LRU
- LFU
がよく登場します。
名前だけを暗記しようとすると、どれも似ていて混乱してしまいます。
そこで今回は、3人席しかない喫茶店を例に考えてみましょう。
コンピュータにも席数がある
喫茶店に席数があるように、コンピュータのキャッシュメモリにも容量があります。
今回は、席が3席しかない喫茶店を考えます。
最初は3人のお客さんが座っています。
席1 Aさん
席2 Bさん
席3 CさんそこへDさんが来店しました。
しかし、席は満席です。
誰か一人に席を譲ってもらわなければなりません。
この**「誰に席を譲ってもらうか」**を決めるルールが、キャッシュの置換アルゴリズムです。
FIFO（First In, First Out）
FIFOは
「一番早く来た人が席を譲る」
というルールです。
来店順が
① Aさん
② Bさん
③ Cさん
④ Dさん（新しく来店）だった場合、
一番早く来たAさんが席を譲ります。
退席：Aさん
残る人
Bさん
Cさん
DさんFIFOでは、途中で何回コーヒーを飲んだか、最近飲んだかは関係ありません。
来店した順番だけで決まります。
LRU（Least Recently Used）
LRUは
「一番最近利用していない人が席を譲る」
というルールです。
例えば、それぞれ最後にコーヒーを飲んだ時刻が
Aさん 10分前
Bさん 1分前
Cさん 今飲んだだったとします。
ここでDさんが来店すると、
一番長い間コーヒーを飲んでいないAさんが席を譲ります。
退席：Aさんもし来店順が一番古くても、最近コーヒーを飲んでいたなら退席しません。
LRUでは、
最後に利用した時刻
だけを見ています。
LFU（Least Frequently Used）
LFUは
「利用回数が一番少ない人が席を譲る」
というルールです。
例えば、
Aさん 10杯飲んだ
Bさん 3杯飲んだ
Cさん 1杯飲んだだった場合、
Dさんが来店すると、
利用回数が最も少ないCさんが席を譲ります。
退席：CさんLFUでは、
最近飲んだかどうかではなく、
これまで何回利用したか
だけを見ています。
違いを整理すると
| 方式 | 何を基準にする？ |
|---|---|
| FIFO | 一番早く来た人 |
| LRU | 最後に利用した時刻 |
| LFU | これまでの利用回数 |
基本情報技術者試験ではここを覚える
試験では、英語の略称を覚えるよりも、
「何を基準に入れ替えるのか」
を理解することが大切です。
- FIFO：来た順番を見る
- LRU：最後に使った時刻を見る
- LFU：利用回数を見る
この違いを理解できれば、問題文を読んでも迷いにくくなります。
まとめ
キャッシュの置換アルゴリズムは難しそうな名前ですが、考え方は意外とシンプルです。
3人席の喫茶店を思い浮かべれば、
「誰に席を譲ってもらうか」
というルールの違いだけだと理解できます。
試験では英語の略称を丸暗記するよりも、この場面をイメージしながら考えるほうが、ずっと記憶に残りやすくなります。