仮想記憶とページング方式

仮想記憶とは、プログラムが扱うアドレス空間を主記憶の大きさに縛られずに広く見せ、実際に使う部分だけを主記憶に置く仕組みである。ページング方式は、仮想アドレス空間と主記憶をともに同じ大きさの固定長の単位に分けて管理する方式であり、仮想側の単位をページ、主記憶側の単位をページフレームと呼ぶ。試験では、ページフォールトの処理の流れ、ページ置換えのアルゴリズム、他方式との比較が中心的に問われる。

原理と仕組み

プログラムが参照した仮想アドレスは、ページ番号とページ内の位置に分けられ、ページ番号を使ってページテーブルを引くことで主記憶上の位置を求める。参照したページが主記憶上にないとページフォールトが発生し、OSはそのページを補助記憶から読み込む。この読み込みをページインと呼ぶ。空いているページフレームがない場合は、主記憶上のページを一つ選んで追い出す必要があり、この追い出しをページアウトと呼ぶ。ページ置換えとは、この追い出すページを決める手続きである。需要ページングでは、ページフォールトを契機として必要なページフレームが割り当てられる。

ページング方式は主記憶を同じ大きさのページフレームに分けて割り当てるため、空き領域が離れて点在していても配置でき、外部断片化は発生しない。 ただし、ページの大きさに満たない末尾の未使用部分が生じるため、内部断片化はあり得る。この点も外部断片化との違いとして押さえておく必要がある。

判断の基準と数値

ページ置換えの代表的なアルゴリズムがLRUである。LRUは、最後に参照されてから最も長い時間が経過したページを置換対象とする方式であり、直近に使われたページは残すという考え方に基づく。 参照列が与えられた問題では、各ページフレームの最終参照時刻を参照のたびに更新し、最も古いものを選んで追い出すという手順で追跡する。

ページフォールトの回数との関係も判断の基準になる。通常のページングでは、ページフォールトが起きると必要なページを補うためページインが発生するため、ページフォールトの回数とページインの回数は等しい。ページアウトは置き換えるページがあり、かつそれを書き戻す必要がある場合に限られるため、その回数はページイン以下となる。