ブロックの置換に関するアルゴリズム｜科目A-1 令和7年 秋期午前試験 問19
出典：令和7年秋期 午前 問19
分野：ソフトウェア ／ オペレーティングシステム
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
TSUNAGARU-ADVICE
まず押さえたいこと
キャッシュ置換アルゴリズムは、どのブロックを追い出すかを決めるルールです。C2を対象にするかは、ロード時間・最終参照時間・参照回数のどれを見る方式なのかで変わります。今回は、最終参照時間が最も古いものを選ぶ考え方がポイントです。
迷ったときの判断軸
FIFOは最も早くロードされたもの、LIFOは最も遅くロードされたもの、LFUは参照回数が最も少ないものを選びます。一方、LRUは最近最も使われていないものを選ぶため、最終参照時間が一番古いC2に注目します。どの列を見るアルゴリズムかを先に決めると混同しにくくなります。
科目Bにつなげるために
特にプロフェッショナルデジタルスキル（システム）試験合格を目指す方は、キャッシュ置換を単なる用語ではなく、メモリやストレージの性能に関わる設計判断として理解しておくと有効です。科目Bでは、アクセス履歴から置換対象を判断したり、キャッシュ効率を改善する考え方につながります。
キャッシュメモリの置換アルゴリズムでは、どのブロックを追い出して新しいブロックを格納するかを決めます。
LRUは、Least Recently Usedの略で、最も長い間参照されていないブロックを置換対象にする方式です。
表の最終参照時間を見ると、C0は0:08、C1は0:06、C2は0:05、C3は0:10です。この中で最も古い最終参照時間はC2の0:05なので、LRUではC2が置換対象になります。
したがって、エが適切です。
❌他選択肢が誤りの理由ア：FIFO
⇒FIFOは、First In First Outの略で、最も早くロードされたブロックを置換対象にする方式です。ロード時間が最も古いのはC0の0:00なので、FIFOではC0が置換対象になります。
イ：LFU
⇒LFUは、Least Frequently Usedの略で、参照回数が最も少ないブロックを置換対象にする方式です。参照回数が最も少ないのはC1の1回なので、LFUではC1が置換対象になります。
ウ：LIFO
⇒LIFOは、Last In First Outの略で、最も新しくロードされたブロックを置換対象にする方式です。ロード時間が最も新しいのはC3の0:05なので、LIFOではC3が置換対象になります。