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

仮想記憶は、補助記憶装置を利用して、実際の主記憶の容量を超える大きさの記憶空間をプログラムに提供する仕組みである。ページング方式では、仮想記憶を固定長のページに、主記憶を同じ大きさのページフレームに分けて管理し、必要なページだけを主記憶に置く。この仕組みを理解する要点は、ページの対応づけ、ページフォールトとページの入れ替え、そして性能を落とす現象の三つである。

ページの対応づけと需要ページング

ページング方式では、仮想アドレスをページ番号とページ内の位置に分け、ページテーブルによってページ番号に対応する主記憶上のページフレームを求める。参照したページが主記憶にないときにページフォールトが発生し、OSは補助記憶から該当ページを読み込むためのページフレームを割り当てる。このように、実行中にページが必要になった時点で読み込む方式を需要ページングという。

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

必要な領域の大きさの計算

ページテーブルの大きさは、仮想アドレス空間に含まれるページ数に、1エントリの大きさを掛けて求める。仮想アドレス空間が2^Lバイト、ページサイズが2^Nバイト、エントリの大きさが2^Eバイトのとき、ページ数は2^(L−N)個となり、必要な領域は2^(L−N+E)バイトとなる。

この計算では、ページ数を求める際にページサイズで割るため指数から引き、エントリの大きさを掛けるため指数に加える。指数の符号の扱いを取り違えると、ページテーブルの大きさを誤って求めるため注意が必要である。

ページ置換えとページイン・ページアウト

主記憶のページ枠がすべて埋まっているときは、どのページを追い出すかを決める必要がある。LRU方式は、最も長い間参照されていないページを追い出す方式である。これに対しFIFO方式は、最も早く読み込まれたページを対象とするため、判断の基準が異なる。

LRUとFIFOの違いは、参照の履歴を基準とするか、読込みの順序を基準とするかにある。参照列を追い、主記憶にないページの読込みが発生する回数を数える問題では、枠の数と参照順から各時点の枠の内容を書き出すのが確実である。