ページテーブル

ページテーブル(page table)とは、コンピュータのオペレーティングシステムの中の仮想記憶(virtual memory)システムで仮想アドレスと物理アドレスを対応付けるために使われるデータ構造である。仮想アドレスはそれにアクセスするプロセスによって実行されるプログラムによって使われ、実際には物理アドレスはRAMサブシステム等のハードウェアによって使われる。

仮想記憶を使うオペレーティングシステムでは、すべてのプロセスは大きくて一続きのメモリ領域で動いていると錯覚させられている。物理的には、それぞれのプロセスのメモリは物理メモリの色々な領域に散らばっているか、ハードディスク等の他のストレージに移されている(ページアウト)。

プロセスが自身のメモリにアクセスを要求したとき、オペレーティングシステムには、プロセスが要求してきた仮想アドレスをデータが保持されている実際のメモリの物理アドレスに対応付ける責任がある。ページテーブルはオペレーティングシステムがこの対応付けを保存しておくところで、それぞれの対応付けはページテーブルエントリー（page table entry(PTE))と呼ばれる。

ワード長が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では、多段ページテーブルを前提とした仮想化ページテーブルと、逆引きページテーブルを前提とした仮想化ハッシュアンカーテーブルをサポートしており、オペレーティングシステムがいずれかを選んで使用することができる。

• アンドリュー・タネンバウム, Modern Operating Systems, ISBN 0130313580

• 仮想記憶
  • ページング方式
• メモリ管理
  • メモリ管理ユニット
    • ページフォールト
• ポインタ (プログラミング)
• PaX

• コンピュータハードウェア(7) 坂井修一、東京大学
• 第一部 第七章 メモリ管理 アドレス変換とメモリ管理 トロン仕様チップ標準ハンドブック(東京大学坂村研究室)
• オペレーティング・システム講座 記憶管理 Multisoft-lab