平成24年度 秋期 午前 問19

✓ これが正解イ4

解説

数えるのは追い出しであって不足ではありません。

LRU 方式は、使われてから最も長く間があいているページを追い出す決まりです。頭の中で並べ替えると必ず順序が狂うので、参照ごとに枠の中身を左が古い順に書き出して追います。最初の四つは枠が空いているので、そのまま入って四つが埋まります。次の二つはすでに入っているので当たりとなり、順序が入れ替わるだけです。七番目でまだ入っていない番号が来て、ここで初めて誰かを押し出します。このとき最も長く使われていない番号が出ていき、これが一回目の追い出しです。続く二つはまた当たりで、十番目でもう一度押し出しが起き、十一番目と十二番目でも同じことが起きます。合わせて四回が答えになります。ここで肝心なのは、数える対象です。目当てのページが枠にないという状態は最初の四つでも起きていますが、そのときは空きがあるので誰も出ていきません。つまり足りなかった回数は八回ですが、ページアウト、すなわち追い出しの回数は四回です。参照かつ更新されるという断りは、押し出すときに書き戻しが必要なことを示しています。

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

• ア3：十一番目までを数えて打ち切るとこの回数になります。最後の参照でもまだ枠に入っていない番号が来るため、そこでもう一度押し出しが起こります。
• ウ5：枠が埋まった四番目の参照から後ろだけを取り出し、目当てが枠になかった回数を数えるとこの値です。四番目は空きに入るだけなので、押し出しの回数には加わりません。
• エ6：最後に使われた時刻ではなく、最初に読み込まれた順で追い出すやり方に取り替えて数えるとこの回数になります。途中の当たりが二回ぶん減り、押し出しがその分増えます。