3つのページ枠をもつ主記憶に、ページ参照列 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 を与える。最初はすべての枠が空で、ページ置換アルゴリズムに FIFO を用いるとき、ページフォールトの回数はいくつか。

解説

正解は「9」です。FIFO では、最も古くに読み込まれたページを置き換えます。順に追うと、1, 2, 3 で3回、4 で1を、1 で2を、2 で3を、5 で4を置き換えてここまで7回です。続く1と2はヒットし、3 で1を、4 で2を置き換えて9回となり、最後の5はヒットします。「7」は、最も遠い将来まで使われないページを置き換える最適アルゴリズムの場合の回数です。「10」は、最も長く使われていないページを置き換える LRU の場合の回数です。この参照列は、FIFO で枠を4つに増やすとフォールトが10回に増える例（ビレイディの異常）としても知られています。「12」は、すべての参照でフォールトが起きると考えた値です。