ページテーブル

ページ テーブルは、仮想アドレスと物理アドレス間のマッピングを保存するためにコンピュータの仮想メモリシステムによって使用されるデータ構造です。仮想アドレスはアクセスプロセスによって実行されるプログラムによって使用され、物理アドレスはハードウェア、より具体的にはランダム アクセス メモリ(RAM) サブシステムによって使用されます。ページ テーブルは、メモリ内のデータにアクセスするために必要な仮想アドレス変換の主要コンポーネントです。ページ テーブルはコンピュータのオペレーティング システムによって設定され、仮想アドレス変換プロセス中にメモリ管理ユニットまたは低レベルのシステム ソフトウェアやファームウェアによって読み書きされる場合があります。

仮想メモリを使用するオペレーティング システムでは、すべてのプロセスが、メモリの大きな連続セクションで作業しているように見えます。物理的には、各プロセスのメモリは物理メモリの異なる領域に分散されているか、または二次ストレージ、通常はハード ディスク ドライブ(HDD) またはソリッド ステート ドライブ(SSD)に移動 (ページ アウト) されている可能性があります。

プロセスがメモリ内のデータへのアクセスを要求すると、プロセスによって提供された仮想アドレスを、そのデータが格納されている実際のメモリの物理アドレスにマッピングするのはオペレーティングシステムの役割です。ページテーブルは、仮想アドレスと物理アドレスのマッピングが格納される場所であり、各マッピングはページテーブルエントリ(PTE) とも呼ばれます。^{[1] [2]}

CPU 内部のメモリ管理ユニット( MMU) には、オペレーティング システムのページ テーブルから最近使用されたマッピングのキャッシュが格納されます。これは、連想キャッシュであるトランスレーション ルックアサイド バッファ(TLB) と呼ばれます。

仮想アドレスを物理アドレスに変換する必要がある場合、最初に TLB が検索されます。一致が見つかった場合 ( TLB ヒット)、物理アドレスが返され、メモリ アクセスを続行できます。ただし、一致がない場合 ( TLB ミス)、MMU、システム ファームウェア、またはオペレーティング システムの TLB ミス ハンドラーは通常、ページ テーブルでアドレス マッピングを検索し、マッピングが存在するかどうかを確認します (ページ ウォーク)。マッピングが存在する場合、TLB に書き戻されます。これは、ハードウェアが仮想メモリ システムで TLB を介してメモリにアクセスし、エラーが発生した命令が再開されるため必須であり、これらも並行して発生する可能性があります。その後の変換で TLB ヒットになり、メモリ アクセスが続行されます。

ページ テーブルの検索が失敗し、ページ フォールトが発生する原因としては、次の 2 つのことが考えられます。

• 仮想アドレスの変換が利用できない場合、検索は失敗する可能性があります。これは、仮想アドレスが無効であることを意味します。これは通常、プログラミング エラーが原因で発生し、オペレーティング システムは問題に対処するために何らかのアクションを実行する必要があります。最新のオペレーティング システムでは、問題のあるプログラムにセグメンテーション エラーシグナルが送信されます。
• ページが現在物理メモリ内に存在しない場合も、検索が失敗することがあります。これは、要求されたページが別のページ用のスペースを確保するために物理メモリから移動された場合に発生します。この場合、ページはハード ディスク ドライブなどのメディアにあるセカンダリ ストアにページ アウトされます (このセカンダリ ストア、つまり「バッキング ストア」は、ディスク パーティションの場合はスワップパーティション、ファイルの場合はスワップ ファイル、スワップファイル、またはページ ファイルと呼ばれることがよくあります)。このような状況が発生すると、ページをディスクから取り出して物理メモリに戻す必要があります。同様のメカニズムがメモリ マップ ファイルにも使用されます。メモリ マップ ファイルは仮想メモリにマップされ、必要に応じて物理メモリにロードされます。

物理メモリがいっぱいでない場合は、これは単純な操作です。ページが物理メモリに書き戻され、ページ テーブルと TLB が更新され、命令が再開されます。ただし、物理メモリがいっぱいの場合は、要求されたページのためのスペースを確保するために、物理メモリ内の 1 つ以上のページをページ アウトする必要があります。ページ テーブルを更新して、以前物理メモリにあったページがなくなったこと、およびディスクにあったページが物理メモリにあることをマークする必要があります。TLB も更新する必要があり、ページ アウトされたページを TLB から削除し、命令を再開する必要があります。どのページをページ アウトするかは、ページ置換アルゴリズムの対象です。

一部の MMU は、ページが現在物理メモリ内に存在し、プロセスの仮想アドレス空間にマップされているかどうかに関係なく、他の理由でページ フォールトをトリガーします。

• ページ テーブルに読み取り専用ビットが設定されている場合に書き込みを試みると、ページ フォールトが発生します。これは、多くのオペレーティング システムのコピー オン ライトの実装における通常の部分です。また、プロセスが読み取りは許可されているが書き込みは許可されていない場所に書き込みが行われた場合にも発生することがあります。その場合、プロセスにシグナルが送信されます。
• ページテーブルにNXビット（実行禁止ビット）が設定されている場合にコードを実行しようとすると、ページフォールトが発生します。これは、オペレーティングシステムが読み取り専用ビットと組み合わせて使用​​することで、ある種のエクスプロイトを阻止する書き込みXOR実行機能を提供するために使用できます。 ^[3]

最も単純なページ テーブル システムでは、フレームテーブルとページ テーブルが保持されることがよくあります。フレーム テーブルには、どのフレームがマップされているかに関する情報が保持されます。より高度なシステムでは、フレーム テーブルには、ページが属するアドレス空間に関する情報、統計情報、その他の背景情報も保持されます。

ページ テーブルは、ページ テーブル エントリの配列です。

各ページ テーブル エントリ (PTE) には、ページの仮想アドレスと物理フレームのアドレス間のマッピングが保持されます。また、ページに関する補助情報として、現在ビット、ダーティビットまたは変更ビット、アドレス空間、プロセス ID 情報などがあります。

ハードディスク ドライブなどの二次記憶装置は、物理メモリを拡張するために使用できます。ページは、物理メモリとディスク間でページインおよびページアウトできます。現在ビットは、現在物理メモリまたはディスクに存在するページを示すことができ、これらの異なるページをどのように処理するか、つまり、ディスクからページをロードして物理メモリ内の別のページをページアウトするかどうかを示すことができます。

ダーティ ビットを使用すると、パフォーマンスを最適化できます。物理メモリにページインされ、その後読み取られ、その後再びページアウトされるディスク上のページは、ページが変更されていないため、ディスクに書き戻す必要はありません。ただし、ページがページインされた後に書き込まれた場合は、ダーティ ビットが設定され、ページをバッキング ストアに書き戻す必要があることを示します。この戦略では、ページがメモリにページインされた後、バッキング ストアがそのページのコピーを保持する必要があります。ダーティ ビットを使用しない場合、バッキング ストアは、任意の時点でページアウトされたすべてのページの瞬間的な合計サイズと同じ大きさで十分です。ダーティ ビットを使用する場合、常にいくつかのページが物理メモリとバッキング ストアの両方に存在することになります。

単一アドレス空間オペレーティング システムではないオペレーティング システムでは、仮想メモリ管理システムがどのページをどのプロセスに関連付けるかを認識するために、アドレス空間またはプロセス ID 情報が必要です。 2 つのプロセスが、2 つの同一の仮想アドレスを異なる目的で使用することがあります。ページ テーブルは、2 つのプロセスに異なる仮想メモリ マッピングを提供する必要があります。これは、2 つのプロセスに異なるアドレス マップ識別子を割り当てるか、プロセス ID を使用することで実行できます。プロセス ID を仮想メモリ ページに関連付けると、ページ アウトするページの選択にも役立ちます。非アクティブなプロセスに関連付けられたページ、特にコード ページがページ アウトされたプロセスに関連付けられたページは、アクティブなプロセスに属するページよりもすぐに必要になる可能性が低いためです。

ページ テーブル エントリにプロセス固有の識別子をタグ付けする代わりに、ページ テーブル自体がプロセスごとに異なる仮想メモリ ページを占有し、ページ テーブルがプロセス コンテキストの一部となるようにすることができます。このような実装では、プロセスがメモリ内に存在しなくなったときにいつでも、プロセスのページ テーブルをページ アウトできます。

ページ テーブルにはいくつかの種類があり、さまざまな要件に合わせて最適化されています。基本的に、必要最低限​​のページ テーブルには、仮想アドレス、この仮想アドレスの「下」にある物理アドレス、および場合によってはアドレス空間情報を格納する必要があります。

反転ページ テーブル(IPT) は、通常のシステム RAM を使用するTLBのオフチップ拡張と考えるのが適切です。真のページ テーブルとは異なり、必ずしも現在のすべてのマッピングを保持できるわけではありません。オペレーティング システムは、MIPS スタイルのソフトウェアで満たされた TLB の場合と同様に、ミスを処理する準備をする必要があります。

IPT は、ページ テーブルとフレーム テーブルを1 つのデータ構造に結合します。その中心にあるのは、メモリ内のフレーム数と同じ行数を持つ固定サイズのテーブルです。フレームが 4,000 個ある場合、反転ページ テーブルには 4,000 行あります。各行には、仮想ページ番号 (VPN)、物理ページ番号 (物理アドレスではありません)、その他のデータ、および衝突チェーンを作成するための手段のエントリがあります。これについては後で説明します。

コア IPT 構造のすべてのエントリを検索するのは非効率なので、ハッシュ テーブルを使用して仮想アドレス (および必要に応じてアドレス空間/PID 情報) を IPT のインデックスにマッピングできます。ここで衝突チェーンが使用されます。このハッシュ テーブルは、ハッシュ アンカー テーブルと呼ばれます。ハッシュ関数は一般にカバレッジに対して最適化されておらず、生の速度の方が望ましいです。もちろん、ハッシュ テーブルでは衝突が発生します。このハッシュ関数の選択により、使用時に多くの衝突が発生する可能性があるため、テーブルの各エントリに対して、検索されたエントリであるか衝突であるかを確認するための VPN が提供されます。

マッピングの検索では、ハッシュ アンカー テーブルが使用されます。エントリが存在しない場合は、ページ フォールトが発生します。それ以外の場合は、エントリが見つかります。アーキテクチャによっては、エントリが TLB に再度配置され、メモリ参照が再開されるか、衝突チェーンが尽きるまで追跡され、ページ フォールトが発生することがあります。

このスキーマの仮想アドレスは 2 つに分割でき、最初の半分は仮想ページ番号、2 番目の半分はそのページ内のオフセットになります。

この設計の主な問題は、ハッシュ関数によってキャッシュの局所性が悪くなることです。ツリーベースの設計では、隣接するページのページ テーブル エントリを隣接する場所に配置することでこの問題を回避しますが、反転ページ テーブルではエントリがあちこちに散らばるため、参照の空間的な局所性が損なわれます。オペレーティング システムでは、この問題を軽減するためにハッシュ テーブルのサイズを最小限に抑えることができますが、その代償としてミス率が高くなります。

通常、物理メモリ内で連続し、すべてのプロセスで共有されるハッシュ テーブルが 1 つあります。プロセスごとの識別子は、異なるプロセスのページを互いに区別するために使用されます。特定のプロセスのページ テーブル エントリを削除するには多少時間がかかります。OS は、この問題に対処するためにプロセスごとの識別子値の再利用を避ける場合があります。代わりに、プロセスごとのハッシュ テーブルを使用することもできますが、メモリの断片化が発生するため実用的ではありません。メモリの断片化が発生すると、テーブルを事前に割り当てる必要があります。

反転ページテーブルは、例えばPowerPC、UltraSPARC、IA-64アーキテクチャなどで使用されています。^[4]

反転ページ テーブルは、物理メモリ内のすべてのフレームにインストールされているマッピングのリストを保持します。ただし、これは非常に無駄になる可能性があります。そうする代わりに、仮想ページのマッピングを含むページ テーブル構造を作成できます。これは、仮想メモリの特定のブロックをカバーする複数のページ テーブルを保持することで実現します。たとえば、4 MB の仮想メモリをカバーする、1024 エントリの 4 KB の小さなページを作成できます。

これは、仮想メモリの最上部と最下部がプロセスの実行に使用されることが多いため便利です。上部はテキストとデータ セグメントに使用され、下部はスタックに使用され、その間に空きメモリがあります。マルチレベル ページ テーブルは、メモリの上部と下部のみをカバーするためにいくつかの小さなページ テーブルを保持し、厳密に必要な場合にのみ新しいページ テーブルを作成します。

現在、これらの小さなページ テーブルはそれぞれマスター ページ テーブルによってリンクされており、実質的にツリーデータ構造を形成しています。レベルは 2 つだけではなく、複数にすることもできます。たとえば、このスキーマの仮想アドレスは、ルート ページ テーブルのインデックス、サブページ テーブルのインデックス、およびそのページ内のオフセットの 3 つの部分に分割できます。

マルチレベル ページ テーブルは、「階層ページ テーブル」とも呼ばれます。

仮想アドレス空間内のすべての仮想ページのマッピングを含むページ テーブル構造を作成すると、無駄になる可能性があると説明しました。ただし、ページ テーブルを仮想メモリに配置し、仮想メモリ システムにページ テーブルのメモリを管理させることで、過剰なスペースの問題を回避できます。

ただし、循環ページ フォールトを防止し、ページ テーブルに存在しないページ テーブルの重要な部分を探すため に、この線形ページ テーブル構造の一部は常に物理メモリ内に常駐している必要があります。

ネストされたページ テーブルを実装すると、ハードウェア仮想化のパフォーマンスが向上します。ページ テーブル仮想化のハードウェア サポートを提供することで、エミュレートの必要性が大幅に軽減されます。x86仮想化の場合、現在の選択肢は、 IntelのExtended Page Table機能とAMDのRapid Virtualization Indexing機能です。

• 翻訳ルックアサイドバッファ
• ページ置換アルゴリズム
• ポインタ（コンピュータプログラミング）
• W^X

• メモリ管理リファレンス