ページテーブル
実行中プログラムが仮想アドレス 0xD09FBABE のメモリにアクセスしようとしているとする。この仮想アドレスはふたつの部分に分けられる。「ページ番号」0xD09FBとそのページ内「オフセット」0xABEである(ページサイズが4Kバイトの場合)。
仮想記憶をサポートするハードウェアでは、このアドレスをTLB内で検索する。TLBはこのような検索を並列に実行できるよう特別に設計されており、この処理は非常に高速である。ページ番号0xD09FBと適合するエントリがTLBにある場合(TLBヒット)、物理フレーム番号をそこから取り出し、オフセットを加えてメモリアクセスが継続される。しかし、適合するエントリがなかった場合(TLBミス)、第二段階の処理としてページテーブルが使用される。
ハードウェアが仮想ページに対応する物理フレームを見つけられない場合、ページフォールトと呼ばれるプロセッサ割り込みを発生させる。オペレーティングシステムがページフォールトを扱う割り込みハンドラを実装する機会が提供されている。そのハンドラはページテーブルを参照してアドレスのマッピングを探す。もしマッピングが存在すれば、それをTLBに書き込み、問題の命令を再度実行することでメモリアクセス処理が再開される。
ページテーブル参照が失敗する場合として以下の2つが考えられる:
そのアドレスにマッピングが存在しない。つまり、そのメモリ参照が不正である場合。
そのページが物理メモリ(一次記憶)に存在しない。つまり、一次記憶に空きがない場合。
逆引きページテーブルは物理メモリ内の全フレームに関するマッピングのリストを保持している。しかし、仮想ページ毎にマッピングを保持するページテーブルを作成するのも自然な考え方のひとつと言える。ただし、仮想アドレス空間が大きくかつ複数存在するため、非常に大きな無駄なデータ構造となりうる可能性がある。そのため、ある仮想空間の領域をカバーするページテーブルを作成する。例えば、4Kページ1024個ぶんの領域をカバーすれば、4Mバイトの仮想メモリをマッピングできる。
仮想空間の両端(アドレス 0x0 の付近と最大アドレスの付近)をプロセスが使用することが多いため、このような部分的な仮想空間をカバーするページテーブルは便利である。例えば、仮想アドレスの小さい方をテキストとデータに使用し、大きい方をスタックに使用する(データセグメントとスタックセグメントがそれぞれ仮想空間の真ん中に向かって成長する)。多段ページテーブルでは小さなページテーブルをいくつか使って使用中の仮想空間の領域だけをカバーし、本当に必要なときだけ追加のページテーブルを作成する。
このような小さなページテーブルは上位のページテーブルにリンクされ、全体として木構造を形成する。2段である必要はなく、それ以上の段数になることもありうる。
この手法では仮想アドレスは(最低でも)3つの部分に分割される。上位ビットのほうから、ルートページテーブルのインデックス、サブページテーブルのインデックス、ページ内オフセットとなる。