Document

仮想機械
温故知新
前田俊行
東京大学米澤研究室
目次
• 論文
“Architecture of Virtual Machines”
の紹介
• 論文
“Formal requirements for
Virtualizable Third Generation Architectures”
の紹介
• IBM VM/370 の紹介(中間報告)
今回扱う “VM”
• ハードウェアインターフェイスを
仮想化するタイプの VM
– 特に、現実のハードウェアと仮想ハードウェアの
アーキテクチャが同一である VM
Architecture of Virtual Machines
Robert P. Goldberg
In Proceedings of the workshop on virtual computer systems
74-112 (1973)
この論文の要点
• VM システムのアーキテクチャモデルを提案
– 2つのマッピング
• φ-マップと f -マップ
• 新しい VM システムの実装方法を提案
– Hardware Virtualizer
• VM を効率良く実装可能
– 再帰的 VM も効率良く実現できる
φ-マップ
• OSインターフェイスから
ハードウェアインターフェイスへのマップ
–例
• 仮想メモリ → 物理メモリ
• スレッド → 物理CPU
• ファイル → 物理ディスク
φ-マップ
ユーザプログラム
OS
ハードウェア
f -マップ
• ハードウェアインターフェイスから
ハードウェアインターフェイスへのマップ
– 例:
• VMの物理メモリ → 物理メモリ
• VMの物理 CPU → 物理 CPU
• VMの物理ディスク → 物理ディスク
f -マップ
OS
VMM
ハードウェア
2つのマップによる
VM システムの表現
通常の VM システム
φ
ユーザプログラム
OS
f
VMM ハードウェア
2つのマップによる
VM システムの表現
再帰的 VM システム
φ
ユーザプログラム
OS
f
f
f
f
VMM VMM VMM VMM ハードウェア
形式的定義: プロセス名とリソース名
• プロセス名 p:
OSインターフェイスを抽象化したもの
– (例) 仮想メモリのアドレス、仮想CPUのレジスタ、
ファイルシステムのファイル名とファイルポインタの組等
• リソース名 r:
ハードウェアインターフェイスを
抽象化したもの
– (例) 物理メモリのアドレス、物理CPUのレジスタ、
物理ディスクのアドレス等
形式的定義: φ-マップ
φは部分関数で
φ: P → R
ここで P はプロセス名 p の集合
P = { p0, p1, …, pj }
また R はリソース名 r の集合
R = { r0, r1, …, rn }
形式的定義: f -マップ
f は部分関数で
f: R1 → R2
ここで R1、R2 は
それぞれリソース名 r の集合
φと f による VM システムの表現
• 通常の VM システム
f φ: P → R2
f とφの合成
• 再帰的 VM システム
f4 f3 f2 f1 φ: P → R5
φと f による VM システムの表現
φ
ユーザプログラム
p1
rv1
p2
rv2
p3
rv3
OS
f
rr1
rr2
VMM ハードウェア
(例)
φ= { p1 → rv2,
p3 → rv3 } のとき、ユーザプログラムが
p1 にアクセスすると、
f = { rv1 → rr2,
OS と VMM により、
rv2 → rr1 }
φ(f(p1)) = rr1 へのアクセスに
変換される
未定義のプロセス名、リソース名の扱い
• あるφ-マップ、f-マップで未定義の
プロセス名やリソース名が利用されたら、
そのφ-マップ、f-マップを実装するOS、VMM に
適当な処理をさせなければならない
未定義のプロセス名、リソース名の扱い
φ
ユーザプログラム
p1
rv1
p2
rv2
p3
rv3
OS
f
rr1
rr2
VMM ハードウェア
(例)
φ= { p1 → rv2,
p3 → rv3 } のとき、ユーザプログラムが
p2 にアクセスしたら、
f = { rv1 → rr2,
例外を発生させ
rv2 → rr1 }
OS に処理させなければならない
未定義のプロセス名、リソース名の扱い
φ
ユーザプログラム
p1
rv1
p2
rv2
p3
rv3
OS
f
rr1
rr2
VMM ハードウェア
(例)
φ= { p1 → rv2,
p3 → rv3 } のとき、ユーザプログラムが
p3 にアクセスしたら、
f = { rv1 → rr2,
例外を発生させ
rv2 → rr1 }
VMM に処理させなければならない
モデルから見た VM システム実装
CP-67
φ の実装
f の実装
ハードウェアソフトウェア
φや f の合成再帰的 VM
ソフトウェア
不可能
VMware
ハードウェアソフトウェア
ソフトウェア
不可能
Bochs
ソフトウェア
ソフトウェア
可能
ソフトウェア
モデルから見た VM システム実装
CP-67
φ の実装
f の実装
ハードウェアソフトウェア
φや f の合成再帰的 VM
ソフトウェア
不可能
VMware
ハードウェアソフトウェア
ソフトウェア
不可能
Bochs
ソフトウェア
ソフトウェア
注
φと f の合成が
ソフトウェア
可能
ソフトウェアで行われていても
その合成結果 (φ’= f φ) は
ハードウェアで実装できる
モデルから見た VM システム実装
φ の実装
f の実装
φや f の合成再帰的 VM
Hardware ハードウェアハードウェアハードウェア可能
Virtualizer
CP-67
ハードウェアソフトウェア
ソフトウェア
不可能
VMware
ハードウェアソフトウェア
ソフトウェア
不可能
Bochs
ソフトウェア
ソフトウェア
可能
ソフトウェア
Hardware Virtualizer
• φ-マップや f -マップの合成を
ハードウェアでサポートするという
VM システムアーキテクチャ
– 実際に実装されたかは不明
– 特許は取られている
» 米国特許4253145 (出願1978年: もう期限切れ?)
Hardware Virtualizer の
構成要素
• VMID レジスタ
– 現在どの VM を実行中かを表す
• マップ合成機構
– Φや f を合成するハードウェア機構
• 例外振分け機構
– 例外や割込を正しい OS、VMM に届けるための
ハードウェア機構
Formal Requirements
for Virtualizable
Third Generation Architecture
Gerald J. Popek
Robert P. Goldberg
In Communications of the ACM 17(7): 412-421 (1974)
この論文の要点
• VM を実現するために
第三世代アーキテクチャが
満たすべき十分条件を
形式的に示した
– 条件: sensitive 命令 ⊆ privileged 命令
• 第三世代アーキテクチャ
– ここでは特権レベル機構や仮想メモリ機構のある
アーキテクチャのことをいう
形式的定義
マシン状態: S
S = ( E, M, P, R )
E : メモリ
M: 実行モード
P : プログラムカウンタ
R : セグメントレジスタ
形式的定義
メモリ: E
E = サイズ q の配列
形式的定義
実行モード: M
M = s または u
s : supervisor モード
u : user モード
形式的定義
プログラムカウンタ: P
P = メモリアドレス
(配列 E のインデックス)
形式的定義
セグメントレジスタ: R
R = (Base, Size)
Base: セグメントのベースアドレス
Size : セグメントのサイズ
マシン状態の例
S = ( [ 4, 5, 1, halt ],
s, 2, (1, 3) )
マシンが上のような状態 S にあるとき、
そのマシンは supervisor モードで実行中で、
かつ、halt 命令を実行しようとしている
pc = 2 だが、R = (1, 3) なので、
実行される命令は E(2+1) = E(3) = halt である
形式的定義
命令: i
i は関数で
i:C→C
C : S の有限集合
形式的定義:
Trap
• 命令 i は次の条件を満たすとき
“Trap する”という
i (E1, M1, P1, R1) = (E2, M2, P2, R2)
ただし
E2[k] = E1[k], for 0 < k < q
E2[0] = ( M1, P1, R1)
( M2, P2, R2) = E1[1]
つまり、命令実行前の (M, P, R) が E[0] にセーブされ、
命令実行後の (M, P, R) が E[1] からロードされるようなとき
形式的定義:
Memory Trap
• Trap する命令 i は次の条件を満たすとき
“Memory Trap する”という
S = ( E, M, P, (Base, Size) ) において
命令 i のアクセスするアドレス a が
Size < a
(セグメントサイズオーバー)
または
q < Base + a (メモリサイズオーバー)
を満たす
形式的定義
Privileged
• 命令 i は以下の条件を満たすとき
Privileged であるという
任意の
S1= (E, s, P, R)
S2= (E, u, P, R)
ただし、i(S1)もi(S2)も Memory Trap しない
において
i(S1) は Trap しない
i(S2) は Trap する
つまり、user モードで実行すると Trap する命令
形式的定義
Control Sensitive
• 命令 i は以下の条件を満たすとき
Control Sensitive であるという
S1= (E1, M1, P1, R1)
i(S1)= S2= (E2, M2, P2, R2)
ある
において
ただし、i(S1)は Memory Trap しない
M1≠M2 and/or R1≠R2
つまり、命令実行後に、例外が生じることなく
メモリマッピングが変わったり実行モードが変わったりすること
Control Sensitive な命令の例
• 仮に IA-32 で例えるならば
– int 命令 (ソフトウェア割込命令)
• 実行後に実行モード (= M) が変わる場合がある
– mov 命令 (メモリ操作命令)
• ページテーブル、GDT、LDT等へのメモリ操作は
R を変更することと対応する
– など
注: ここでの抽象化モデルと IA-32 は必ずしも一致しないので
ここで挙げた例は、定義に厳密に基づいたものではない
形式的定義
Behavior Sensitive
• 命令 i は以下の条件を満たすとき
Behavior Sensitive であるという
ある
S1= (E1, M1, P, R)
S2= (E2, M2, P, R+x)
R = (b, s) のとき
R+x = (b + x, s)
ただし、i(S1)も i(S2)も Memory Trap せず
i(S1) = (E’1, M1, P1, R)
E1| (b,s) = E2| (b,s) +x
i(S2) = (E’2, M2, P2, R+x)
⇔
0≦ k < s なる k で
E1|R = E2|R+x
において
E1[b+k] = E2[b+x+k]
E’1|R≠E’2|R+x and/or P1≠P2
つまり、命令実行の結果が、例外を生じることなく
メモリマッピングや実行モードによって異なること
Behavior Sensitive な命令の例
• 仮に IA-32 で例えるならば
– sgdt 命令 (GDTレジスタ読出命令)
• GDT レジスタ (= R に対応) の値によって結果が異なる
– push 命令 (メモリ操作命令)
• push CS の実行結果が実行モード (= M) によって異なる
– など
注: ここでの抽象化モデルと IA-32 は必ずしも一致しないので
ここで挙げた例は、定義に厳密に基づいたものではない
形式的定義
Sensitive
• 命令 i は Control Sensitive または
Beharior Sensitive であるとき
Sensitive であるという
定理 1
• あるアーキテクチャが
以下の条件を満たすとき
そのアーキテクチャは仮想化可能である
{ i | i は Sensitive }
⊆ { i | i は Privileged }
この条件を満たすアーキテクチャ上では、
ゲスト OS を user モードで実行すれば仮想化できる
定理 2
• あるアーキテクチャが
仮想化可能であるとき
そのアーキテクチャは
再帰的仮想化可能である
– 再帰的仮想化 = VM の上に VM を実現すること
定理1 と IA-32
• IA-32 には Sensitive であるが
Privileged でない命令が存在するので
IA-32 は条件を満たさない
• Sensitive であるが Privileged でない命令
– mov 命令、sgdt 命令、push 命令など
ハイブリッド仮想化
• Supervisor モードでは
命令をハードウェアで実行せずに
インタプリタで実行する仮想化の方式
– 純粋な仮想化よりも
アーキテクチャが満たすべき条件は緩い
形式的定義
User Sensitive
• 命令 i は以下の条件を満たすとき
User Sensitive であるという
S = (E, u, P, R)
において
i が Sensitive
つまり、user モードで実行されたとき
Sensitive となる命令
定理 3
• あるアーキテクチャが
以下の条件を満たすとき
そのアーキテクチャは
ハイブリッド仮想化可能である
{ i | i は User Sensitive }
⊆ { i | i は Privileged }
この条件を満たすアーキテクチャ上では、
ゲスト OS をインタプリタ実行すれば仮想化できる
定理3 と IA-32
• IA-32 には User Sensitive であるが
Privileged でない命令が存在するので
IA-32 は条件を満たさない
• User Sensitive であるが Privileged でない命令
– mov 命令、sgdt 命令など
VMware はどうしているか
• ハイブリッド仮想化
– ただし user モードで実行されるプログラムは
正しいハードウェアが見えない
• (例) sgdt 命令の結果は VM の GDT レジスタではなく
本物の GDT レジスタの値となる
– user モードプログラムが GDT を直接操作できるような OS が
あったら、その OS は正しく動作しないであろう
VMware はどうしているか
• ハイブリッド仮想化
– ページテーブルへのメモリ操作は、
IA-32 の仕様上 mov CR3 命令が実行されるまで
その操作が CPU に反映されないと見なせるので
問題はない
• Mov CR3 は Privileged 命令、
すなわちインタプリタ実行される
– そもそも user モードプログラムがページテーブルを
直接操作できるような OS でなければこの問題は存在しない
» なぜならページテーブルの操作 = Privileged 命令
と見なせるから
IBM VM/370
中間報告
IBM の汎用計算機の歴史
• System 360 (1964) Solid Logic による実装
• System 370 (1970) IC による実装
• System 390 (1990)
• いわゆる「メインフレーム」
• 基本的なアーキテクチャは
ほとんど変わっていない
– CISC、セグメント + ページング
IBM の VM の歴史
• CP-67 (1966)
• 仮想メモリ機構の欠けた VM を実現
• VM/370 (1972)
• 完全な VM を実現
– 再帰的 VM もサポートしているらしい
» VM/370 の新バージョンのデバッグは
VM/370 の古いバージョン上で行われたらしい
• z/VM 5.1 (2004)
VM/370 のアーキテクチャ
OS
VMM
CMS
DOS/360
OS/360
CP (= Control Program)
System/370
MVS
VM/370 の特徴
• 2つの仮想化モード
– V=R モード
• VM の物理アドレス = 本物の物理アドレス
として性能改善をはかるモード
• システムに1つだけ存在できる
– V=V モード
• VM の物理アドレスは本物の物理アドレスとは
関係なく、ページテーブルによって対応づけるモード
• いくつでも存在できる
– (これは S/390 上でのことだが、Linux を V=V モードで
約40000 も同時に実行した人もいるらしい)
続く…
• 現在までにまだ調べ終えていないこと
– VM/370 が本当に再帰的仮想化可能か?
– VM-Assist とは何か?
• System/370、VM/370 には
VM-Assist という VMM 実装を支援する
ハードウェア機構があるらしい
– など
終
予備スライド
Hardware Virtualizer による
再帰的 VM システムの例
0
VM1: 4, 8
4
VM1: 5, 3
VM2: 12, 5
物理メモリ空間
Hardware Virtualizer による
再帰的 VM システムの例
0
VM1: 4, 8
4
9
12
17
VM1: 5, 3
VM2: 12, 5
物理メモリ空間
これらが f を表す
ここでは簡単のため f は
セグメントマップ = (オフセット, サイズ)とする
Hardware Virtualizer による
再帰的 VM システムの例
VM1
0
VM1: 4, 8
4
VM2
9 VM1.1 12
17
VM1: 5, 3
VM2: 12, 5
物理メモリ空間
Hardware Virtualizer による
再帰的 VM システムの例
VM1
0
VM1: 4, 8
4
VM1: 5, 3
VM2
9 VM1.1 12
17
P1: 2, 1
VM2: 12, 5
物理メモリ空間
Hardware Virtualizer による
再帰的 VM システムの例
VM1
0
VM1: 4, 8
4
VM1: 5, 3
VM2
9 VM1.1 12
17
P1: 2, 1
VM2: 12, 5
物理メモリ空間
これがφを表す
ここでは簡単のためφも f 同様
セグメントマップ = (オフセット, サイズ)とする
Hardware Virtualizer による
再帰的 VM システムの例
VM1
0
VM1: 4, 8
4
VM1: 5, 3
VM2
9 VM1.1 12
17
P1: 2, 1
VM2: 12, 5
物理メモリ空間
プロセスP1
Hardware Virtualizer による
再帰的 VM システムの例
VM1
0
4
VM1: 4, 8
VM1: 5, 3
VM2
9 VM1.1 12
17
P1: 2, 1
VM2: 12, 5
物理メモリ空間
プロセスP1
今、プロセス P1 が VM1.1 上で
動作しているとする
このとき LMID レジスタは 1.1 という値をとっている
Hardware Virtualizer による
再帰的 VM システムの例
VM1
0
4
VM1: 4, 8
VM2
9 VM1.1 12
VM1: 5, 3
17
P1: 2, 1
VM2: 12, 5
もしこのプロセス P1 が
アドレス 0 にアクセスすると…
(例: load 0)
物理メモリ空間
プロセスP1
Hardware Virtualizer による
再帰的 VM システムの例
VM1
0
4
VM1: 4, 8
VM1: 5, 3
VM2
9 VM1.1 12
17
P1: 2, 1
VM2: 12, 5
まずマップ合成機構は
φを見に行く
φ(0) = 2
物理メモリ空間
プロセスP1
Hardware Virtualizer による
再帰的 VM システムの例
VM1
0
4
VM1: 4, 8
VM1: 5, 3
VM2
9 VM1.1 12
17
P1: 2, 1
VM2: 12, 5
物理メモリ空間
プロセスP1
次にマップ合成機構は
VMID = 1.1 なので VM1 の f の VM1 を見に行く
f1(2) = 7
そして仮の VMID を 1 とする
Hardware Virtualizer による
再帰的 VM システムの例
VM1
0
4
VM1: 4, 8
VM1: 5, 3
VM2
9 VM1.1 12
17
P1: 2, 1
VM2: 12, 5
物理メモリ空間
プロセスP1
最後にマップ合成機構は
仮のVMID = 1 なのでオリジナルの f のVM1を見に行く
f (7) = 11
Hardware Virtualizer による
再帰的 VM システムの例
VM1
0
4
VM1: 4, 8
VM2
9 VM1.1 12
VM1: 5, 3
17
P1: 2, 1
VM2: 12, 5
もしこのプロセス P1 が
アドレス 3 にアクセスすると…
(例: load 3)
物理メモリ空間
プロセスP1
Hardware Virtualizer による
再帰的 VM システムの例
VM1
0
4
VM1: 4, 8
VM1: 5, 3
VM2
9 VM1.1 12
17
P1: 2, 1
VM2: 12, 5
物理メモリ空間
プロセスP1
まずマップ合成機構は
φを見に行くが、
φ(3) = 未定義 (セグメントサイズを超えている)
よって VM1.1 で実行中の OS にセグメント例外を投げる
Hardware Virtualizer による
再帰的 VM システムの例
VM1
0
4
VM1: 4, 8
VM1: 5, 3
VM2
9 VM1.1 12
17
P1: 2, 5
VM2: 12, 5
物理メモリ空間
プロセスP1
もしφのセグメントサイズが
VM1.1 のサイズをこのように超えているとき
プロセス P1 がアドレス 3にアクセスすると…
Hardware Virtualizer による
再帰的 VM システムの例
VM1
0
4
VM1: 4, 8
VM1: 5, 3
VM2
9 VM1.1 12
17
P1: 2, 5
VM2: 12, 5
まずマップ合成機構は
φを見に行く
φ(3) = 5
物理メモリ空間
プロセスP1
Hardware Virtualizer による
再帰的 VM システムの例
VM1
0
4
VM1: 4, 8
VM1: 5, 3
VM2
9 VM1.1 12
17
P1: 2, 5
VM2: 12, 5
物理メモリ空間
プロセスP1
次にマップ合成機構は
VMID = 1.1 なので VM1 の f の VM1 を見に行くが
f1(5) = 未定義 (セグメントサイズを超えている)
よって VM1 にセグメント例外を投げる

Download Report