平成28年度 秋期 午前 問18

✓ これが正解イ10

解説

12回の参照のうちヒットは2回、残りが外れです。

LRU は、最も長く使われていないものを追い出す置換えの方式です。枠の中身を、古く使ったものから新しく使ったものへ並べて書き出すと数え間違いが減ります。参照の列を順に追います。最初の 0、1、2 は空いている枠に入るので三つとも外れで、この時点で枠は埋まります。次の 3 では最も古い 0 が出ていき、4 では 1 が、そのあとの 0 では 2 が、続く 2 では 3 が出ていきます。ここまでで外れは七つです。八手目の 4 は枠の中にあるのでヒットとなり、中身は変わらず並び順だけが新しい側へ動きます。続く 3 では 0 が、1 では 2 が追い出されて外れが九つになります。十一手目の 4 も枠の中にあるので二度目のヒットです。最後の 5 で 3 が追い出され、外れは十になります。検算はヒットを数えるほうが速く、12 回のうちヒットは 2 回なので、12 から 2 を引いて 10 と一致します。プログラムの大きさが 6 ページであることは枠の数とは別の条件で、枠は 3 ページのままです。

ほかの選択肢はなぜ違うのか

• ア9：枠の中にあった参照を三つと数えた場合の値です。同じページが後からもう一度現れて枠に残っている場面は、八手目と十一手目の二つしかありませんから、12 回から差し引ける回数も二つまでです。
• ウ11：枠の中にあった参照を一つしか数えなかった場合の値です。同じページが後からもう一度現れる箇所が二か所あるので、参照の列を最後まで追えば見つかる回数は二つになります。
• エ12：参照した 12 回すべてで枠に無かったと数えた値です。異なるページが 6 種類あっても枠が 3 ページ分あるため、直前までに使ったものが残っている場面が生じ、すべてが外れになることはありません。