平成30年度 III-13

解説

この問題で問われていること

ページ参照列に対して、LRUとFIFOで、ページの置換を順にシミュレートし、最終状態を求める問題。

解き方

① LRU: 最も長く使われていないページを追い出す(使うたびに順位を更新)。FIFO: 最も早く読み込んだページを追い出す(使っても順位は変わらない)。空いた枠に入れる
② LRU: P4がP0、P5がP2、P6がP3、P7がP1、P8がP5、P9がP6を追い出す → P4, P7, P8, P9。FIFO: P4がP0、P5がP1、P6がP2、P7がP3、P8がP4、P9がP5を追い出す → P8, P9, P6, P7
③ ②

正解が正しい理由

LRU(最も長い間使われていないページを追い出す)では、P0〜P3を読み込み(4面が埋まる)。P1は参照(ヒット)。P4でP0を追い出し、P5でP2を追い出し、P4はヒット。P6でP3を追い出し、P7でP1を追い出し、P6・P4はヒット。P8でP5を追い出し、P7はヒット。P9でP6を追い出す。最終状態は、上から順に、P4、P7、P8、P9。FIFO(最も早く読み込まれたページを追い出す)では、P0〜P3を読み込み、P1はヒット。P4でP0を追い出し、P5でP1、P4はヒット、P6でP2、P7でP3を追い出し、P6・P4はヒット。P8でP4を追い出し、P7はヒット。P9でP5を追い出す。最終状態は、P8、P9、P6、P7。したがって、LRU=P4、P7、P8、P9、FIFO=P8、P9、P6、P7の②が正しい。

各選択肢について

• ① FIFOの最終状態がP4、P7、P8、P9となっており、FIFOの計算結果と一致しない(これはLRUの結果)。
• ② LRU=P4、P7、P8、P9、FIFO=P8、P9、P6、P7で、正しい。これが正答。
• ③ LRUの並びが、P4、P8、P7、P9と、ページの配置(割当ての順序)が異なる。
• ④ LRUがP8、P9、P6、P7となっており、これは、FIFOの結果に近く、LRUの結果と一致しない。
• ⑤ LRUとFIFOがともにP8、P9、P6、P7となっており、LRUの結果と一致しない。

覚えるべきポイント

LRUは、ヒットしたページの参照履歴を更新する。FIFOは、ヒットしても順序は変わらず、読み込まれた順に追い出す。置換したページは、追い出されたページと同じ位置に入る。