メモリ階層と性能
最も長い間使われていないものを追い出すLRUに対して、今後最も長い間使われないものを追い出す方式(最適置き換え、OPT)についての説明として正しいものはどれか。
- A実際のキャッシュで広く使われている、最も一般的な置き換え方式である
- B実現できないが、他の方式のミス数の下限を示す基準になる
- Cどんなアクセスの並びでもLRUとまったく同じミス数になる
答えと解説を見る
正解：B. 実現できないが、他の方式のミス数の下限を示す基準になる
最適置き換え(ベラディのOPT)は、将来のアクセスの順番が分かっているとして、次に使われるのが最も先のデータを追い出す方式で、ミス数が理論上最小になります。しかし実際のハードウェアは未来のアクセスを知ることができないため実現できず、記録したアクセスの並びに当てはめて、LRUなどの方式がどれだけ最適に近いかを評価するのに使います。LRUとは追い出すデータが違うので、ミス数は一般に異なります。
- A. 未来を知る必要があるため、実際のキャッシュでは使えません。
- B. 正しい。実現はできませんが、ミス数の下限を示す基準になります。
- C. 追い出すデータが違うため、ミス数は一般に異なります。