問題
応用情報技術者 平成29年春期 午前問16
4ブロック分のキャッシュメモリC0～C3が表に示す状態である。ここで，新たに別のブロックの内容をキャッシュメモリにロードする必要が生じたとき，C2のブロックを置換の対象とするアルゴリズムはどれか。
| キャッシュメモリ | ロード時刻（分：秒） | 最終参照時刻（分：秒） | 参照回数 |
| C0 | 0:00 | 0:08 | 10 |
| C1 | 0:03 | 0:06 | 1 |
| C2 | 0:04 | 0:05 | 3 |
| C3 | 0:05 | 0:10 | 5 |
- FIFO
- LFU
- LIFO
- LRU
答え
LRU
解説
キャッシュアルゴリズム
キャッシュアルゴリズムとは、コンピュータ上で最近使った情報を保存しているキャッシュがいっぱいになってしまった時に、どのデータを捨てるのかを判断するアルゴリズムです。
最も効率的なキャッシュアルゴリズムは、今後長期に渡って必要とされないデータを常に捨てていくものである。この理想的アルゴリズムは、Laszlo Belady の最適アルゴリズム、あるいは千里眼置換アルゴリズムなどと呼ばれる。実際には、あるデータを将来に渡ってどれだけ必要としないかを予測することは不可能であり、このアルゴリズムは一般には実装できない。実用上の最適解は実験して初めて得られ、実際のキャッシュアルゴリズムとその最適解との効率を比較することは可能である。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
単純なアルゴリズムとして、FIFO（First In First Out）、LIFO（Last In First Out）、LFU（Least Frequently Used）、LRU（Least Recently Used）がありますが、どのアルゴリズムが最適かは事前にはわかりません。
FIFO（First In First Out）
一番最初に読み込んだブロックを置き換えます。
今回はC０が該当します。
LIFO（Last In First Out）
一番最後に読み込んだブロックを置き換えます。
今回はC3が該当します。
LFU（Least Frequently Used）
参照頻度の最も低いブロックを置き換えます。
今回はC1が該当します。
LRU（Least Recently Used）
最後に参照されてから最も時間の経つブロックを置き換えます。
今回はC2が該当します。