ページテーブル(Page Table)とは、コンピュータのオペレーティングシステムにおけるページング方式の仮想記憶システムで使われるデータ構造であり、仮想アドレスと物理アドレスのマッピングを格納するものである。仮想アドレス空間はプロセス毎に割り当てられ、物理アドレスはシステム全体でRAMなどを配置するアドレスである。PC上でのウェブブラウザであれ、論文上のチューリングマシンであれ、プログラムの実行とは物理的な世界とコンピュータのメモリの間でデータを転送し、メモリ上のデータを変換する処理である。情報工学では、プログラムは命令列であり、プロセスはその命令列にしたがって処理を行うことを意味する。メモリは物理的にはさまざまな構成が考えられる。例えば、長い紙テープやディスク上の磁気、マイクロチップ上の小さなキャパシタの配列などがある。1950年代、コンピュータが複雑化するにしたがって、さまざまな種類のメモリが接続されるようになってきた。どのメモリにどのようなデータを格納するかを管理するのが複雑化し、特に同時に複数のプロセスを実行する場合にそれが顕著となってきた。有益な単純化として仮想記憶が開発された。オペレーティングシステムと呼ばれるプログラムがデータの物理的配置を管理し、性能と信頼性を保証するためにそれらデータを移動させる。ユーザーレベルのプログラムのために、オペレーティングシステムが簡素化した仮想記憶空間を作り出す。仮想記憶上で動作するプロセスはデータの物理的配置を気にする必要がなくなり、一次記憶装置の割り当てを自らが制御する必要がなくなった。他のプロセスを気にすることなく仮想空間を必要なだけ使用する自由を得たのである。プログラムは(単純化すれば)以下の2つの部分から構成される:プログラム実行時、オペレーティングシステムはプログラムのテキスト部とデータ部を仮想アドレス空間にマップし、メモリ上の命令を実行する(ノイマン型参照)。しかし、実際にプログラムを実行すると、一時的なデータを格納する必要が生じるし、さらに重要な点としてサブルーチンを呼び出すときに現在のルーチンの状態をセーブする必要が出てくる。そのような目的のためにスタックにデータを格納し、サブルーチンの実行が完了したときにはそれらデータが不要になるので、スタックのデータ構造としての特性として自然に不要なデータを "pop" 操作で捨てることができる。つまり、スタックはプログラムの実行に伴って動的に成長する。オペレーティングシステムはテキスト、データ、スタックをそれぞれ別個の領域に分けてセキュリティと信頼性を確保する。これを「セグメント」と呼ぶ（セグメント方式参照）。例えば、スタックが大きくなりすぎてテキストセグメントやデータセグメントを上書きしそうになった場合、上書きする前にそれを検出することができる。全ての情報がスタックに格納できるわけではない。例えばワードプロセッサプログラムを考えてみよう。最初に文書を格納する小さなメモリ領域を確保するが、ユーザーが文書をさらに入力すると、その領域を成長させなければならない。スタックは基本的に固定サイズのメモリ領域の確保に適しており、このような成長するメモリ領域には適していない。このため、プログラムのデータセグメントを拡張して、文書を格納できるだけのメモリ領域を確保する(動的メモリアロケーション、ヒープ領域参照)。したがってデータセグメントも動的に成長したり縮小したりする。一次記憶は有限である。つまり、データを格納するのに使える場所が有限個であることを意味する。最近のコンピュータアーキテクチャでは、リニア(線形)なインデックスで記憶位置を示す。メモリの先頭にインデックスが0の場所があり、その後にインデックスが1ずつインクリメントされてメモリの最後まで続く。このメモリ上の位置を「アドレス」と呼ぶ。例えば、16メガバイトの一次記憶があれば、アドレスは 0 から 16777215 までとなる。技術的な文脈では十六進記数法を使ってアドレスを表現することが多く、C言語風の記述をすれば16Mバイトのメモリのアドレスは 0x0 から 0xFFFFFF となる。コンピュータ・アーキテクチャは、単に32ビットとか64ビットなどと表現されることがある。これは例えば32ビットアーキテクチャのコンピュータが処理できる数の最大値が32ビットで表現できることを意味する。これを「ワード長」と呼ぶ。コンピュータが利用できる物理メモリのサイズもこのワード長に制限される。32ビットコンピュータが使用できるアドレスの範囲は 0 から 4294967295 (formula_1) であり、4ギビバイトのメモリを使用できる。この事実は後の説明で重要となる。プログラム実行時、情報を格納する何らかのメモリが必要となる。プログラムは計算に使用する数値変数を格納するかもしれないし、会計アプリケーションで顧客情報をデータとして格納するかもしれない。多くのコンピュータではメモリを以下のように構成する:仮想アドレッシングでは、物理メモリのアドレスとプログラムがデータのロード/ストアでアクセスするアドレスを分離する。この分離の一般的な実現方式としてページング方式がある。オペレーティングシステムは使用していない命令やデータを「二次記憶」に移して、一次記憶を別の用途に使うことで効率的なメモリの利用を実現する。元のプロセスがその命令やデータを指す仮想アドレスを参照しようとしたとき、オペレーティングシステムは物理メモリを再確保して(必要ならばその内容を一次記憶から二次記憶へ追い出して)命令やデータを一次記憶に戻す。オペレーティングシステムがアプリケーション群を動作させるために常に一次記憶と二次記憶の間でデータ転送しなければならないとしたら、システムの性能は低下する。これをスラッシングと呼ぶ。仮想アドレッシングには他にも利点がある。重要な利点のひとつとして、各プロセスはオペレーティングシステムが仮想アドレス空間にマッピングした物理メモリにのみアクセス可能という特徴がある。これにより、あるプロセスが他のプロセスのデータを上書きすることを防ぐ。他の利点として、オペレーティングシステムが不正なアドレスへの参照を検出できる点があげられる(例えば、物理メモリが対応していないアドレスへのアクセスや、リードオンリーの場所への書き込みなど)。仮想アドレッシングと二種類の記憶装置の組合せを仮想記憶と呼ぶが、これは誤解されやすい名称でもある。ワード長が32ビットのコンピュータについて考えてみる。アドレス範囲は 0x00000000 から 0xFFFFFFFF までの 4Giバイトとなる。このアドレス範囲が仮想アドレス空間となる。仮想記憶を使用しない場合、物理メモリが16Miバイトしかないなら 0x01000000 以上のアドレス範囲は不正なアドレスとなる。しかし、多くのプログラムは4Gバイトのメモリを一度に全部使用するわけではない(参照の局所性、ワーキングセット参照)。例えば、あるプログラムはテキストとデータとスタックの最大値を合計しても1メガバイトに満たないだろう。4Giバイトのアドレス空間はあるサイズのかたまり(一般的には4Kiバイト)に分割される。このかたまりを「ページ」と呼ぶ。物理メモリも同じサイズに分割される。こちらは「フレーム」と呼ぶ。例えば、プログラムのテキストセグメントはアドレス 0x00000004(ページ番号 0x0、ページ内オフセット 0x4)からスタートするかもしれないが、対応する物理アドレスは 0xFF0E0004(フレーム番号 0xFF0E、フレーム内オフセット 0x4)かもしれない。仮想記憶システムが行うことは、仮想アドレスを物理アドレスに変換することで、基本的にはページとフレームにマッピングすることである。ページテーブルはそのために使われる。多くのアーキテクチャでは仮想記憶を直接ハードウェアでサポートする「トランスレーション・ルックアサイド・バッファ(TLB)」を持っている。TLBはページとフレームのマッピングを格納し、仮想記憶システムを完全にソフトウェアで実装した場合に比較してハードウェアでのページ-フレーム変換を高速化して全体の性能を向上させる。しかし、TLBは一定数のページ-フレームマッピングしか保持できない。これをソフト的に拡張し、多くのマッピングを保持するのは仮想記憶システムの役割である。仮想記憶システムは「ページテーブル」を使ってこれを行う。なお、「ページ」と「フレーム」という名称の区別をしないで、「仮想ページ」、「物理ページ」と呼ぶこともあるし、「フレーム」を「ページフレーム」と呼ぶこともある。実行中プログラムが仮想アドレス 0xD09FBABE のメモリにアクセスしようとしているとする。この仮想アドレスはふたつの部分に分けられる。「ページ番号」0xD09FBとそのページ内「オフセット」0xABEである(ページサイズが4Kバイトの場合)。仮想記憶をサポートするハードウェアでは、このアドレスをTLB内で検索する。TLBはこのような検索を並列に実行できるよう特別に設計されており、この処理は非常に高速である。ページ番号0xD09FBと適合するエントリがTLBにある場合(TLBヒット)、物理フレーム番号をそこから取り出し、オフセットを加えてメモリアクセスが継続される。しかし、適合するエントリがなかった場合(TLBミス)、第二段階の処理としてページテーブルが使用される。ハードウェアが仮想ページに対応する物理フレームを見つけられない場合、ページフォールトと呼ばれるプロセッサ割り込みを発生させる。オペレーティングシステムがページフォールトを扱う割り込みハンドラを実装する機会が提供されている。そのハンドラはページテーブルを参照してアドレスのマッピングを探す。もしマッピングが存在すれば、それをTLBに書き込み、問題の命令を再度実行することでメモリアクセス処理が再開される。ページテーブル参照が失敗する場合として以下の2つが考えられる:前者の場合、メモリアクセスが不正であるため、オペレーティングシステムはその問題に何らかの対処を必要とする。例えば、問題のプログラムにセグメンテーション違反のシグナルを送ったりする。後者の場合、ページの内容は別の場所、例えばディスク内に格納されている。これに対処するにはページの内容をディスクから物理メモリに持ってくる必要がある。物理メモリに空きがあれば問題はなく、単にページの内容を空き物理メモリ領域に書き込んで、ページテーブルのエントリを書き換えて、TLBに同じマッピングを書き込んで命令を再実行すればよい。しかし、物理メモリに空きがなく、使用可能なフレームがない場合、必要なページの内容を物理メモリ上に持ってくるために、別のページの内容をディスクに追い出す必要が生じる。そのフレームが使われていたページに対応するページテーブルのエントリを書き換えて「スワップアウト」されたことを示すようにし、逆に新たに持ってきたページに対応するページテーブルエントリに対応するフレーム番号を書き込む(当然ながら、TLBの処理と命令の再実行も必要)。このような処理を「スワッピング」と呼ぶ(プロセス全体のスワッピングのみをスワッピングと呼ぶこともある)。この処理はTLBだけ(あるいはメモリ上のページテーブル参照の場合も)のときに比べて非常に時間がかかる。どのページをスワップするかはページ置換アルゴリズムで決定される。設計上意図されたわけではないが、ページテーブルをルートキットで操作してソフトウェアのコードを隠すことができる。このような操作は検出が困難であり、不正なソフトウェアを隠しておく効果がある。最も単純なページテーブルシステムはフレームテーブルとページテーブルから構成される。フレームテーブルは最も基本的なシステムであり、どのフレームがマップされているかという情報を保持する。より高度なシステムではフレームテーブルにはどの仮想アドレス空間にそのページが属しているかという情報、統計情報、その他の情報も格納される。ページテーブルはページの仮想アドレスと物理フレームのアドレスのマッピングを保持する。その他の補助的情報として、"present"(存在)ビット、"dirty"または"modified"(書き込み)ビット、アドレス空間識別子やプロセス識別子などの情報も格納される。ハードディスクなどの二次記憶は物理メモリを増やすためにも使われる。ページはメモリからディスクにスワップアウトしたり、逆にスワップインしたりすることができる。presentビットはページがどのレベルに存在するかを示すものであり、スワップアウトやスワップインの基本的な情報として使用される。dirtyビットは性能最適化に使用される。あるページを物理メモリにスワップインしたとする。このページに書き込みが行われるかもしれないし、内容を読むだけかもしれない。そして、後でそのページをスワップアウトする必要が生じたとき、そのページがスワップインされてから変更されていなければ、スワップアウトを実際に行う必要はない(再度スワップインしたければ、以前の内容を持ってくればよい)。しかし、書き込みを行っていれば dirtyビットが立っているので、スワップアウトを行わなければならない。アドレス空間識別子あるいはプロセス識別子はページの対応するプロセスを識別するのに必要である。各プロセスの仮想メモリマップは同じなので、二つのプロセスの間で同じ仮想アドレスが別の用途に使われている。したがってページテーブル上で仮想アドレスの属しているプロセスを識別しなければならない。このためにユニークなアドレス空間識別子かプロセス識別子を使用するのである。なお、ページテーブルのエントリはそのままTLBに書き込める形式になっていることが多い。したがって、ハードウェアの仕様としてTLBのエントリにはハードウェアが使用しないビットがいくつか用意されていて、ソフトウェアがページテーブルに追加の情報を格納するのに使うことができるようになっている。いくつかのタイプのページテーブルがあり、それぞれ異なった条件に適合するよう設計されている。基本的にページテーブルは仮想アドレスとそれに対応する物理アドレス、そして必要なら追加のアドレス空間情報を格納しなければならない。逆引きページテーブル(Inverted Page Table, IPT)は、ページテーブルとフレームテーブルをひとつのデータ構造にまとめたものである。中核となるのはメモリのフレームに対応するエントリがフレーム番号順に並んだ固定サイズのテーブルである。4000個のフレームがあれば、逆引きページテーブルも4000エントリで構成される。各エントリには仮想ページ番号(VPN)、物理ページ番号(物理アドレスではない)、後述するコリジョン(衝突)チェインを生成するのに使う他のデータなどが格納される。物理フレーム番号順に並んでいるため、そのままでは仮想アドレスから物理アドレスへの変換に使うのは不便である。逆引きページテーブルは全プロセスの仮想空間サイズの合計が実装している物理メモリ量に比較して非常に大きいことから、物理フレーム毎に管理する方がメモリ量を節約できるとの目論見で採用された設計である。しかし、そのままでは与えられた仮想アドレスを物理アドレスに変換するのにIPT全体を見なければならず、時間がかかる。そこで仮想アドレス(と必要なら仮想空間識別子かプロセス識別子)をIPTのインデックスにマッピングするハッシュテーブルを使用する。ここでコリジョンチェインが使用される。このテーブルをハッシュアンカーテーブル(Hash Anchor Table)とも呼ぶ。ハッシュ関数は分布の良さよりも高速さを要求される。もちろん、ハッシュテーブルではコリジョン(衝突)が発生する。ハッシュ関数の選び方によっては衝突が頻繁に発生するので、テーブル内の各エントリにはVPNが格納されていて、それが求めていたエントリなのか、衝突なのかが分かるようになっている。マッピングを探すときに、ハッシュアンカーテーブルが使用される。エントリが見つからなければページフォールトが発生する。エントリが見つかれば(アーキテクチャにもよるが)、それをTLBに置いて、メモリアクセスが再実行される。また、コリジョンチェインを辿っていってエントリが見つからない場合もページフォールトが発生する。この手法では、仮想アドレスは2つに分けられ、上位ビット部分が仮想ページ番号、下位部分がページ内オフセットである。逆引きページテーブルを使用するアーキテクチャとしてはPA-RISCやPOWERがある。逆引きページテーブルは物理メモリ内の全フレームに関するマッピングのリストを保持している。しかし、仮想ページ毎にマッピングを保持するページテーブルを作成するのも自然な考え方のひとつと言える。ただし、仮想アドレス空間が大きくかつ複数存在するため、非常に大きな無駄なデータ構造となりうる可能性がある。そのため、ある仮想空間の領域をカバーするページテーブルを作成する。例えば、4Kページ1024個ぶんの領域をカバーすれば、4Mバイトの仮想メモリをマッピングできる。仮想空間の両端(アドレス 0x0 の付近と最大アドレスの付近)をプロセスが使用することが多いため、このような部分的な仮想空間をカバーするページテーブルは便利である。例えば、仮想アドレスの小さい方をテキストとデータに使用し、大きい方をスタックに使用する(データセグメントとスタックセグメントがそれぞれ仮想空間の真ん中に向かって成長する)。多段ページテーブルでは小さなページテーブルをいくつか使って使用中の仮想空間の領域だけをカバーし、本当に必要なときだけ追加のページテーブルを作成する。このような小さなページテーブルは上位のページテーブルにリンクされ、全体として木構造を形成する。2段である必要はなく、それ以上の段数になることもありうる。この手法では仮想アドレスは(最低でも)3つの部分に分割される。上位ビットのほうから、ルートページテーブルのインデックス、サブページテーブルのインデックス、ページ内オフセットとなる。仮想アドレス空間の全仮想ページについてのマッピングを含むページテーブル構造は非常に無駄が多いことは上述の通りである。しかし、ページテーブルを仮想記憶システム内に置くことでページテーブル用のメモリを仮想記憶方式で管理することができる。つまり、多段ページテーブルのサブページテーブルに相当するものを仮想空間上で連続に並べ、現在のプロセスが使用している仮想空間全体がカバーされる仮想化ページテーブルを作成するのである。当然、もともとのサブページテーブルがない部分には何もマッピングされない。32ビットシステムで4Kページ、ページテーブルエントリが32ビットであれば、4Mバイトの仮想空間をページテーブルのマッピングに使用することになる。仮想化ページテーブルはハードウェアがページテーブルを自動的に参照しない場合に、TLBミスの処理を高速化する手段として使われることが多い。例えば、MIPSアーキテクチャでこれが使われているし、SPARCでも類似の手法が使われている。ただし、この場合に一部のページテーブルは必ず常駐していないと、ページフォールトの連鎖が発生する。つまり、ページフォールトのハンドラ内でアクセスする可能性のある部分でページフォールトが発生すると、ページフォールトが解決できなくなってシステムがストールしてしまう。ItaniumおよびItanium2では、多段ページテーブルを前提とした仮想化ページテーブルと、逆引きページテーブルを前提とした仮想化ハッシュアンカーテーブルをサポートしており、オペレーティングシステムがいずれかを選んで使用することができる。

出典:wikipedia