仮想メモリ方式の分類

作成日：2006.03.30
修正日：2016.10.17

更新記録
(2006.03.30) 2006/3/10 と2006/3/11 の日記の内容を元に作成。
(2006.04.07) SPARC 32 ビットプロセッサのページテーブル構成を修正。
(2006.05.25) 3.2節ページテーブルエントリを追加。
(2012.05.29) PowerPC のセグメントサイズの誤りの修正と図の追加。
(2016.10.17) Intel64 の Process-Context Identifiers(PCIDs) と Protection Keys の説明を追加。また TLB エントリの無効化と ARM の情報も追加。タイポの修正。

1. はじめに
2. 仮想メモリの全体像とページング以外の機構
- 事前処理
- 事後処理
3. ページング
4. アーキテクチャ別の詳細
コメント

1. はじめに

仮想メモリ方式 (Virtual Memory System) は、ハードディスクをメモリの退避領域として使うことで、搭載メモリ量よりも多くのメモリがあるように見せかける技術だ。この機構の実現のためにプロセッサの内部にある Memory Management Unit (MMU) が中心的な役割を果たす。

このドキュメントは仮想メモリの教科書的な解説は省き、各マイクロプロセッサの MMU がどのような特徴を持っているかを解説する。

2. 仮想メモリの全体像とページング以外の機構

仮想メモリの中心的な仕事は、「仮想アドレス」を「物理アドレス」に変換することにある。この処理のことをページング(paging)と呼ぶのだが、各アーキテクチャはページング機構の周りに附属的な処理をいろいろ行っている。仮想メモリ方式はこの附属物によって、分類することができる。

とりあえず附属機構の解説のために、この文書では以下のように用語を定義する。

ユーザープロセスから見たときにロード・ストア命令で直接指定するアドレスを論理アドレス(logical adderss) と呼ぶことにする。
ページングを行う前のアドレスを仮想アドレス(virtual adderss) と呼ぶことにする。
ページングを行った後のアドレスを実アドレス(real adderss) と呼ぶことにする。
物理的な実体を持っていてメモリバスで指定できるアドレスを物理アドレス(physical adderss) と呼ぶことにする。

ロード・ストア命令から物理メモリまで以下の図のような変換経路をたどる。アーキテクチャによってページングの前後におまけがつくことになる。

まず、おまけ機構について見ておこう。

2.1 事前処理

System/370、SPARC、MIPS、Alpha のようなアーキテクチャでは論理アドレス＝仮想アドレスとなる。しかし IA-32、AMD64、PowerPC、PA-RISC、IA-64 では論理アドレスから仮想アドレスへの変換を行う機構が入る。

この変換は IA-16 (8086) のことを思い出すと分かりやすい。 IA-16 で直接行えるメモリアドレッシングは 16 ビットだった(これが論理アドレスに相当)。別にセグメントレジスタと呼ばれる 16 ビット幅のレジスタ群があり、メモリアクセスはセグメントレジスタのどれかによって修飾されて実行されていた。実際にアクセスされるメモリアドレスは(セグメントレジスタ) × 16 + (オフセットアドレス) によって合成されていたので、論理アドレスの制限(16ビット)を越えて 20 ビット幅のメモリまでアクセス可能になっていた。

PowerPC(セグメンテーション) や IA-64(リージョン)は、IA-16 のセグメンテーションと同じような仕掛けで論理アドレスよりも大きな仮想アドレスを使用可能にする。 IA-64 では 64 ビット論理アドレス空間を 2^61 毎に 8 分割し、分割されたメモリ帯に 24 ビット値 << 61 のリージョン値が足され、仮想アドレスは 85 ビットとして扱える。

PowerPC も (32 ビット PowerPC、64 ビット PowerPC ともに) 論理アドレス空間が 16MB ごとに分割され、上位ビットが拡張される。結果 32ビット PowerPC なら仮想アドレスが 52 ビットに拡張され、64 ビット PowerPC なら仮想アドレスが 80 ビットに拡張される。

PA-RISC は Spacing という機構を持ち、IA-16/IA-32 のような命令を修飾するセグメンテーションと、IA-64 のような論理アドレス空間を分割するセグメンテーションの両方を組み合わせている。

IA-32 のセグメンテーションは IA-16 を継承しているが、通常はセグメントレジスタとオフセットアドレスを単純加算する仕組みになっているため、論理アドレスのサイズ＝仮想アドレスのサイズとなる。ただし FS セグメント修飾と GS セグメント修飾だけは、ベースアドレスの加算が行なわれる。

2.2 事後処理

ほとんどのプロセッサは実アドレスが物理アドレスと等しくなるが、筆者が知る限り System/370 だけが prefixing と呼ばれる事後処理を持っている。

S/370 は割り込みが発生した時の発生理由やプログラムカウンタ値の保存を、実アドレスの 0-511 バイトに記録する仕様になっている。どのアドレスに何が記録されるかは厳密に仕様によって決まっていて動かせない。

この仕様はマルチプロセッサ環境で問題になる。各プロセッサに固有の情報が同じ実アドレスに記録されると、衝突してしまうからだ。

S/370 は 4K バイトのページを持つのだが、衝突回避するために実アドレスの最底位の 0x0000 - 0x0fff (4Kバイト) とプロセッサ内のレジスタが指定する任意の 1 ページ(4K バイト) を入れ替える形で実アドレス空間と物理アドレス空間を対応関係を変えることができる。

3. ページング

仮想メモリの中核になるページングは、固定サイズのページを単位に仮想アドレスから物理アドレスの変換を行う。ページサイズが p ビットの場合、仮想アドレス m ビットの上位 m - p ビットが仮想ページ番号 (Virtual Page Number; VPN) となり、実アドレスが n ビットの場合には上位 n - p ビットが Physical Page Number (PPN) またはPage Frame Number (PFN) となる。ページングは VPN から PPN への変換を行い、ページ内のオフセットアドレスはそのまま適用される。

VPN から PPN への変換表(ページテーブル)は物理メモリ上に配置されるが、MMU 内の Translation Look-aside Buffer(TLB) がページテーブルのキャッシュを行い、メモリアクセスの度に TLB が変換を行う。

3.1 ページウォーク

TLB のエントリ数は 30 ～ 1,000程度のため、TLB ミスは頻繁に起こっている。TLB ミスが起きた場合、ページテーブルから該当するエントリを読み込む必要があるが、その際の処理をソフトウェアで行うものと、MMU 内のハードウェアで行うものの2種類が存在する。

ハードウェアによるページウォーク

ハードウェアによるページテーブルウォークは、プロセッサによってページテーブルの構成方法が決まっていて、TLB ミスが起こると MMU が自動で実メモリ上にあるページテーブルを検索し該当するエントリを探す。ページテーブルの構成方法は、だいたい2種類に分かれる。

2段から4段の階層テーブル方式
ハッシュテーブル方式

ページテーブルの構成がアーキテクチャによって決まってしまうので自由度がないが、ソフトウェアによるページウォークよりも高速である。

ソフトウェアによるページウォーク

ソフトウェア制御のページテーブルウォーカーは、TLB ミス時に例外ハンドラに処理が移り、ハンドラの中で専用命令などを使って TLB エントリを挿入する。そのためソフトウェアによるページウォーカーは、ページテーブルの構造を自由に決められる。極端な場合にはページテーブルを静的に作らないことも可能。またページサイズが自由に混在できるプロセッサが多い。

ただし処理自体はハードウェアによるページウォークと比べて低速である。そのためソフトウェアによるページウォークを採用している CPU にいは補助ハードウェアを持つものがある。 UltraSPARC や IA-64 はハッシュテーブル形式の補助ページテーブルをメモリ上に配置し、TLB ミスはまずハードウェアがハッシュテーブルを検索して、それでもエントリが見つからない場合のみページテーブルの検索をソフトウェア的に行う。

3.2 ページテーブルエントリ

ページテーブルウォークの結果、仮想ページに対応するページテーブルエントリ (Page Table Entry ; PTE)を見つけることができる。ページテーブルエントリはアーキテクチャによって決まる 4 ～ 16 バイトのデータ構造である。 32 ビットアーキテクチャでは 2 バイトか 4 バイト、64 ビットアーキテクチャでは 4 バイトか 8 バイトになっている。

PTE のフィールドの内容は、以下のようなフィールドが代表的だ。

無効 Invalid (I) ビット (その逆に有効 Valid ビット、存在 Present ビット)

この PTE が無効であることを示すビット属性 (あるいは有効であることを示すビット)。 I ビットが 1 の場合は、PTE の残りのビットフィールドが無視されるアーキテクチャが多い。
OS は I ビットが 1 の場合は、

この仮想ページがマップされていない。
この仮想ページの内容がディスクに書き出されている(ページ・アウトされた)。

の二つの意味をもたせる場合が多い。無視された残りのビットフィールドを使って、スワップディスクのどの位置に書き出されたかを記録したりする。

Physical Page Number (PPN) あるいは Real Page Number (RPN)

仮想ページを変換する実ページを示すビット。
VPN を PPN に変換するのがページングの役割であるから、もっとも重要なフィールドだ。

特権レベル Privilege Level (PL)

ページの特権レベルをあらわすフィールド。
この特権よりも低い特権の CPU がアクセスすると、特権違反例外やそれに類する CPU 割り込みが起きる。
PL フィールドは、1 ビットで User ページと Supervisor ページをあらわすアーキテクチャや、数ビットを使って PL0 ～ PL3 ぐらいまで設定できるアーキテクチャなど色々ある。

アクセス権 Access Rights

数ビットを使ってページのアクセス属性をあらわす。
ふつう読み込み(RD)・書き込み(WR)・実行(EX)に関して許可・禁止を設定できる。 UNIX API の mprotect(2) はこの機能で反映され、違反するとアクセス権限例外やそれに類する CPU 割り込みが起きる。

アーキテクチャによっては、RD・WR・EX がそれぞれ独立して指定できるもの、(No eXecute 導入以前の) IA-32 のように実行の設定ができないもの、「書き込みは許可するが読み込み禁止」といった細かいパターンがないものが存在する。

特殊なアクセス権限パターンとしては、PA-RISC と IA-64 にある特権昇格ページというパターンがある。特権昇格ページ内のコードは低特権時でも実行可能で、その中に置かれた特殊な命令を実行すると特権が昇格する。 OS はこのページをシステムコールの入り口を実装するために利用する。

アクセス Access (A) ビット/ダーティ Dirty (D) ビット (あるいは参照 Reference (R) ビット/変更 Change (C)ビット)

このページになんらかのメモリアクセスが成功すると A ビットに 1 が立ち、書き込みが成功すると D ビットに 1 が立つ。ビットがいったん 1 になると、明示的にゼロクリアされるまではそのままになる。

この A/D ビットは物理メモリが不足した時に、ページアウトするページを選ぶために使われる。ページアウトするページは「最後の参照から最も時間が経過しているページ」を選びたいのだが、時刻管理をまじめに行うのはオーバーヘッドが大きい。定期的に A/D ビットをクリアして次のインターバルまでに A/D ビットが立つかどうかで、「最近参照がないページ」を大雑把に探している。

3.1節で述べたページウォークをハードウェアで行うアーキテクチャは PTE を A/D ビットを自動的にオンにしてくれるが、ページの解決をソフトウェアによるアーキテクチャは、A/D ビットを立てるのもソフト制御の場合が多い。

ページサイズ Page Size

ページの大きさをあらわす数ビットのフィールド。
ページサイズが固定なアーキテクチャでは存在しない。

メモリ属性

メモリの属性を指定する。通常モード以外に、メモリの順序性を緩めるページ、キャッシュしない・ライトスルーするページなどを指定可能になる。

グローバル Global (G) ビット

3.3 節で説明するが IA-32 や x86-64 ではプロセススイッチが起きる時に TLB をフラッシュする必要がある(ただし Intel64 は PCIDs を使うと、プロセススイッチの度の TLB フラッシュを回避できる)。
しかしプロセス間で共有なページ(例えば IA-32/Linux は 3 GB 以上のカーネル領域は、全てのプロセスで同一のマップがされている)も存在し、そのエントリは TLB からフラッシュされて欲しくない。 G ビットはこの PTE を TLB 上にピンしておいて、プロセススイッチ時などの TLB の一斉解放ではフラッシュしないで欲しいということを指示するビット。

SPARC V9 や PowerPC 系には、意味が少し違うが似たような属性ビットがある。
S/370 には PTE ではなく、セグメントテーブルエントリに Common Segment Bit があり、全ての仮想メモリ空間で共通なメモリ領域を示すことが指定できた。

Key、Access ID、Context

Key (IA-64)、Access ID (PA-RISC 2.0)、SPARC (Context) は PTE 中にあるキー情報で、CPU 内にあるキーとマッチしなければアクセスできず例外となる。
Intel64 も Protection Keys が導入された。

その他

アーキテクチャによってはさらに特殊な属性ビットが存在する。

エンディアン逆転ビット: SPARC V9 はビッグ・エンディアンとリトル・エンディアンの両方が使え、CPU の制御レジスタビットでどちらかを選択可能だ。さらに仮想ページ単位での設定も可能で、このビットが立っているページはエンディアンが反転してアクセスされる。
条件分岐予測(predication method for branching): PA-RISC 2.0 に存在する属性ビットで、このビットによってページ内の命令の条件分岐予測の有効・無効を切り替えられる。
Speculative Load、Non-faulting load: IA-64、SPARC V9、x86-64 などに存在する、投機ロード、ノン・フォルト・ロード用。
デバッグ用: PA-RISC 2.0 に存在する属性ビットで、データアクセス時/メモリ書き込みにデバッグトラップが発生する。

ソフトウェア用の予約ビット

OS が独自の用途に使えるように残してあるビット。

3.3 マルチタスクOS でのプロセスの切り替え

プリエンティブマルチタスク OS では、複数のプロセスがタイムスライスで切り替わりながら処理を進めている。同一の論理アドレスでもプロセスが変われば異なる実メモリページにマップされ、異なる内容を保持している。

そのためマルチタスク OS では、プロセスの論理アドレスが単純に仮想アドレスに変換されると TLB 内でエントリの衝突が起きてメモリ保護に矛盾が発生する。この矛盾を回避する方法は、以下の 3 種類に分類できる。

プロセススイッチ毎に TLB をフラッシュする: プロセススイッチ時に TLB をフラッシュすることで、仮想アドレスの衝突を解決している。この方法は TLB エントリを無駄にパージする可能性が高く効率が悪い。
Segment Table Origin(STO): プロセスのページテーブル構造は物理アドレス空間中でそれぞれ別のアドレスを持っている。そのためページテーブル構造の先頭アドレスを TLB エントリ中に埋め込むのが合理的である。
System/370 は 2 段のページテーブル構造を持ち、1 段目をセグメントテーブル(Segment Table)と呼ぶ。そして Segment Table のアドレスを Segment Table Origin(STO) と呼ぶ。 System/370 は制御レジスタの CR0 に STO をセットすることでプロセス空間(に相当するもの)を切り替えるが、TLB エントリには STO が記録されるので異なるプロセス空間の同一の仮想ページが TLB 中で衝突することはない。
ただし System/370 は 4 KB/page で 31 ビットアドレス空間を持つので、TLB エントリは仮想ページのタグ 19 ビット + STO のタグ 19 ビットとかなり大きくなってしまう。
アドレス空間識別子(ASI): TLB のエントリに Virtual Page Number (VPN) 以外にメモリ識別子を埋め込む。 TLB は VPN + ASI を使って検索を行うので、プロセス毎に異なる ASI を与えれば衝突しない。 ASI はアドレス空間/コンテキストを識別できる自由な番号を挿入する。 Intel64 にはプロセスコンテキスト識別子(Process-context identifiers; PCIDs)という名前で導入された。
ASI は 12 ビット前後で STO よりもビット数が少ないことが多い。
Single Address Space: システム(OS)内に仮想アドレス空間を一つだけ用意するような仮想メモリの使い方を SAS (Single Address Space) と呼ぶ (逆に OS 内に複数のメモリ空間があるようなものをMAS (Multiple Address Space) と呼ぶ)。 SAS の場合には TLB の衝突は発生しない。
SAS だとプロセス毎のメモリ保護をどうするのかという疑問が湧くが、2.1 節で述べたようにプロセッサの中には論理アドレスよりも大きな仮想アドレスを持つアーキテクチャがある。このようなアーキテクチャでは OS に一つだけ巨大な仮想アドレス空間を用意して、プロセス毎の論理アドレスをその中にマップしてしまうという構成方法が取れる(SAS はこのようなアーキテクチャでのみ有効)。 TLB から見ると、異なるプロセスの同一論理アドレスは異なる仮想アドレスにマップされるので TLB エントリの衝突は生じない。

各方式のメリット・デメリットを述べるなら、TLB フラッシュは他の方式に比べて性能が悪い。 ASI、STO、SAS を比べた場合、OS が何千～何万というプロセスを生成させると ASI のビット幅は同時走行するプロセス数をカバーするのに十分でないため、プロセスと ASI のマッピングに工夫が必要となる。 STO と SAS は ASI よりもビット幅が大きいためにより多くのプロセス数をカバーできる。逆説的には構造的に STO や SAS が提供するビット幅が OS で動作する最大プロセス数を規定することになる。

アーキテクチャごとの方式は表1 のプロセス切替の欄にまとめておく。

3.4 TLB エントリの無効化

プロセス内のメモリ空間は mmap() や mprotect() のようなシステムコールによって稼働中に変更を受ける。この時、ページテーブル構造の一部分を書き換えるのだが、書き換えと同じ箇所の情報が TLB に載っている場合、該当する TLB エントリを無効化する必要がある。

商業コンピュータシステムとして仮想メモリ方式を最初に導入した System/370 は Invalidate Page Table Entry(IPTE) という命令を導入した。 IPTE 命令は実アドレス上(実質、物理アドレス上)のページテーブルエントリを指定すると、そのページテーブルエントリから生じた TLB エントリを無効化する命令である。他のアーキテクチャの TLB エントリの無効化命令は論理/仮想アドレスを指定する。

System/370 の IPTE 命令は、IPTE 命令を実行した CPU の TLB エントリを無効化するだけではなく、SMP システム構成内の全 CPU に対して TLB エントリ無効命令をブロードキャストする。 IPTE 命令は全ての CPU の TLB エントリ無効化が完了した後に終了する。有効だが極めて重い命令である。

PowerPC には IPTE と同様に他のプロセッサの指定の TLB エントリを無効化する TLB Invalidate Entry(tlbie) 命令がある。ただし tlbie 命令は他のプロセッサが TLB エントリを無効化するのを待たずに終了する。他の CPU が TLB エントリを無効化したことを検査するには TLB Synchronize(tlbsync) 命令を使う。 tlbsync 命令が完了すると、先行する tlbie 命令が出した TLB エントリの無効化は完了したことが保証される。

IA-32 や x86-64 には Invalidate TLB Entries (INVLPG) 命令がある。 INVLPG 命令はこの命令を実行した CPU 自身の TLB エントリを無効化するが、他の CPU には影響を与えない。マルチスレッドプロセスのメモリ空間を変更している場合には、ページテーブル構造体を変更した影響は SMP システム構成内の全 CPU から TLB エントリを無効化する必要がある。 IA-32 や x86-64 は命令レベルではこれを保証する機構がなく、Inter-Processor Interruption(IPI) のような CPU 間通信を使いながらソフト的に全 CPU をカバーする必要がある。

アーキテクチャごとの方式は表1 の TLB エントリ無効化の欄にまとめておく。

3.5 キャッシュの記録するアドレス

TLB とは少し離れるが、メモリキャッシュもアドレスを記録している。このキャッシュ内のアドレスが仮想アドレスで記録されるか、実アドレスで記録されるかはプロセッサによって異なる。

仮想アドレスで記録している場合、論理アドレス→仮想アドレスの変換を行うだけでキャッシュの検索が可能になる。そのため非常に高速に処理できる。ただし同一物理メモリが複数の仮想アドレスにマップされるエイリアスの問題や、3.3 節で述べたプロセス切り替えによる TLB 処理への対応が必要になる。
実アドレスで記録する場合、エイリアスやプロセス切り替えによる矛盾は発生しない。ただしキャッシュ検索を行う前にページング変換によるアドレス変換が必要なので、各ロード・ストア処理が低速になる。

現在のプロセッサは、高速なアクセスが必要な L1 キャッシュでは、仮想アドレスで記録を行うものが多い。キャッシュと TLB は連動しており、TLB エントリが削除されるとキャッシュもパージされるといった処理を行い、矛盾を防いでいる。

L2 以降の比較的大容量のキャッシュは、仮想アドレスで記録するものと実アドレスで記録するものの両方タイプが存在する。

4. アーキテクチャ別の詳細

ここからはアーキテクチャ毎の仮想メモリの詳細を列挙する。

表1: アーキテクチャ毎の仮想メモリ方式の特徴
アーキテクチャ	CPU	論理	仮想	物理	TLB walker	ページサイズ	プロセス切替	TLBエントリ無効化	備考
System/370	XA 以前	32	24	24	Hard	2KB	STO	IPTE (グローバル)
System/370	XA 以降	32	31	31	Hard	4KB	STO	IPTE (グローバル)
IA-32	i486以前	32	32	32(?)	Hard	4KB	TLBフラッシュ	INVLPG (ローカル)
IA-32	Pentium	32	32	32	Hard	4KB、4MB(?)
IA-32	Pentium Pro	32	32	36	Hard	4KB、4MB
AMD64/Intel64		64	48	52	Hard	4KB、2MB、1GB	TLBフラッシュ ASI(*)		ASI が使えるのは PCIDs 導入以降
PowerPC 32-bit	MPC750	32	52	32	Hard	4KB	SAS	tlbie (グローバル)
PowerPC 64-bit	PowerPC 970	64	80	62	Hard	4KB、16MB	SAS	tlbie (グローバル) tlbiel (ローカル)	仕様上はページサイズを 2¹²～2²⁸ バイトに変更できるが、本当にとれるページサイズは CPU の実装による。
SPARC 32-bit		32	32	36	Hard	4KB	ASI	?
SPARC 64-bit	UltraSPARC III	64	64	43	Soft + Support Hard	8KB、64KB、512KB、4MB	ASI	?
PA-RISC 32-bit		32	52	32	Soft	4KB、32KB	SAS	PDTLB、 PITLB (グローバル) PDTLBE、PITLBE (ローカル)
PA-RISC 64-bit		32	96	62	Soft	4KB～64MB (4倍刻み)	SAS	PDTLB、 PITLB (グローバル) PDTLBE、PITLBE (ローカル)
MIPS 32-bit	R3000	32	32	?	Soft	?	ASI	?
MIPS 64-bit	R12000	64	44	40	Soft	4KB～16MB (4倍刻み)	ASI	?
Alpha	21264	64	48	44	Soft	8KB	ASI	PAL_tbi (?)
IA-64	Itanium2	64	85	50	Soft + Support Hard	4KB～256MB(4倍刻み) + 8KB	SAS	ptc.l (ローカル) ptc.g、ptc.ga (グローバル) ptc.e (ローカル)
ARM 32-bit (AArch32)		32	32	32	Hard	4KB、64KB	ASI	?	オプションで物理メモリを 40 ビットに拡張できるがページサイズが 16MB になる。
ARM 64-bit (AArch64)		64(56)	48	48	Hard	4KB、16KB、64KB	ASI	?	論理アドレスの上位 8 ビットがタグになっている。

以下の説明では各アーキテクチャ毎の用語を使うので 2.で定義した用語とは若干ずれるので注意。

IBM System/370

System/370 は仮想メモリ機構を備えた最初の商業コンピュータシステムである。

31 ビット仮想アドレス空間と 31 ビット物理アドレス空間を持つ。物理アドレスは後にだんだん拡張された。
ページは最初 2KB/page だったが、後に 4KB/page に拡張される。 ESA/390 以降は 4KB/page のみ。
仮想アドレスの上位 19 ビットが VPN。下位 12 ビットがページ内のオフセットとなる。
TLB ミス時のページテーブルウォーク(page table walk) はハードウェアによって行われる。
ページテーブルの検索は 2 段階で行われ、1段目のテーブルを Segment-Table、2段目のテーブルを Page-Table と呼ぶ。
1. まずレジスタ中に Segment Table の位置(Segment Table Origin) が書かれていて、そこを Segment-Table とする。
2. VPN の上位 m ビットをインデックスとして Segment_Table[VPN の上位 m ビット] を検索すると、Page Table の位置(Page Table Origin) へのポインタが得られる。
3. Page_Table[VPN の下位 19 - m ビット] でページテーブルエントリが得られる。
4. ページテーブルエントリの中に物理メモリページ番号(PPN) が書かれている。
VPN の区切りである m はプロセッサ中のコントロールレジスタで調整可能。
Prefixing 機構
- S/370 は物理アドレスの低位のアドレス (0～511) を、割り込み時のプロセッサ情報を書き出しのためなどに使用する。そのためマルチプロセッサにこの低位アドレスがバッティングする。
- このバッティングを回避するために、本当の物理アドレス空間(Absolute Address Space) とプロセッサから見た場合の擬似物理アドレス空間 (Real Address Space) と二重化がなされている。 Absolute Address Space と Real Address Space の違いは、最下位の 1 ページとプロセッサの prefix register が指すページが入れ替わってみえることである。これが prefixing。
- Prefixing は VA-PA 変換の後の Real Address に対して適用される。
仮想メモリの機構ではないのだが、ストレージ・キー (Storage Key) と呼ばれる機構が存在する。
System/370 は物理メモリもページ分割されており、物理ページ毎に 7 ビットの情報が付加されている(これがストレージ・キー)。
- ストレージ・キーは 4 ビットの ACcess-Controlled (ACC) ビット、1 ビットの Fetch-Protection (F) ビット、1 ビットの Reference (R) ビット、1 ビットの Change (C) ビットを持つ。
- CPU 内の制御レジスタの一部に 4 ビットのキー情報が存在する。メモリへの書き込みが行われる際に、CPU のキーとページの ACC ビットの比較が行われ、一致しないと書き込みができずプロテクション割り込みが発生する。これを Key-Controlled Protection と呼ぶ。
- ページに F ビットが立っている場合、メモリの読み込みにも Key-Controlled Protection がはたらくようになる。
- メモリへのアクセスがあった場合には R ビットに、アクセスが書き込みの場合にはさらに C ビットに自動的に 1 が書き込まれる。
- プログラムからは専用命令でストレージ・キーを読み書きできる。
つまりストレージ・キーは、3.2 節で説明した Access Rights と R/C ビットと Key と同様の機能を提供できる。ただし他のアーキテクチャが TLB/MMU によって仮想アドレス空間上で実現している機能を、物理アドレス空間上で実現しているのが特異だ。
TLB の各エントリは Segment Table Origin (20-bit) と VPN (20-bit) を組み合わせて、メモリアクセス時には CR0 と論理アドレスの両方をキーにして検索する。プロセス毎に STO が異なるので複数プロセス分の TLB エントリが混在できる。

ESA/370 には dual address space facility が追加され primary space mode 以外にもう一種類アドレス機構を持てるように拡張された。 System/390 以降はアドレスモードが 4 種類に増え、primary space mode 以外に secondary space mode、home space mode、address-register specified space mode が使えるようになっている。ただしページングの起点となる STO を格納する場所が違う点を除くと、どのモードも大差がない。

x86、IA-32

i386 以降の x86、つまり IA-32 は 32 ビット CPU で、32 ビットの仮想アドレス空間と 32 ビットの物理アドレス空間を用いる。
IA-32 の VM はセグメンテーション＋ページングという2段階システム。
ユーザーランドのメモリアドレスを論理アドレスと呼ぶ。論理アドレスは DS、FS、GS、SS、CS といったセグメントレジスタによる修飾を受け、ゲタを履かされる。つまり論理アドレス + α(セグメントレジスタ)という修正を受け、これがリニアアドレスとなる。これが x86 のセグメンテーション。
リニアアドレスはページ単位仮想メモリであるページング処理の対象となる。 IA-32 は 4KB/page が基本なので下位 12 ビットがオフセットアドレスで、上位 20 ビットが VPN となる。
TLB ミス時のページテーブルウォークはハードウェアが行う。このページテーブルも 2 段階。ただし 20 ビットの VPN は、10ビット : 10ビットに分けると固定されている。またセグメントテーブルとページテーブルの大きさは 4KB となる。
Pentium 以降のプロセッサにはページ拡張モード(Paging Size Extensions; PSE)があり、仮想ページを 4MB/page に広げられる。この場合はページテーブルの一部が 1 段階になり、上位 10 ビットが VPN で下位 22 ビットがオフセットになる。
Pentium Pro 以降のプロセッサには物理アドレス拡張(Physical Address Extention; PAE)があり、物理アドレスを 36 ビット (64ギガバイト) まで拡張できる。
ページング変換は CR3 レジスタの指すページテーブルから検索を開始する。タスクスイッチを行うか CR3 レジスタを変更すると (基本的に) TLB はフラッシュされる。

x86-64、AMD64、Intel64、IA32m、EM64T

AMD64/EM64T (のロングモード) は 64 ビット CPU だが、仮想アドレス空間は 48 ビットに制限されている(上位 16 ビットは予約)。これは TLB ミス時のページテーブルウォークがハードウェアゆえの縛り。物理アドレス空間は最大 52 ビット(今後の拡張のための予約ビットも含める)。
基本は 4KB/page で下位 12 ビットがオフセットアドレスになるので、中の 36 ビットが VPN になる。ページテーブルウォークの際には 36 ビットの VPN を 9 ビットづつ 4 つに区切って、4レベルのページテーブルを検索する。
IA-32 の PSE と同様の方法で 2MB/page のモードが使える。この場合は 4 レベルページテーブルの最後の一段がなくなり、ページテーブルの一部が 3 レベルになる。
AMD64 にもセグメンテーションはあるのだが、ほとんど無視できる。
TLB は CR3 レジスタの指すページテーブルから検索を開始する。タスクスイッチを行うか CR3 レジスタを変更すると (基本的に) TLB はフラッシュされる。
- CR3 レジスタの変更でフラッシュの弱点を回避するために Process-Context Identifiers(PCIDs) が導入された。これは SPARC や MIPS のアドレス空間識別子と同様の機構である。 TLB のエントリに 12 ビットのタグを埋め込み、コンテキストスイッチで以前のプロセスの TLB エントリが全フラッシュされることを回避している。
  - CR4.PCIDE=1 の場合、INVLPG 命令によって無効化される TLB エントリは現在 CR3 が選択している PCID 空間内のものとなる。
  - PCID 機能のために INVPCID 命令が追加された。INVPCID 命令は指定した PCID に属する全 TLB エントリをフラッシュする、G ビットの立っていない全 TLB エントリをフラッシュする、G ビットが立っているものも含めて全てフラッシュするという機能が使える。他に INVPCID 命令は INVLPG 命令と同様の機能がある。
  - CR3 レジスタを変更する場合、MOV TO CR3 が CR3 の設定値となるソースオペランドの最上位ビット(bit 63) に 1 を立てて CR3 を設定した場合は TLB エントリはいずれも無効化されない。ソースオペランドの最上位ビットに 0 を立てた場合、CR3 に切り替わる前にソースオペランドの 0～11 ビットの指定する PCID に属する TLB エントリが無効化される。なおソースオペランドの最上位ビットを 1 に指定して MOV TO CR3 を実行しても、CR3 レジスタの最上位ビットは 0 のままとなる。
- なお PCIDs は Intel64 の IA-32e のみの機能で、32 ビットモードでは使えない。
Intel64 の IA-32e モードには Protection Keys と呼ぶアクセス制限が導入された。これは仮想ページに 0～15 のキー値を設定し、CPU 側でどのキーにアクセス可能かを設定する機能である。この機能を使うと例えば同一メモリ空間を共有するマルチスレッドであっても、特定のスレッドからはアクセス禁止・書き込み禁止の領域を作成できる。ただしこのアクセス制限はユーザーモードのみで有効で、スーパーバイザーモードでは効果はない。
- ページテーブルエントリの最上位ビット XD(execute-disable) に続く 4 ビットに protection key を設定する。
- PKRU(Protection key rights register for user pages)レジスタがアクセス可能なキーを制御する。 16種類のキーに対してそれぞれ 2 ビットの制御情報を持ち、各キーにアクセス禁止・書き込み禁止を設定できる。 PKRU レジスタは RDPKRU 命令と WRPKRU 命令で読み書きする。
- Protection key 違反で #PF 例外が発生した場合、スタック上に積まれるエラーコードの 5 ビット目が PK ビットとなる。 Protection-key が原因で #PF 例外が発生した場合、PK ビットが 1 となり protection-key violation であることが判明する。

PowerPC 32 ビット

32 ビット PowerPC は、IA-32 と同様にセグメンテーション＋ページングの2段階を行う。プログラム中に使用されるメモリアドレスは effective address と呼ばれ 32ビットだが、セグメンテーションを受けることで virtual address に変換される。 virtual address は 52 ビット。virtual address がページングによって phsyical address に変換される。
PowerPC のセグメンテーションは、effective address を 16 MB 毎に区切ってセグメントと呼んでいる。つまり effective address の上位4ビット毎に別セグメントとして区別される。この上位 4 ビットを virtual segument ID と呼ぶ。
プロセッサ中に 16 本のセグメントレジスタがあり、上位 24 ビットのアドレスを保持している。
```
char* Segment_Registers[16]  /* 上位24ビット */
```
セグメントレジスタの値と effective address の下位 28 ビットを足したものが TLB から見た場合の virtual address になる。
セグメントレジスタの値はプログラム中で変更できるので、 24 + 28 で 52 ビット分の仮想アドレス空間を持っていると考えることもできる。

Programming Environments Manual for 32-Bit Implementations of ther PowerPC™ Architecture
PowerPC はページングは 4KB/page が基本。 TLB ミス時のページテーブルウォークはハードウェア制御。 Virtual address の上位 20 ビットを VPN とし、ハッシュ検索されるページテーブルを持つ。テーブルのサイズ等は調整可能。

PowerPC 64 ビット

64 ビット PowerPC では 64 ビット effective address と、セグメンテーションを行うことにより 80 ビット相当の virtual address が使える。 Physical address は 62 ビット。
セグメンテーションは 64 ビットのうち上位 36 ビットで行い、52 ビット分の virtual address のベースを作る。
32 ビット PowerPC の場合には 4GB を 16MB づつ 16 分割すればよかったのだが、64 ビット PowerPC でも 16MB で分割するので 2^36 (=68,719,476,736) 分割になる。 32 ビット PowerPC と違い char* Segment_Registers[68,719,476,736] のようなデータ構造を作れないので、TLB に似た Segment Lookaside Buffer (SLB) という機構を設けて Effective Segment ID から Virtual Segment ID への変換をキャッシュする。 SLB がミスした場合は、ソフトウェア的に物理メモリにセグメント情報を検索に行く。

IBM PowerPC® Microprocessor Family: The Programming Environments Manual for 64-bit Microporcessors Ver 3.0
ページングの仮想ページサイズは 4KB/page が基本だが、仕様上は 2¹² から 2²⁸ まで自由なページサイズを使える。実際の実装としては PowerPC 970 が 16MB/page のラージページが使える。
TLB ミス時のページテーブルウォークはハードウェア。

SPARC 32 ビット (SPARC V8)

SPARC V8 のプロセッサは 32 ビットの仮想アドレス空間と 36 ビットの物理アドレスをサポートしている。
仮想ページサイズは 4KB/page 固定。 20 ビットの VPN が 24 ビットの Pyshical Page Number (PPN) に写像される。
TLB ミス時のページテーブルウォークはハードウェア。
ページテーブルは 3 段階で構成され VPN が上位から 8 ビット : 6 ビット : 6 ビットに分割される。
TLB の各エントリに context indentifier と呼ばれるタグ領域があり、検索時にプロセッサ中の context register と比較される。一致しないエントリは VA-PA 変換できない。一般には OS のプロセスの番号を context indentifier として与える。

SPARC 64 ビット (SPARC V9)

SPARC V9 は 64 ビットの仮想アドレスと 43 ビットの物理アドレスをサポートしている。
仮想ページサイズは 8KB/page、64KB/page、512KB/page、4MB/page をサポートしているが、同一仮想メモリ空間内で混在可能。
TLB ミス時のページテーブルウォークはソフトウェア(主にOS)が行う。
SPARC V9 の仕様には出てこないが、UltraSPARC には Translation Storage Buffer (TSB) と呼ばれる TLB ミスハンドリングを助けるハードウェア機構が存在する。 TSB は頻繁にミスするページテーブルエントリを登録しておくキャッシュ。プロセッサは TLB ミスが起こった時にまず TSB 内のデータを検索する。 TSB に見つからない場合に TLB ミス例外を発生させる。
TSB は (VPN, ページテーブルエントリへのポインタ) の組を保持したダイレクトマップ。
TLB の各エントリ context indentifier と呼ばれる 13 ビットのタグ領域があり、検索時にプロセッサ中の context registers と比較される。プロセッサ内の context register は primary と secondary の2本があり、どちらかに一致すればよい。一致しなければ VA-PA 変換は行わない。

PA-RISC 32ビット (PA-RISC 1.1)

32ビットの仮想アドレス空間と 32 ビットの物理アドレス空間を持っている。
仮想ページは 4KB/page が基本で、32KB/page のラージページを持っている。
PA-RISC は 8 つの Space の概念を持っていて、IA-32 や PowerPC のセグメントテーションのようにアドレスにゲタを履かせることができる。ゲタの値は Space Registers[8] にセットされている。この中に最大 20 ビットの Space ID が入っている。そのため仮想メモリ空間を 32 + 20 = 52 ビット相当まで広げることができる。
どのアドレスがどのスペースを使うかは2種類の方法があり、コントロールレジスタによって決められる。一つはロード・ストア命令の中にある s-field でスペースを決める方法で、もう一つは virtual address の最上位 2 ビットによってスペースを決める方法(PowerPCに近い)である。
TLB ミス時のページテーブルウォークはソフトとハードのどちらでも良いが､ PA-RISC にはハード TLB の定義はない。

PA-RISC 64ビット (PA-RISC 2.0)

64ビットの仮想アドレス空間と 64ビットの物理アドレス空間(ただしメモリとして使えるのは 62 ビットまで)を持つ。
Space ID の仕組みによって +32 ビットで 96 ビット分の Global Virtual Adress (GVA) が使える。
ページは 4KB/page ～ 64MB/page (4倍刻み)に設定可能。
TLB ミス時のページテーブルウォークはソフトとハードのどちらでも良いが､ PA-RISC 仕様にはハード TLB の定義はなく、64 ビット PA-RISC プロセッサにはハードページテーブルウォーカーを持つものはない。

MIPS 32 ビット

32 ビットの仮想アドレス空間(ユーザー側で使えるのは31ビットまで)と 29 ビットの物理アドレス空間を持つ(R3000)。
ページサイズは 4KB だったような気がする。
プロセス(メモリ空間)の識別のために Address Space Identification (ASID) という 8 ビットの値がある。 TLB 内からエントリを探す時は ASID:VPN の組み合わせで検索を行っている。
TLB ミス時のページテーブルウォークはソフトウェア制御。

MIPS 64 ビット

44 ビットの仮想アドレス空間と 40 ビットの物理アドレス空間を持つ (R10000 以降)。
仮想アドレスは 64 ビット分あるが、上位 5 ビットと下位 44 ビット分が使われ、中間の 15 ビットは無視される。
ページサイズは 4KB ～ 16MB/page まで 4 倍刻みで設定できる。
TLB ミス時のページテーブルウォークはソフトウェア制御。
プロセス(メモリ空間)の識別のために Address Space Identification (ASID) という 8 ビットの値がある。 TLB 内からエントリを探す時は ASID:VPN の組み合わせで検索を行っている。

Alpha

48 ビットの仮想アドレス空間と 44 ビットの物理アドレス空間を持っている (21264)。
8KB/page が基本。この時は VPN は 31 ビット。
TLB ミス時のページテーブルウォークはソフトウェア制御。
プロセス(メモリ空間)の識別のために Address Space Number (ASN) という 8 ビットの値がある。 TLB 内からエントリを探す時は ASN:VPN の組み合わせで検索を行っている。

IA-64、IPF

IA-64 アーキテクチャは、非常に多彩な仮想メモリ機構を持っている。

64ビットの仮想メモリ空間と 50 ビットの物理メモリ空間を持っている。
PowerPC のセグメンテーションと同様の Virtual Region と呼ばれる機構を持つ。仮想アドレスの上位 3 ビットが Virtual Region Number (VPN) で、仮想メモリ空間が 2^61 で 8 つに分割される。プロセッサ内の Region_Register[8] は 24 ビットのゲタを持っていて、TLB から見たときに 24 + 61 ビットで 85 ビットの仮想メモリ空間に見える。
ページサイズは 4KB、8KB、16KB、64KB、256KB、1MB、4MB、16MB、64MB、256MB から選択可能。 TLB 内で自由に混在可能。
Itanium2 では 1GB、4GB も使用可能。
ページテーブルウォークはソフトウェア制御。
ページテーブルウォークをハードウェアで補助する Virtual Hash Page Table (VHPT) がオプションで存在する。 VHPT は SPARC の TSB と同様の機構。
- VHPT は仮想メモリ空間に置かれる。 1ページあたり32バイトのエントリ形式を持つロング形式と、1ページあたり8バイトのエントリ形式を持つショート形式の2種類が使える。ロング形式は IA-64 TLB の全てのデータを充填可能で、エントリ毎にページサイズ・保護キーを持てる。ショート形式は IA-64 TLB の一部のデータしか充填できず、ページサイズはリージョン毎に固定で保護キーは使えない。
- ロング形式の場合には VHPT はハッシュテーブルとして構成され、VPN 値をハッシュ化して検索される。ロング形式 VHPT は 2^64 の仮想アドレス内に1個だけ存在し、CR8 レジスタによってアドレスとサイズが指定される。
- ショート形式の場合には仮想アドレス空間のリージョン毎に配置される(一般的には各リージョンのお尻の部分に VHPT を配置する)。ショート形式 VHPT はハッシュテーブルではなく、リージョン内の全てのページにつき 8 バイトづつのエントリが並んだ巨大なリニアページテーブルとして構成される。リージョン内は一つのページサイズに固定されるので、仮想アドレスをページサイズで割ったものがリニアページテーブルのインデックスとなる。
  例えばリージョンを 16KB/page (2^14) で設定した場合、ショート形式の VHPT はリージョン空間の全ページ 2^(61-14) 個のエントリを持つ配列となる。
- ショート形式のエントリは 8 バイトなので 16KB/page 設定の場合には VHPT は 2^(61-14+3) = 2^50 になり、非常に広大なアドレス空間を占める。ただし VHPT は仮想アドレス空間上に置かれるので、この全領域に物理メモリを貼り付ける必要はない。
  ロード・ストア命令による仮想メモリアクセスが TLB ミスを起こした場合に MMU はまず VHPT を検索に行くが、該当する VHPT ページが TLB 上になければ VHPT 情報を読めない。そこで CPU は VHPT ミスフォルトを発生させ、ソフトウェアハンドラによって VHPT ページを TLB に挿入させる。つまり広大な VHPT 領域のうち実際にアクセスがあった箇所だけが、使用される。
その他にキー保護と呼ばれる機構がある。
- S/370 の Key-controlled protection に似ていて、TLB のエントリ毎に 24 ビットの保護キーを埋め込むことができる。 (別に存在する)特権保護によるアクセス制御は低い特権レベルモードでは高い特権レベルのページにアクセスできないが、高い特権レベルモードでは低い特権レベルのページには無制限にアクセスできてしまうという上下方向の制御だが、キー保護ではロールベースのアクセス制御など横方向の制御が可能になる。
- TLB の保護キーはメモリアクセスの度に IA-64 プロセッサの pk レジスタ群と比較され、pk レジスタ群内に一致したものがあれば VA-PA 変換が行われる。一致したものがなければ Key Miss フォルト割り込みが発生する(pk レジスタが何個あるかは実装依存だが、仕様により最低 16 個は存在する)。
- また pk レジスタのタグ設定を行うことで保護キー毎にメモリ属性よりも厳しい条件を課すことができる(保護キーを複数プロセス間で共有し、プロセスAは読み書き自由だが、プロセスBは読むことしかできないという条件をつけるなど)。
リージョニングによる仮想アドレスの増加分は、OS によってプロセス識別子として使われることが多い。
デフォルトの IA-64/Linux は VHPT をショート形式で運用し、保護キーを使用しない。
IA-64/Windows は VHPT をロング形式で運用し、保護キーも使用している。

コメントを書き込む