ページング方式
32ビットのコンピュータでPAEなどを使わなければ、最大主記憶容量は4GBまでだが、その限界ぎりぎりまでRAMを搭載したシステムも珍しくない。IBM System/370 はXAモードでもアドレッシング可能な範囲は2GBまでだった。
ページングおよびスワップスペースはこの4GBの限界を超えて使うことができ、そのためにメモリアドレスではなくディスク上の位置でアドレス指定される。
リニアなアドレス空間の32ビットマシンでは、プログラムの仮想アドレス空間は4GBまでに制限されておりが、複数のプログラムでグループを形成すればその制限を越えることも可能である。個々の仮想アドレス空間の総和は、ページテーブルがサポートするプロセスID(または仮想空間ID)のビット数で制限される。
セグメントレジスタ(例えば、System/370のESAモードにおけるアクセスレジスタ)のあるマシンでは、アドレス空間の大きさはOSによってのみ制限され、マッピング用テーブルのサイズだけが問題となる。
結果として、各プログラムのページテーブルには、以下のようなマッピングが格納される(「プログラムのページ番号 → OSのページ番号」)。
プログラムA: 0 → 0、1 → 1、2 → 2
プログラムB: 0 → 3、1 → 4、2 → 7
プログラムD: 0 → 5、1 → 6
ここで、プログラムが自身に割り当てられたメモリにアクセスしようとしたときに何が起きるかを示す。プログラムA が "LOAD memory at 20FE"(20FE番地からロード)という命令を実行したとする。
20FE(16進数)を2進数表記すると(16ビットシステムでは) 0010000011111110 となる。ページサイズは4Kバイトとする。従って、20FE番地のメモリ参照要求を受けると MMU は以下のようにこのアドレスを見る。
ページサイズが4096バイトなので、MMUはアドレスの先頭(最上位桁ビット群)4ビットをページ番号、残りの12ビットをページ内相対メモリアドレスとして扱う。ページサイズが2048バイトなら、MMUは先頭5ビットをページ番号、残り11ビットをページ内相対メモリアドレスとして扱うだろう。
これを「ページアウト」と呼ぶ。そうでない場合、選択したページフレームの内容は二次記憶装置の所定の位置にあるものと同じなので、書き戻す必要がない。そのように使用中のページを奪った場合、もともとそのページを使っていたプロセスがそのページにアクセスしようとした場合、同様に空のページフレームを取得して、ページインする必要がある。
効率的なページングシステムは、空にすべきページフレームとして、短期間では必要とされなさそうなページを選択しなければならない。そのためのページ置換アルゴリズムには様々なものがある。多くのオペレーティングシステムは Least Recently Used (LRU) アルゴリズムに類するものを使うか(LRUそのものは現行のハードウェアでの正確な実装は困難である)、ワーキングセットベースのアルゴリズムを使っている。
さらに応答性を向上させるため、ページングシステムはどのページがすぐに必要とされるかを予測する様々な戦略を活用する。プログラムが参照する前に先行的にページをロードするシステムもある。
ページング方式では、実際のメモリアクセスはページテーブルを使用してメモリ管理ユニットがハードウェアレベルで制御する。前述の通り、物理メモリはページと呼ばれる小さなブロックに分割される。各ページにはページ番号が付与される。OSは未使用のページのリストを保持するか、メモリ使用要求があったときに毎回メモリを調べる(最近のOSでは前者の実装が一般的)。いずれにしても、プログラムがメモリを要求したとき、OSがそのプログラムに何ページかのメモリを割り当て、それをプログラム(プロセス)毎に割り当て中のページを管理するリストに入れておく(訳注:ページそのものはプログラムが使用するので、それをリストに入れるわけではなく、物理ページを管理するデータ構造を別途作成してリストに入れる)。具体例を以下に示す。
以下のような順番でページの割り当てが行われたときのページアロケーションリストをテーブルに示す。
プログラムAが3ページのメモリを要求
プログラムCが2ページのメモリを要求
プログラムDが2ページのメモリを要求
プログラムCが終了し、2ページが解放される
プログラムBが3ページのメモリを要求し、先にCが解放した2ページを割り当て、さらに残りの1ページを割り当てる