単一システムイメージを 提供するための仮想マシンモニタ 金田憲二 大山恵弘　米澤明憲　 （東京大学）

コモディティクラスタの普及 かつてないほど一般に浸透 個人・ワークグループ用として　　　　　　　　　　　　　　　　　　　　　　4~32ノード程度のクラスタを所有するのが、　普通になっている

クラスタの利用における問題点 利便性が低い 例）複数のマシンに分散したCPUやディスクを大域的に管理する機構の欠如 一般のクラスタ利用者には、致命的な問題

小・中規模クラスタを簡便に利用できるようにする 本研究の目標 クラスタ上に単一システムイメージを構築 大域プロセス空間 大域ファイルシステム … 計算機科学を専門としない一般の人でも、 小・中規模クラスタを簡便に利用できるようにする

本研究のアプローチ 仮想マシンモニタを利用する 実機と同等の処理が可能な仮想マシンを構築するミドルウェアシステム 例）VMware Workstation

我々が提案する仮想マシンモニタ ネットワークで結合された複数のマシン上に SMPマシンを仮想的に構築する Nプロセッサからなる仮想SMPマシン 仮想化 N台のシングルプロセッサマシン

仮想マシンの動作デモ … 8台の物理マシン上に8-wayのSMPマシンを仮想的に構築する ゲストOS上で立ち上げたプロセスが、 それぞれ異なる物理マシン上で並列に実行される プロセス プロセッサ メモリ … それでは、このシステムが具体的にどう動作するかについて、デモを通して説明します。 このデモでは、8台の物理マシン上に8-wayの仮想SMPマシンを構築します。 そして、この仮想マシン上で走るゲストOS上で複数プロセスを立ち上げます。 すると、生成されたプロセスが、それぞれ別の物理マシン上で並列に実行されるようになります。 仮想マシン プロセッサ プロセッサ プロセッサ 物理マシン群 … メモリ メモリ メモリ

仮想SMPマシン上で動いているLinuxの端末 それぞれの実マシンのCPU負荷 仮想マシンの動作デモ 仮想SMPマシン上で動いているLinuxの端末 では、実際に簡単なデモムービーをお見せします。 このウィンドウが、仮想マシン上で走るLinuxの端末です。 この左上のグラフが、各マシンのCPU負荷を表しています。棒が高くなるほど負荷が高いことを意味しています。 そして、このLinux上でいくつかプロセスをforkします。するとforkされたプロセスがLinuxのプロセススケジューラによって、各仮想プロセッサに割り当てられて、最終的にはその仮想プロセッサをエミュレーションするマシン上で実行されます。 この場合、立ち上げた8つプロセスが、それぞれ別のマシンで計算されるため、左上の棒グラフからも分かるように、各マシンの負荷が高くなります。 そして、もちろん、普通のLinuxのようにシグナルを送るなどのプロセス制御も簡便に行えますし、 何かスクリプトを記述してワークフローのようなものを実行するといったことも可能になっています。

我々のアプローチの利点 (その1) 既存の並列プログラムを（ほとんどの場合）無変更のまま、実行可能 科学技術計算からWebサーバまで 多少の改変でLinuxカーネルも プロセス管理機構やファイルシステムを 分散環境上で利用可能 このシステムの利点ですが、まず、既存の共有メモリを仮定して書かれた並列アプリケーションが（ほとんど）無変更で動作することが挙げられます。例えば、SMP用Linuxカーネルなども仮想マシン上で動作させることができます。 また、仮想マシンですので、サンドボックスとして利用可能であったり、各ユーザが自由に環境をカスタマイズ可能であったりいった利点も持ちます。

我々のアプローチの利点 (その2) 仮想マシンを様々な目的に応用可能 サンドボックスとしての利用 仮想マシンの実行状態の保存・復元 …

残りの発表の流れ 我々の仮想マシンモニタの概要 ハードウェアの仮想化 共有メモリの一貫性制御の仮想化 予備実験 関連研究 まとめと今後の課題

提供される仮想マシンの特徴 仮想資源と実資源の対応付け 我々の仮想マシンモニタの概要 提供される仮想マシンの特徴 仮想資源と実資源の対応付け 　それでは、システムの設計について説明します。

仮想マシンの特徴 (その1) ISAレベルの仮想化 ※VMWare，Xenなどと同様 ユーザアプリ ゲストOS ISA 仮想マシン システムコール ゲストOS 仮想マシン上では、提供されるISAを満たすOSを走らせることができる ISA 仮想マシン 仮想マシンモニタ

仮想マシンの特徴 (その2) 仮想マシンのISA ≒ 実マシンのISA ゲストOS 仮想マシンのISA 仮想マシン 仮想マシンモニタ ユーザアプリ ホストOS 仮想マシン ゲストOS 仮想マシンモニタ 仮想マシンのISA 実マシンのISA

仮想マシンの特徴 (その2) 既存のOSを仮想マシン上で走らせるためには カーネルに修正を加える必要がある ただし、ほとんどの修正は自動化できる 手動で加える変更も、ほぼ自明のもの 例）カーネル空間のベースアドレスの変更 ※LilyVM [H. Eiraku et al. BSDCon’03]と同様の設計

仮想マシンの特徴 (その3) 仮想マシン・実マシン共にLinux/IA-32を対象 一般に広く普及しているので 既存研究の資産が利用しやすいので

仮想資源と実資源の対応例 プロセッサ プロセッサ 仮想SMP メモリ プロセッサ プロセッサ ディスク ディスク メモリ メモリ 実マシン

仮想資源と実資源の対応例 プロセッサ プロセッサ 仮想SMP メモリ プロセッサ プロセッサ ディスク ディスク メモリ メモリ 実マシン 　まず、プロセッサの対応付けについて説明します。 　個々のモニタプロセスが、SMPのそれぞれのプロセッサをエミュレーションします。つまりは、モニタプロセスの走っている実マシンのプロセッサと仮想マシンのプロセッサが1対1対応します。このスライドの場合ですと、モニタプロセスが2つなので、2-wayのSMPが構築されることになります。 プロセッサ プロセッサ ディスク ディスク メモリ メモリ 実マシン 実マシン

仮想資源と実資源の対応例 プロセッサ プロセッサ 仮想SMP メモリ プロセッサ プロセッサ ディスク ディスク メモリ メモリ 実マシン 　次に、メモリについて説明します。普通のVMWareなどの仮想マシンと同様に、仮想マシンは、実機のメモリの一部を自分のメモリとして使用します。複数の実機からそれぞれ等量のメモリを確保し、その確保したメモリ量と同じだけの共有メモリを、仮想マシンは持ちます。 プロセッサ プロセッサ ディスク ディスク メモリ メモリ 実マシン 実マシン

仮想資源と実資源の対応例 プロセッサ プロセッサ 仮想SMP メモリ モニタプロセス モニタプロセス プロセッサ プロセッサ ディスク 最後にディスクやネットワークデバイスなどのI/Oデバイスですが、仮想マシンは、実マシンの持つデバイスの一部を利用します。例えば、ハードディスクの場合ですと、仮想マシンは、ある実マシンのもつハードディスクの一部を自分のものとして使用します。 プロセッサ プロセッサ ディスク ディスク メモリ メモリ 実マシン 実マシン

ハードウェアの仮想化 　以上がシステムの設計についての説明です。このシステムをどう実装するかについて、これから説明します。

ハードウェアの仮想化 以下の資源をユーザレベルで仮想化 プロセッサ 共有メモリ I/Oデバイス 特権命令、割り込み、… ページング、一貫性制御、… I/Oデバイス ハードディスク、APIC、タイマー、…

ハードウェアの仮想化 以下の資源をユーザレベルで仮想化 プロセッサ 共有メモリ I/Oデバイス 特権命令、割り込み、… ページング、一貫性制御、… I/Oデバイス ハードディスク、APIC、タイマー、… LiLyVMとほぼ同様 LiLyVMとほぼ同様

ハードウェアの仮想化 以下の資源をユーザレベルで仮想化 プロセッサ 共有メモリ I/Oデバイス 特権命令、割り込み、… ページング、一貫性制御、… I/Oデバイス ハードディスク、APIC、タイマー、… LiLyVMとほぼ同様 LiLyVMとほぼ同様 我々独自の点

VMプロセスの実行を監視し、必要に応じて仮想化処理を エミュレーションする 基本的な実装方針 一つの仮想プロセッサごとに，　　　　　　　　　　　　　　　　　　以下の2つのユーザプロセスを用意 ゲストOSをnativeに実行する VMプロセス VMプロセスの実行を監視し、必要に応じて仮想化処理を エミュレーションする モニタプロセス

システムの基本動作サイクル VMプロセス モニタプロセス ゲストOSをnative実行 実行を捕捉 実行を再開 　モニタプロセスが、どうやって仮想マシンを構築するかについて、つまりは、仮想マシンがどうやってゲストOSを走らせ、ゲストOSから実機ではなく仮想マシンの状態が見えるようにするのかについて説明します。 　我々のシステムは、基本的には、LilyVM [H. Eiraku et al. ’03]と同様の動作をします。 　我々のシステムにおいては、まず、モニタプロセスが、 VMプロセスと呼ばれるプロセスを生成します。このVMプロセスが、ゲストOSを実機上でNativeに実行します。 　モニタプロセスは、このVMプロセスの実行をptraceシステムコールで監視し、VMプロセスが、特殊なハードウェアへのアクセスなど、何か仮想化を必要な命令を実行しようとする時に、それを捕捉し、VMプロセスの代わりにエミュレーション実行します。そしてエミュレーション終了後、VMプロセスの実行を再開させます。これによって、ゲストOSからは、実機ではなく仮想マシンの状態が見えるようになります。 　まとめると、ほとんどの命令はVMプロセスによって実機上でダイレクトに実行され、仮想化の必要な命令のみモニタプロセスによって、エミュレーション実行されます。 命令などの実行をエミュレーション

実マシンのメモリ上のどこかに 仮想マシンのGDTRの値を格納 システムの動作例 … lgdtl 0xa01002c2 特権命令の実行（GDTRへの 書き込み） シグナル発生 VMプロセス シグナルを捕捉 VMプロセスの実行を再開 モニタプロセス 実マシンのメモリ上のどこかに 仮想マシンのGDTRの値を格納

IA-32のメモリモデルの概要 Simpleな一貫性制御アルゴリズム アルゴリズムの改良にむけて 共有メモリの一貫性制御の仮想化 IA-32のメモリモデルの概要 Simpleな一貫性制御アルゴリズム アルゴリズムの改良にむけて 　それでは、システムの設計について説明します。

共有メモリの一貫性制御の仮想化 ある仮想プロセッサが行った書き込みを、 他の仮想プロセッサに反映させる必要がある IA-32メモリモデルを満たすように

IA-32のメモリモデルの概要 以下の制約を満たす 同期命令を提供する Processor consistency Write atomicity 同期命令を提供する 一時的にメモリ一貫性を強めることが可能 　IA-32のメモリモデルですが、基本的には、Processor consistencyと呼ばれる制約と、Write atomicityと呼ばれる制約の二つを満たすように書き込みを反映させます。 　そして、この二つの制約に加えて、一時的にメモリ一貫性を強める役割を果たす、同期命令というものを提供しています。

Processor Consistency (1/2) あるプロセッサが行った書き込みは， 同一プロセッサには，すぐに反映される 異なるプロセッサには，遅れて反映されうる PU1 PU2 write X to p 書き込み反映 read from p 　それではまず、Processor consistencyという制約が、何を保障するのかについて説明します。 　メモリモデルがProcessor consistencyを満たすという時は、あるプロセッサが行った書き込みは，同一プロセッサに対しては，すぐに反映されることが保障されています。自分と異なるプロセッサに対しては，すぐに反映されるとは保障されておらず、遅れて反映されることがあります。 　例えば、このスライドにあるように二つのプロセッサPU1とPU2があるとします。矢印の方向に沿って時間が経過しているとします。このとき、PU1がアドレスpに対してXという値を書き込んだとします。この書き込み結果は、自プロセッサに対しては、すぐに反映されます。例えば、書き込み後にPU1が同じアドレスpから読み込みを行うと、さきほど書き込んだ値Xが得られることが保障されています。 　それに対して、PU1の書き込みは、リモートプロセッサであるPU2には、書き込み直後に反映されるとは限らず、遅れて反映される場合があります。この場合、PU2は、PU1のアドレスpへの書き込み後に読み込みを行ったとしても、値がXにならず、しばらくたって、書き込み結果が反映された後で、読み込んだ値がXになります。 = ? read from p = X read from p = X

Processor Consistency (2/2) あるプロセッサが行った書き込みは， 同じ順序でリモートプロセッサに反映される PU1 PU2 PU3 write X to p write Y to q write Z to r 　Processor consistencyは、他にも、「あるプロセッサが行った書き込みが、同じ順序でリモートプロセッサに反映される」ということを保障します。 　例えば、PU1が値Xをアドレスpに書き込み、その後、値Yをアドレスqに書き込み、その後、値Zをアドレスrに書き込んだとします。この場合、リモートプロセッサPU2とPU3に対して、それぞれ同じ順番で書き込みが反映されることが保障されます。

（アドレスpに対する）読み書きは，この間に 発生しない Write Atomicity 書き込みはリモートプロセッサにatomicに　　　　　　　　反映される PU1 PU2 PU3 write X to p （アドレスpに対する）読み書きは，この間に　　　　　　　　　　発生しない 　次に、Write Atomicityが何を保障するかについて説明します。 　Write atomicityは、「書き込みがリモートプロセッサにatomicに反映される」ことを保障します。つまり、書き込みがリモートプロセッサに反映されるときは，全てのプロセッサに対して同時に反映され、一つのプロセッサに反映され、他のプロセッサにまだ反映されていない間に、書き込みが発生したのと同じアドレスに対する読み書きは起こらないことを保障します。 　例えば、PU1がアドレスpに対して書き込みを行ったとします。それがリモートプロセッサPU2に反映されるのと、PU3に反映されるのとの間に、アドレスpに対する読み書きが発生しないことが保障されています。

同期命令 一時的にメモリ一貫性を強める 例） mfence命令 PU1 PU2 PU3 write X to p write Y to q 書き込みがリモートプロセッサに反映されたことを保障 PU1 PU2 PU3 write X to p 　以上の制約に加えて、IA-32は、同期命令と呼ばれる一時的にメモリ一貫性を強める命令を提供しています。 　例えば、同期命令の一つであるmfence命令は、その命令が実行された時には、それ以前に行われた書き込みがリモートプロセッサに反映されていることを保障します。このスライドの場合ですと、PU1がmfenceを実行した時点で、それ以前に実行した二つの書き込みは、リモートプロセッサPU2とPU3に反映されていることが保障されます。 write Y to q mfence

Simpleな一貫性制御アルゴリズム 特にIA-32のメモリモデルに特化しない ページ単位での、メモリの共有・非共有の管理 Write invalidateプロトコル single writer, multiple readers 同一ページへ読み込みは、 複数のプロセッサが同時に行える 同一ページへの書き込みは、 1つのプロセッサしか同時に行えない

各ページに割り当てられる状態 RW：読み書き共に可能 RD：読み込みのみ可能 INV:読み書き共に不可能

各ページに割り当てられる状態 RW：読み書き共に可能 RD：読み込みのみ可能 INV:読み書き共に不可能 ページ0 ページ1 ページ2 … 一つのプロセッサでページの状態がRWであれば、他のプロセッサのそのページの状態はINVでなければいけない 状態がRWであるプロセッサが、ページの最新の内容を持つ 複数のプロセッサで同一ページの状態がRDであることは可能 ページの複製を持つ … プロセッサ0のメモリ RW RD INV … プロセッサ1のメモリ INV RD RW … プロセッサ2のメモリ INV INV INV

ページの状態がRWである プロセッサは同時に一つ 各ページに割り当てられる状態 RW：読み書き共に可能 RD：読み込みのみ可能 INV:読み書き共に不可能 ページの状態がRWである プロセッサは同時に一つ 他のプロセッサの ページの状態はINV ページ0 ページ1 ページ2 状態がRWであるプロセッサが、ページの最新の内容を持つ 複数のプロセッサで同一ページの状態がRDであることは可能 ページの複製を持つ … プロセッサ0のメモリ RW RD INV … プロセッサ1のメモリ INV RD RW … プロセッサ2のメモリ INV INV INV

ページの状態がRDであるプロセッサは 複数存在する場合がある 各ページに割り当てられる状態 RW：読み書き共に可能 RD：読み込みのみ可能 INV:読み書き共に不可能 ページの状態がRDであるプロセッサは 複数存在する場合がある ページ0 ページ1 ページ2 状態がRWであるプロセッサが、ページの最新の内容を持つ ページの複製を持つ … プロセッサ0のメモリ RW RD INV … プロセッサ1のメモリ INV RD RW … プロセッサ2のメモリ INV INV INV

ページの状態の更新 以下のアクセスが発生した際に、 ページの状態が更新される 状態がINVであるページへの読み書き 状態がRDであるページへの書き込み INVであるページへの読み込み、 最新のページの内容を取得 自分のページの状態をRDに変更する

仮想プロセッサ0がページ2に 読み込みを行った場合 (ii) プロセッサ0のページ2を読み込みのみ可能にする ページ0 ページ1 ページ2 … プロセッサ0のメモリ RW RD RD INV … プロセッサ1のメモリ INV RD RD RW … プロセッサ2のメモリ INV INV INV (i) プロセッサ0以外のページ2を書き込み禁止にする

仮想プロセッサ0がページ2に 書き込みを行った場合 (ii) プロセッサ0のページ2を読み込み書き可能にする ページ0 ページ1 ページ2 … プロセッサ0のメモリ RW RD RD RW … プロセッサ1のメモリ INV RD RD INV … プロセッサ2のメモリ INV INV INV (i) プロセッサ0以外のページ2を読み書き禁止にする

アルゴリズムの改良にむけて IA-32のメモリモデルを考慮した より効率的なアルゴリズムにしたい

アルゴリズムの最適化の例 Multiple writes 同一ページに対して複数の仮想プロセッサが同時に書き込み可能にする ただし、Processor Consistencyは満たしつつ

Multiple Writesの実現方法 (1/4) 直列化命令実行時に，ローカルの書き込みを他の全てのマシンに反映させる PU1 PU2 Write X to p Write Y to q ※自然と書き込み順序は保存される p, q, rへの書き込み結果を送信 Write Z to r 書き込み結果を反映 mfence

Multiple Writesの実現方法 (2/4) 全てのページを書き込み禁止にする PU1 PU2 Memory Memory Write X to p Write Y to q Write Z to r mfence このアルゴリズムは、具体的には、以下のように動作します。 まず、全てのページを書き込み禁止にし、仮想マシンの実行を開始します。 …

Multiple Writesの実現方法 (3/4) ページに対して書き込みがあると　 そのページのコピー(= twin)を作成する そのページへの書き込みを許可する PU1 PU2 Twins Memory Memory Write X to p Write Y to q Write Z to r mfence 実行中にページに対して書き込みがあると、発生したシグナルをトラップし、そのページのコピー(= twin)を作成します。そして、次に、そのページへの書き込みを許可し、実行を再開させます。書き込みが許可されたので、それ以降は、シグナルを発生することなく書き込みは行われます。 p X q Y r Z

Multiple Writesの実現方法 (4/4) 　mfence命令を実行する時に， twinと現在のメモリを比較してdiffを作成する diffをリモートマシンに送信する PU1 PU2 Twins Memory Memory Write X to p Write Y to q Write Z to r mfence mfence命令を実行する時に，twinと現在のメモリを比較し、mfence実行前にどのようにメモリが更新されたかの差分をとります。それを他のマシンに送信します。その差分を受け取ったマシンは、それを元に自分のメモリの状態を更新します。 diffを送信後は、また全ページを書き込み禁止にし、同様のステップを繰り返します。 p X Y Z q r

予備実験

予備実験 システムの基本性能の評価 実験内容 実験環境 仮想マシン上で、互いに独立なタスクを並列実行 　実験内容 仮想マシン上で、互いに独立なタスクを並列実行 フィボナッチ x 8プロセス 　実験環境 CPU: Intel Xeon 2.4 GHz メモリ: 2GB ネットワーク: 1000Base ゲスト・ホストOS: Linux 2.4 このシステムの基礎性能の評価として、仮想マシン上で、互いに独立なタスクを並列実行し、その実行時間を測定しました。 具体的には、このスライドにあるような環境でfib(44) を実行するプロセスを8個立ち上げ、並列に走らせました。

並列フィボナッチの性質 主に、以下の処理で仮想化が必要となる forkなどのシステムコールの発行 ライブラリの読み込みなどによる ハードディスクへのアクセス 共有メモリの一貫性制御 例）プロセススケジューリングを行う際に、 異なるプロセッサが同一ページにアクセスする

並列フィボナッチの速度向上 タスクの粒度が粗ければ、台数効果が出た fib(46)の時、8プロセッサで約6.6倍の速度向上

fib(44)の実行時間の内訳 プロセッサ数が増加するにつれて、 共有メモリの仮想化のオーバヘッドが増大 プロセッサ数 全実行時間 Native Shmem Misc Idle 1 180.0 177.8 0.0 2.2 2 90.3 87.9 1.0 1.1 0.3 4 52.4 43.7 3.0 0.4 5.3 8 27.9 22.1 3.7 0.1 2.0 （単位：秒）

Page fetchにかかる時間の分布 大半のfetch処理は、数ミリ秒以内に完了 一部のfetch処理だけ、数十ミリ秒必要

Fetchされた仮想アドレスの分布 カーネル空間 ユーザ空間

実験の考察 False sharingによるオーバヘッドが大きい 改善案はいくつか考えられる 当然といえば当然 一貫性制御アルゴリズムの改良 Multiple writesの実現 ゲストOSの改変 ゲストOSをLinux2.6にするだけでも、 性能が改善するかも

関連研究

仮想マシンモニタ (1/2) vNUMA [M. Chapman USENIX’05] 複数のItaniumマシン上にccNUMAを仮想的に構築 ただし、メモリ一貫性制御がsequential consistency 　関連研究ですが、我々と同じように、分散環境上にマルチプロセッサマシンを仮想的に構築する仮想マシンモニタについての研究が存在します。　 一つはvNUMAというもので、これは、複数のItanumのマシン上に、仮想的にccNUMAを構築するシステムです。ただし、メモリ一貫性制御がsequential consistencyであり、我々のシステムと比べて非効率なものとなっています。 また、Virtual Ironというものも、ほぼ同様のシステムですが、詳細が未公開のため、我々のシステムとの比較はまだ出来ていません。

仮想マシンモニタ (2/2) VMWare ESX Server [1]、Disco [2] 仮想的にSMPマシンを構築 [1] C. Waldspurger et al. OSDI’02 [2] E. Bugnion et al. SOSP’97

クラスタミドルウェア (1/2) Score [3]、Condor [4] クラスタへの並列ジョブ投入などが可能になる ただし、それぞれのシステム特有の操作に、 利用者は習熟する必要がある [3] http:// www.pccluster.org [4] http://www.cs.wisc.edu/condor

クラスタミドルウェア (2/2) MOSIX [5]、Kerighed [6] Linuxカーネルを改変した分散OS ただし、カーネル改変に多大な手間を必要とする [5] A. Barak et al. FGCS’98 [6] C. Morin et al. Euro-Par’03

ソフトウェアDSM Shasta [7]、cJVM [8] 共有メモリを仮定して書かれた並列アプリを、 ソースコードの改変なしに分散環境上で実行可能 ただし、ユーザプログラムのみ対象としている OSカーネルなどは実行不可能 [7] D.J. Scales et al. ASPLOS-VII’96 [8] Y. Aridor et al. ICPP’99

まとめと今後の課題

まとめ 単一システムイメージを提供するための 仮想マシンモニタ ネットワークで結合された複数のマシン上に 仮想SMPマシンを構築 単一システムイメージを提供するための　　仮想マシンモニタ ネットワークで結合された複数のマシン上に　仮想SMPマシンを構築 共有メモリへのアクセスが少ない粗粒度タスクであれば、高性能を達成

今後の課題 (1/2) メモリの一貫性制御アルゴリズムの改良 より詳細な性能評価 現実的なアプリケーションを利用して 例）SPLASH-2、Apache

今後の課題 (2/2) 仮想資源と実資源の柔軟な対応付け 物理的なマシンの構成によらず、 常に一定数の仮想プロセッサを提供 仮想化 N-way SMPマシン N-way SMPマシン N-way SMPマシン また、我々の仮想マシンモニタは、動的な物理マシンの増減を隠蔽します。 具体的には、動的にマシンが追加・削除される中でも、仮想マシンのプロセッサ数を常に一定に保つことができます。 仮想化 N台のシングルプロセッサマシン

より将来的な課題 耐故障性 CPU性能などがヘテロな環境への適応