平成23年度 特別 午前 問21

✓ これが正解イFIFO＝3 ／ LRU＝6

解説

置き換えは枠が埋まった後だけ数え、3回と6回です。

問われているのは置き換えの回数であって、ページフォールトの回数ではありません。最初の三つの参照は空いている枠を埋めるだけですから、追い出されたページは一つもなく、数に入りません。ここを取り違えると、どちらの方式も三つ多く数えることになります。実記憶の枠は三つ、参照の並びは十回です。FIFO は枠に入った順番だけで追い出す相手を決め、途中でそのページを参照しても順番は動きません。1，3，2 が枠を埋め、次の 1 は枠にあるので何も起きず、4 で 1 が出て一回目、5 で 3 が出て二回目、2 は枠にあり、3 で 2 が出て三回目、残る 4 と 5 は枠にありますから、合計は三回です。LRU は最後に使ってから最も長く経った枠を追い出しますので、参照するたびに順番が動きます。二度目の 1 の参照で 1 が最も新しくなり、ここから FIFO と差が付きます。4 で 3 が出て、5 で 2 が出て、2 で 1 が出て、3 で 4 が出て、4 で 5 が出て、5 で 2 が出ますから、合計は六回です。後半の参照が 2，3，4，5 と規則的に回るため、最後に使ってから長く経った枠が、次に必要になるページと重なり続けるのです。したがって組合せは三回と六回になります。ページ置換えの方式は、新しく工夫されたものほど常に少なく済む、とは限りません。

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

• アFIFO＝3 ／ LRU＝2：前半の値は合っていますが、後半を二回としています。あとから工夫された方式のほうが常に有利だという思い込みから生まれる形で、実際に追い出したページを一つずつ書き出すと、後半は六回になります。
• ウFIFO＝4 ／ LRU＝3：どちらの値も、与えられた参照の並びからは導けません。枠に残っているページへの参照まで数え入れたり、順番の入れ替えを一部だけ反映したりすると生じる形です。追い出した相手を並べて確かめると合いません。
• エFIFO＝5 ／ LRU＝4：前半を五回、後半を四回としています。追い出したページを一つずつ書き出すと前半は三回、後半は六回になり、どちらの値も合いません。