仮想記憶とページ置換

仮想記憶とは、プログラムが使うアドレス空間を主記憶の実容量に縛られずに扱えるようにする仕組みであり、ページング方式ではアドレス空間を固定長のページに分けて主記憶と補助記憶の間で入れ替える。主記憶上に空きのページ枠がないときは、どのページを追い出すかを決めるページ置換えが必要になる。本単元では、ページフォールトの仕組み、置換えアルゴリズムと性能の計算、そして読み込み方式や現象の区別を順に整理する。

原理・仕組み

ページング方式では、プログラムの論理アドレス空間を一定の大きさのページに分け、主記憶も同じ大きさのページ枠に分けて管理する。参照したページが主記憶上になければページフォールトが発生し、OSはそのページを補助記憶から主記憶へ読み込む。この読み込みをページインと呼ぶ。ページフォールトは必要なページを補うための処理であるため、通常のページングではページフォールトの回数とページインの回数は等しくなる。

ページ枠に空きがない場合には既存のページを追い出す必要があり、その追い出しをページアウトと呼ぶ。ページアウトは、置き換えるページがあり、かつそのページを書き戻す必要がある場合に起きるため、ページインの回数を超えることはない。 一方、空きページ枠がある場合は、ページアウトを伴わずページインだけで処理が完了する。ページフォールトのたびに必ずページアウトが起きるわけではない点が、後で区別すべき要点である。

需要ページングでは、実行中に参照されたページを必要に応じて読み込むのが基本である。プログラムの実行開始時にコード領域全体を主記憶へ載せる必要はなく、ページフォールトを契機として、そのページを読み込むための主記憶が割り当てられる。

ページは固定長であるため、空き領域が離れていてもページ単位で配置でき、外部断片化は発生しない。ただし、最後のページに未使用部分が生じる内部断片化はあり得る。

判断の基準や数値

ページ置換えの代表的な基準がLRUである。LRUは、最後に参照されてから経過した時間が最も長いページを置換対象とする方式である。

LRUでは、各ページの最終参照時刻を比べて追い出すページを決める。例えば4つのページ枠に1、2、3、4の順で読み込んだ後、2、5、3、1、6、5と参照すると、途中でページ1、4、2が順に追い出される。 その結果、最後にページ4を参照する時点で最も長く参照されていないのはページ3となり、ページ4はページ3の枠に入る。