Intel x86 Assembly Language & Microarchitecture
ページング - 仮想アドレス指定とメモリ
サーチ…
前書き
歴史
最初のコンピュータ
初期のコンピュータには、プログラマがコードとデータを入れ、CPUがこの環境内で実行されるメモリブロックがありました。コンピュータが非常に高価だったことを考えると、1つのジョブを実行し、次のジョブがロードされるのを待ってから、そのジョブを処理するのは残念です。
マルチユーザ、マルチプロセッシング
つまり、コンピュータはすばやく洗練され、複数のユーザーやプログラムを同時にサポートしましたが、それは単純な「1ブロックのメモリ」アイデアで問題が発生し始めたときです。コンピュータが2つのプログラムを同時に実行していた場合、または同じプログラムを複数のユーザーに対して実行していた場合、各ユーザーごとに個別のデータが必要になりました。
例
たとえば、プログラムがメモリアドレス1000で動作するように書かれていて、そこに別のプログラムが既にロードされている場合、新しいプログラムをロードできませんでした。これを解決する1つの方法は、プログラムが「相対アドレス指定」で動作するようにすることです。プログラムがロードされた場所は関係なく、ロードされたメモリアドレスを基準にして行われます。
洗練
コンピュータハードウェアがより高度化するにつれて、より大きなメモリブロックをサポートすることができ、より多くの同時プログラムが可能になり、既にロードされたものに干渉しないプログラムを書くのが難しくなった。 1つの迷いのあるメモリ参照は、現在のプログラムだけでなく、メモリ内の他のプログラム（オペレーティングシステム自体を含む）をダウンさせる可能性があります。
ソリューション
必要なのは、メモリブロックに動的アドレスを持たせるメカニズムでした。そうすれば、プログラムは、認識されたアドレスでメモリのブロックを処理し、他のプログラムの他のブロックにアクセスすることはできません（いくつかの協力が許可されていない限り）。
セグメンテーション
これを実装した1つのメカニズムはセグメンテーションでした。これにより、メモリのブロックはすべての異なるサイズで定義でき、プログラムは常にアクセスしたいセグメントを定義する必要がありました。
問題
この手法は強力でしたが、その柔軟性は問題でした。セグメントは基本的に利用可能なメモリを異なるサイズのチャンクに分割していたため、セグメントのメモリ管理は問題でした。割り当て、割り当て解除、拡張、縮小、断片化 - 必要なすべての洗練されたルーチン、
ページング
別のテクニックでは、すべてのメモリを「ページ」と呼ばれる同じサイズのブロックに分割し、割当てルーチンと解放ルーチンを非常にシンプルにし、成長、縮小、断片化を解消しました（内部断片化を除いて無駄）。
仮想アドレッシング
メモリをこれらのブロックに分割することによって、プログラムが必要とする任意のアドレスで、必要に応じて異なるプログラムに割り当てることができます。メモリの物理アドレスとプログラムの所望のアドレスとの間のこの「マッピング」は非常に強力であり、今日の主要なプロセッサ（Intel、ARM、MIPS、Power等）メモリ管理の基礎となっている。
ハードウェアとOSのサポート
ハードウェアは自動的かつ継続的に再マッピングを実行しましたが、何をすべきかのテーブルを定義するためにメモリが必要でした。もちろん、この再マッピングに関連するハウスキーピングは何かによって制御されなければならなかった。オペレーティングシステムは、必要に応じてメモリを除外し、プログラムが必要とするものをサポートするためにハードウェアが必要とするデータのテーブルを管理しなければならない。
ページング機能
ハードウェアがこの再マッピングを実行できるようになると、何が可能になりましたか？主なドライバーはマルチプロセッシングで、それぞれが独自のメモリーを持つ複数のプログラムを実行して相互に保護していました。しかし、2つの選択肢には、「疎なデータ」と「仮想メモリ」があります。
マルチプロセッシング
各プログラムには、自分の仮想アドレス空間（物理アドレスが割り当てられたアドレス範囲）が与えられました。十分な物理メモリがあれば（下記の「仮想メモリ」を参照）、多数のプログラムを同時にサポートすることができます。
さらに、これらのプログラムは 、仮想アドレス空間にマップされていないメモリにアクセスすることはできませんでした 。プログラム間の保護は自動でした。プログラムが通信する必要がある場合、OSは、2つの異なるプログラムのアドレス空間に同時にマッピングされた物理メモリのブロックである共有メモリブロックを手配するよう要求することができます。
スパースデータ
巨大な仮想アドレス空間（典型的には4GBは32ビットレジスタに対応している）は、そのアドレス空間の広い領域がマップされていないとメモリを浪費しません。これにより、ある時点で特定のパーツのみがマッピングされる巨大なデータ構造を作成することができます。各方向に1,000バイトの3次元配列を想像してみましょう。これは通常10億バイトを要します！しかし、プログラムは、このデータを「保持」するために仮想アドレス空間のブロックを確保することができますが、小さなセクションにはデータが移入されるたびにマップされます。これは効率的なプログラミングを可能にし、まだ必要でないデータのためのメモリを浪費しない。
仮想メモリ
上記では、「仮想アドレス指定」という用語を使用して、ハードウェアによって実行される仮想から物理へのアドレス指定を説明しました。これはしばしば「仮想メモリ」と呼ばれますが、この用語は、仮想アドレス指定を使用して実際に利用可能なメモリよりも多くのメモリを使用するというテクニックをより正確に対応させます。
それはこのように動作します：
- プログラムがロードされ、より多くのメモリを要求すると、OSは使用可能なメモリからメモリを提供します。メモリは、どのメモリがマップされているかを把握するだけでなく、メモリが実際に使用された時期も把握しています。ハードウェアは使用済みページのマーキングをサポートしています。
- OSの物理メモリが不足すると、使用されたページが最も少なくなったか、または最も長く使われていなかったかにかかわらず、すでに渡されたすべてのメモリが調べられます。その特定のページの内容をハードディスクに保存し、元の所有者のハードウェアに「存在しない」とマークしてから、そのページをゼロにして新しい所有者に渡します。
- 元の所有者がそのページに再度アクセスしようとすると、ハードウェアはOSに通知します。その後、OSは新しいPageを割り当てます（前のステップをやり直さなければならないかもしれません！）、古いPageのコンテンツを読み込んで元のプログラムに渡します。
注目すべき重要なポイントは、どのページも任意のアドレスにマップでき、各ページは同じサイズであるため、1つのページは他のページと同じくらい良いということです。
- プログラムがマップされていないメモリ位置にアクセスすると、ハードウェアは以前と同じようにOSに通知します。今回は、OSはそれが救われたページではないことに気付き、それをプログラムのバグとして認識し、終了させます。
これは実際にあなたのアプリが不思議にあなたを失ったとき、つまりおそらくOSのMessageBoxを使って起こることです。悪名高いブルースクリーンや悲しいMacを引き起こすこともしばしば起こります。そのバギープログラムは、実際にはそうしてはならないメモリにアクセスするOSドライバでした！
ページングの決定
ハードウェア設計者は、設計がCPUの設計に直接影響を及ぼすため、ページングについていくつかの大きな決定をする必要がありました。非常に柔軟なシステムではオーバーヘッドが大きく、ページングインフラストラクチャ自体を管理するだけで大量のメモリが必要になります。
ページの大きさはどれくらいですか？
ハードウェアでは、ページングの最も簡単な実装は、Addressを2つの部分に分割することです。上部はアクセスするページのインジケータになり、下部は必要なバイトのページへのインデックスになります。
+-----------------+------------+
| Page index | Byte index |
+-----------------+------------+
小さなページには各プログラムの膨大なインデックスが必要ですが、マップされていないメモリであっても、これを示すテーブルにエントリが必要です。
したがって、代わりに多層索引が使用されます。アドレスは複数の部分に分割され（3つは下の例で示されます）、最後のページへの最後のバイトインデックスがデコードされるまで、先頭部分（一般に「ディレクトリ」と呼ばれます）
+-----------+------------+------------+
| Dir index | Page index | Byte index |
+-----------+------------+------------+
つまり、ディレクトリインデックスは、多数のページインデックスを必要とせずに、アドレススペースの膨大な部分に対して「マップされていない」ことを示すことができます。
どのようにページテーブルの使用を最適化するには？
CPUが行うすべてのアドレスアクセスはマップされなければならないので、仮想から物理へのプロセスはできるだけ効率的でなければなりません。上記の3階層システムを実装する場合、実際にはすべてのメモリアクセスが3つのアクセスとなることを意味します。 1つはページテーブルに、最後に希望のデータそのものを選択します。また、CPUがハウスキーピングを実行する必要がある場合（このページが現在アクセスまたは書込みされたことを示すなど）には、フィールドを更新するためのアクセスがさらに必要になります。
メモリは高速かもしれませんが、これはページング中にすべてのメモリアクセスに3倍の減速を課すでしょう！幸いなことに、ほとんどのプログラムは「範囲の局所性」を持っています。つまり、メモリ内の1つの場所にアクセスすると、おそらく将来のアクセスが近くにあります。また、Pagesは小さすぎないので、新しいページにアクセスしたときにマッピングの変換を実行するだけで済みます。すべてのアクセスが絶対に必要ではありません。
しかし、最も最近のページだけでなく、最近アクセスしたページのキャッシュを実装する方が良いでしょう。問題は、キャッシュされた値を見つけるためにハードウェアがすべてのアクセスでキャッシュをスキャンしなければならないであろう、どのページがアクセスされたのか、それがなかったのかを維持することである。したがって、キャッシュはコンテンツアドレス可能なキャッシュとして実装されます。アドレスによってアクセスされるのではなく、コンテンツによってアクセスされます。要求されたデータが存在する場合はそれが提供され、そうでない場合は空の場所にフラグが立てられます。キャッシュはそのすべてを管理します。
このコンテンツアドレス可能キャッシュは、しばしば変換ルックアサイドバッファ（TLB）と呼ばれ、仮想アドレス指定サブシステムの一部としてOSによって管理される必要があります。ディレクトリまたはページテーブルがOSによって変更された場合、TLBにエントリを更新するよう通知するか、単にエントリを無効にする必要があります。
80386ページング
ハイレベルデザイン
80386は32ビットのプロセッサで、32ビットのアドレス指定可能なメモリ空間を備えています。ページング・サブシステムの設計者は、4Kのページ設計が、10ビット、10ビット、および12ビットという非常にきれいな方法でこれらの32ビットにマップされていることに気付きました。
+-----------+------------+------------+
| Dir index | Page index | Byte index |
+-----------+------------+------------+
3 2 2 1 1 0 Bit
1 2 1 2 1 0 number
つまり、バイトインデックスは12ビット幅で、4Kページにインデックスを付けることになりました。ディレクトリとページのインデックスは10ビットで、それぞれ1,024エントリのテーブルにマップされます。これらのテーブルエントリがそれぞれ4バイトであれば、それはテーブルあたり4Kです。
そういうわけで、彼らは何をしました：
- 各プログラムには独自のディレクトリがあります.1104ページのエントリを持つPageがあり、次のレベルのPage Tableがあった場合はそれぞれ定義されています。
- 存在していた場合、そのページテーブルには1,024ページのエントリがあり、それぞれが最後のレベルのページがある場所が定義されています。
- もしあれば、そのページはバイトを直接読み上げることができます。
ページエントリ
トップレベルのディレクトリと次のレベルのページテーブルはともに1,024ページのエントリで構成されています。これらのエントリの最も重要な部分は、索引付けされているもののアドレス、つまりPage Tableまたは実際のPageです。このアドレスには32ビットは必要ありません。すべてがページなので、上位20ビットだけが重要です。したがって、ページエントリ内の他の12ビットは、次のレベルが存在するかどうかなど、他のものにも使用できます。ページがアクセスされたか書き込まれたかのハウスキーピング、たとえ書き込みが許可されるべきであっても！
+--------------+----+------+-----+---+---+
| Page Address | OS | Used | Sup | W | P |
+--------------+----+------+-----+---+---+
Page Address = Top 20 bits of Page Table or Page address
OS = Available for OS use
Used = Whether this page has been accessed or written to
Sup = Whether this page is Supervisory - only accessible by the OS
W = Whether this page is allowed to be Written
P = Whether this page is even Present
Pビットが0の場合、Entryの残りの部分には、OSの中に入れたいものがあることが許されます。たとえば、ページの内容がハードディスク上にあるかどうかなどです。
ページディレクトリベースレジスタ（ PDBR ）
各プログラムに独自のディレクトリがある場合、ハードウェアはどのようにマッピングを開始するのかを知っていますか？ CPUは一度に1つのプログラムしか実行していないので、現在のプログラムのディレクトリのアドレスを保持する単一の制御レジスタを持っています。これはページディレクトリベースレジスタ（ CR3 ）です。 OSが異なるプログラム間でスワップすると、 PDBRはプログラムの関連ページディレクトリで更新されます。
ページフォルト
CPUがメモリにアクセスするたびに、指定された仮想アドレスを適切な物理アドレスにマップする必要があります。これは3つのステップからなるプロセスです。
- 適切なページテーブルのアドレスを取得するために、
PDBRによって示されたページにアドレスの上位10ビットをインデックスする。 - 適切なPageのアドレスを取得するために、Directoryによって示されたPageへのアドレスの次の10ビットを索引付けします。
- アドレスの最後の12ビットにインデックスを付けて、そのページからデータを取得します。
上記のステップ1.と2.は両方ともページ・エントリーを使用するため、各エントリーは問題を示す可能性があります。
- 次のレベルは「存在しない」とマークされることがあります。
- 次のレベルは「読み取り専用」としてマークされ、操作は書き込みです。
- 次のレベルは "スーパーバイザー"としてマークされているかもしれません - それはメモリではなくOSにアクセスするプログラムです。
このような問題がハードウェアによって認識されると、アクセスを完了するのではなく、障害：割り込み14番、ページフォルトが発生します。また、いくつかの特定の制御レジスタに、障害が発生した理由の情報を記入します。スーパーバイザアクセスであったかどうか。それが書き込みの試みかどうか。
OSは、そのフォルトをトラップし、制御レジスタをデコードし、何をすべきかを決定することが期待されている。無効なアクセスであれば、障害の発生しているプログラムを終了することができます。仮想メモリへのアクセスであれば、OSは新しいページ（既に使用中のページを空ける必要があるかもしれません！）を割り当て、必要な内容（すべて0またはディスクから戻された以前の内容）、新しいページを適切なページテーブルにマップし、それを現在のものとしてマークしてから、フォルト命令を再開します。今回はアクセスが正常に進み、プログラムは何か特別なことが起こったことを知らずに進みます（時計を見ない限り！）
80486ページング
80486ページングサブシステムは、80386と非常によく似ていました。それは下位互換性があり、唯一の新機能は、ページ単位でメモリキャッシュ制御を可能にすることでした.OSデザイナーは、特定のページをキャッシュしないようにマークしたり、異なるライトスルーまたはライトバックキャッシング技術。
その他の点では、「80386ページング」の例が該当します。
ペンティアムページング
Pentiumが開発されていたときに、メモリサイズとその中で実行されたプログラムが大きくなっていました。大規模なプログラムやデータセットが使用されているときに更新する必要があった膨大な数のページインデックスだけで、ページングサブシステムを維持するためにOSはますます多くの作業をしなければなりませんでした。
ペンティアムのデザイナーは単純なテクニックを追加しました。ページディレクトリのエントリには、次のレベルがページテーブル（以前と同じように）だったのか、直接4MBページになったのかを示すビットが追加されました。 4 MBページの概念を持つことで、OSはページテーブルを作成し、基本的に前のものよりも4K高いアドレスをインデックス付けしていた1,024のエントリで満たす必要はありません。
住所のレイアウト
+-----------+----------------------+
| Dir Index | 4MB Byte Index |
+-----------+----------------------+
3 2 2 0 Bit
1 2 1 0 number
ディレクトリエントリのレイアウト
+-----------+----+---+------+-----+---+---+
| Page Addr | OS | S | Used | Sup | W | P |
+-----------+----+---+------+-----+---+---+
Page Addr = Top 20 bits of Page Table or Page address
OS = Available for OS use
S = Size of Next Level: 0 = Page Table, 1 = 4 MB Page
Used = Whether this page has been accessed or written to
Sup = Whether this page is Supervisory - onlly accessible by the OS
W = Whether this page is allowed to be Written
P = Whether this page is even Present
もちろん、それにはいくつかの影響がありました。
- 4Kページは4Kアドレス境界から開始しなければならなかったのと同じように、4MBアドレス境界から開始しなければなりませんでした。
- 4MBはすべて1つのプログラムに属していなければならず、複数のプログラムで共有する必要がありました。
これは、OSが使用するためにマップされる必要のある大きなアドレススペースのウィンドウを持つグラフィックスアダプタなどの大容量の周辺機器に使用するのに最適でした。
物理アドレス拡張（PAE）
前書き
メモリ価格が下がるにつれて、インテルベースのPCは、より多くのRAMを手に入れることができ、同時に生産されていた巨大なアプリケーションの多くを実行することによる多くのユーザーの問題を軽減することができました。仮想メモリでは、既存の「古い」ページの内容をハードディスクにスワップして「新しい」データを保存できるように、メモリを事実上「作成」することができました。これにより、ページ「スラッシング」がデータを絶え間なくスワップしながらハードディスクのオンとオフを切り替えます。
より多くのRAM
より多くの物理RAMにアクセスする能力が必要でしたが、すでに32ビットのアドレスバスだったため、増加するとより大きなアドレスレジスタが必要になります。それとも？ Pentium Pro（さらにはPentium M）を開発するときに、64ビットプロセッサが生成されるまでのストップギャップとして、レジスタビットの数を変更することなく物理アドレスビットを増やす（物理メモリを増やす） ことができます。これは仮想アドレスが物理アドレスにマッピングされているために実現できました。変更が必要なものはすべてマッピングシステムでした。
設計
既存のシステムは、最大32ビットの物理アドレスにアクセスできます。これを増やすには、ページエントリ構造を32ビットから64ビットに完全に変更する必要がありました。最小限の粒度を4Kページに保つことが決定されたため、64ビットのエントリは52ビットのアドレスと12ビットの制御（以前のエントリは20ビットのアドレスと12ビットの制御を持っていたようです）。
64ビットのエントリを持つが、（まだ）4Kのページサイズを持つことは、前の1,024ではなく、ページテーブルまたはディレクトリごとに512のエントリしか存在しないことを意味していました。これは、32ビットの仮想アドレスが以前とは異なる方法で分割されることを意味します。
+-----+-----------+------------+------------+
| DPI | Dir Index | Page Index | Byte Index |
+-----+-----------+------------+------------+
3 3 2 2 2 1 1 0 Bit
1 0 9 1 0 2 1 0 number
DPI = 2-bit index into Directory Pointer Table
Dir Index = 9-bit index into Directory
Page Index = 9-bit index into Page Table
Byte Index = 12-bit index into Page (as before)
ディレクトリ索引とページ索引の両方から1ビットを切り捨てると、マッピングの3番目の層に2ビットが与えられました。これは、以前のものではなく4つのディレクトリを扱う4つの64ビット・エントリの表であるページ・ディレクトリ・ポインタ・テーブル（PDPT） 1。 PDBR（ CR3 ）は、代わりにPDPTを指し示しました。これは、 CR3が32ビットであったため、アクセシビリティのために最初の4 GBのRAMに格納する必要がありました。 CR3の下位ビットは制御のために使用されるので、PDPTは32バイト境界で開始しなければならないことに留意されたい。
ページサイズ拡張（PSE）
そして、以前の4MBのページはとても良いアイデアだったので、大きなページを再びサポートできるようにしたかったのです。しかし今回は、階層システムの最後のレイヤーを削除しても、10 + 12ビットの4MBページは生成されず、9 + 12ビットの2MBページが生成されました。
PSE-32（およびPSE-40）
Pentium Pro（およびPentum M）で導入された物理アドレス拡張（PAE）モードは、オペレーティングシステムのメモリ管理サブシステムのような変更であったため、IntelがPentium IIを設計したときに、以前に定義された32ビットエントリ内のプロセッサの新しい物理アドレスビットをサポートします。
彼らは、4MBのページが使用されたときに、ディレクトリエントリが次のようになったことを認識しました。
+-----------+------------+---------+
| Dir Index | Unused | Control |
+-----------+------------+---------+
エントリのDirインデックスとコントロール領域は同じでしたが、それらの間の未使用ビットのブロック（存在していればページインデックスによって使用される）は無駄でした。そこで彼らはその領域を使用して31より上の物理アドレスの上位ビットを定義することにしました！
+-----------+------+-----+---------+
| Dir Index |Unused|Upper| Control |
+-----------+------+-----+---------+
これにより、PAEモードを採用していないOSでは4 GB以上のRAMにアクセスできるようになりました。余分なロジックを追加すれば、各プログラムに通常の4 GBを超えることはありません。最初は4ビットしか追加されず、36ビットの物理アドレス指定が可能なため、このモードはPage Size Extension 36（PSE-36）と呼ばれていました。しかし、実際にはページサイズは変更されませんでしたが、アドレス指定だけが変更されました。
ただし、この制限は4GB以上のページしか定義できないということでした.4Kページは許可されていませんでした。このモードの採用は広範ではありませんでした .PAEを使用するよりも速度が遅いと報告されています.Linuxはこれまで使用していませんでした。
それにもかかわらず、物理アドレスビットがさらに増えた後のプロセッサでは、AMDとインテルの両方がPSE領域を8ビットに広げました。これは「PSE-40」と呼ばれ、