平成22年度 春期 午前 問18
システム構成要素
キャッシュメモリに関する問題
表のような状態の 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
解説
最終参照時刻が最も古い C2 を選ぶのは LRU です。
置換の問いは、四つの候補をそれぞれ表のどの列を見る規則かへ翻訳してから表を読むと、迷わずに片づきます。4 ブロック分のキャッシュメモリの状態として、いつ読み込んだかを示すロード時刻、いつ最後に使われたかを示す最終参照時刻、何回使われたかを示す参照回数の 3 列が与えられており、四つの候補はこの 3 列のいずれかに対応します。設問が聞いているのは C2 が追い出される相手になるのはどの規則か、という向きなので、四つとも実際に当てて確かめます。正解は LRU です。最も長く使われていないものを追い出す規則なので見るのは最終参照時刻の列で、C0 が 0 分 8 秒、C1 が 0 分 6 秒、C2 が 0 分 5 秒、C3 が 0 分 10 秒と並ぶ中でいちばん古いのは C2 になります。この表は四つの規則がそれぞれ別のブロックを指すように作られているので、四つ全部を出せば自分で答え合わせができ、逆にひとつでも取り違えると必ず別の候補へ着いてしまいます。
ほかの選択肢はなぜ違うのか
- アFIFO：最初に読み込んだものから順に追い出す規則なので、見るのはロード時刻の列です。いちばん早く読み込まれたのは 0 分 0 秒の C0 なので、追い出される相手が設問の指定しているブロックと違います。
- イLFU：使われた回数が最も少ないものを追い出す規則なので、見るのは参照回数の列です。最も少ないのは 1 回の C1 であり、3 回使われているブロックのほうには順番が回ってきません。
- ウLIFO：最後に読み込んだものから追い出す規則で、こちらもロード時刻の列を見ますが向きが逆です。いちばん遅く読み込まれたのは 0 分 5 秒の C3 なので、やはり指定されたブロックにはなりません。
この問題の用語
- キャッシュ一度取り寄せた内容を手元に置いて、次から早く使えるようにする仕組み。CPUとメモリの間や、ブラウザ、DNSなど、さまざまな場所で使われます。
- アルゴリズム問題を解くための、決まった手順や考え方そのものです。同じ問題でも手順によって、処理にかかる時間や必要な記憶量が変わります。
出典：平成22年度 春期 応用情報技術者試験 午前 問18
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）