ページ置換アルゴリズムの計算ツール

正解：B. ベラディの異常

直感的には物理ページを増やせばページフォルトは減るはずですが、FIFO方式では、特定のアクセスの並びで、ページ数を3から4に増やすとフォルトがかえって増えることが知られています。これをベラディの異常といいます。LRUのように、ページ数を増やしても保持するページの集合が必ず前の集合を含む方式(スタックアルゴリズム)では起こりません。スラッシングはメモリ不足で置き換えが続く状態、コピーオンライトは書き込み時に複製する方式です。

正解：B. 5回

順に追うと、A(ミス、[A])、B(ミス、[A,B])、A(ヒット、Aが最近)、C(ミス、最も古いBを追い出し[A,C])、B(ミス、最も古いAを追い出し[C,B])、A(ミス、最も古いCを追い出し[B,A])となり、ミスは5回です。4回とするのは、Cを入れるときにAを追い出したと誤った場合などの数え方で、LRUではヒットしたAが新しくなっている点が大切です。6回は3回目のAのヒットを見落とした数です。

正解：B. 実現できないが、他の方式のミス数の下限を示す基準になる

最適置き換え(ベラディのOPT)は、将来のアクセスの順番が分かっているとして、次に使われるのが最も先のデータを追い出す方式で、ミス数が理論上最小になります。しかし実際のハードウェアは未来のアクセスを知ることができないため実現できず、記録したアクセスの並びに当てはめて、LRUなどの方式がどれだけ最適に近いかを評価するのに使います。LRUとは追い出すデータが違うので、ミス数は一般に異なります。

正解：B. アクセスしたページが、物理メモリに割り当てられていないとき

ページフォルトは、アクセスしたページのページテーブルの項目が無効、つまり物理メモリに割り当てられていない(ディスクに追い出されている、まだ読み込んでいないなど)ときや、読み出し専用のページに書き込むような許されないアクセスをしたときに起こる例外です。OSがページを用意して命令をやり直します。キャッシュミスはハードウェアだけで処理され、例外にはなりません。TLBにあればすぐ変換できるので、フォルトは起きません。