仮想記憶のページング管理

ページング方式の仮想記憶は、仮想アドレス空間と主記憶を同じ大きさの固定長の単位（ページ）に分けて管理する方式である。プログラムの実行に必要なページだけを主記憶に置き、参照したページが主記憶にない場合にページフォールトを発生させて補助記憶から読み込む。管理の要点は、いつページを読み込むか、主記憶が満杯のときどのページを追い出すか、そして処理能力の急激な低下をどう防ぐかの三つである。

ページの読込みと主記憶の割当て

需要ページング方式では、実行中に参照されたページが主記憶にないときに、そのページフォールトを契機として必要なページを読み込む。 読込み先のページ枠は、このフォールトが発生した時点で割り当てられ、空きがなければ既存のページを追い出して確保する。したがって、実行開始時にプログラム全体を主記憶へ載せる必要はなく、参照されない部分は主記憶に載らないことがある。不正なアドレスの参照は、ページの読込みではなくエラーとして扱われる。

一方、プリページングは、将来必要になると予想したページをあらかじめ主記憶へ読み込んでおく方式である。 参照された時点で補助記憶へアクセスする待ち時間を減らせるが、予想が外れた場合には使われないページを読み込んだ分の転送と主記憶の領域が無駄になる。主記憶に十分な余裕がある環境では、この無駄の影響が小さいため、プリページングの利点が生きやすい。

ページ置換えの判断基準とLRU方式

主記憶のページ枠がすべて使われている状態で新たなページを読み込む場合、既存のページを一つ選んで追い出す必要がある。LRU方式は、最後に参照されてから最も長い時間が経過したページを置換えの対象とする方式である。 直近に使われたページは再び参照される可能性が高いという考えに立ち、使われなくなって久しいページを残さないようにする。例えば、ページ枠が四つで参照順が1、2、3、4、2、5であれば、ページ1が最も古く参照されているため、5を読み込むときに追い出される。

試験では、各枠の最終参照の順を参照履歴から追跡して、次に追い出される枠を求める問題が出題される。 途中で既存のページが再び参照された場合に、最終参照の順が入れ替わる点が見落とされやすいため、参照のたびに順序を更新する必要がある。