仮想メモリ方式の分類

作成日:2006.03.30
修正日:2016.10.17

更新記録
(2006.03.30) 2006/3/102006/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. はじめに

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

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

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

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

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

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

アドレス変換

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

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 ビット幅のメモリまでアクセス可能になっていた。

8086 のセグメンテーション

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 バイト) を入れ替える形で実アドレス空間と物理アドレス空間を対応関係を変えることができる。

S/370 の prefixing

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 の場合は、
  1. この仮想ページがマップされていない。
  2. この仮想ページの内容がディスクに書き出されている(ページ・アウトされた)。
の二つの意味をもたせる場合が多い。 無視された残りのビットフィールドを使って、スワップディスクのどの位置に書き出されたかを記録したりする。
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 とは少し離れるが、メモリキャッシュもアドレスを記録している。 このキャッシュ内のアドレスが仮想アドレスで記録されるか、実アドレスで記録されるかはプロセッサによって異なる。

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

現在のプロセッサは、高速なアクセスが必要な 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  
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 (ローカル)
仕様上はページサイズを 212~228 バイトに変更できるが、本当にとれるページサイズは 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  
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 は仮想メモリ機構を備えた最初の商業コンピュータシステムである。

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

x86-64、AMD64、Intel64、IA32m、EM64T

PowerPC 32 ビット

PowerPC 64 ビット

SPARC 32 ビット (SPARC V8)

SPARC 64 ビット (SPARC V9)

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

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

MIPS 32 ビット

MIPS 64 ビット

Alpha

IA-64、IPF

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

コメント

コメントを書き込む

TOP    掲示板    戻る
Written by NAKAMURA Minoru, Email: nminoru atmark nminoru dot jp, Twitter:@nminoru_jp