Virtualizing a Multiprocessor Machine on a Network of Computers 東京大学米澤研究室D2 金田憲二

発表の流れ 背景 基本設計 VMMの実装 共有メモリの一貫性制御 関連研究 まとめと今後の課題

発表の流れ 背景 基本設計 VMMの実装 共有メモリの一貫性制御 関連研究 まとめと今後の課題

グリッド計算 広域に分散した多数の計算資源上での並列計算 例）複数の地理的に分散したクラスタ上で高性能計算 例）多数の遊休PC群を利用して地球外生命体を探索

グリッド計算の実現には… Customizableかつ安全な実行環境が必須 ヘテロ環境上に、自分に適した環境を構築したい 例）全計算機に同一OS・ライブラリをインストールしたい 信頼できないプログラムを安全に実行したい 異なるOSがインストールされたマシン群（winXP、Linux2.4、Linux2.6） 複数のユーザ（それぞれ違う色にする） Linux2.6 Linux2.4 Solaris Win2000

一つのアプローチ Virtual Machine Monitor (VMM)の利用 個々のユーザは、それぞれ別々の仮想機械上でプログラムを実行するようにする 前のスライドであったマシン上に、 複数の小さな仮想マシンを載せる（ユーザと同じ色）

VMMによるアプローチの利点 仮想機械は実機械から独立しているので 各ユーザごとに使用するOS・ライブラリを カスタマイズ可能 仮想機械をサンドボックスとして利用可能 Linux2.6 Linux2.6 Linux2.6 Linux2.6 仮想マシンに同じOSがのる例 Linux2.6 Linux2.4 Solaris Win2000

既存研究 [1~5]など 例）VMPlant [3] 仮想機械の柔軟な生成 仮想機械の設定の自動化

既存研究の問題点 並列計算のための枠組みとしては不十分 VMM自体は、遠隔ジョブ投入・スケジューリングなどの機能を提供しない 既存の並列計算ツールとの組み合わせが必須 計算機の利用にかかる手間が増大

本研究の目的 より並列計算の実行に適したVMMの実現 分散した資源を非常に簡便に利用できるようにする

提案するシステム 複数の分散した計算機上に 仮想的な並列計算機を構築するシステム 仮想空間 Nプロセッサのマルチプロセッサマシン 実空間 複数の分散した計算機上に　　　　　　　　　　　　　　　　　　　　　仮想的な並列計算機を構築するシステム 仮想空間 Nプロセッサのマルチプロセッサマシン 実空間 N台のシングルプロセッサマシン

本システムの利点 分散資源の簡便な利用 仮想空間 Nプロセッサのマルチプロセッサマシン 実空間 N台のシングルプロセッサマシン ゲストOSのスケジューラが、個々の計算機にプロセスを　自動的に割り振ってくれる 仮想空間 プロセス プロセス プロセス プロセス プロセス プロセス プロセス プロセス Nプロセッサのマルチプロセッサマシン 実空間 N台のシングルプロセッサマシン

動作デモ ２台のラップトップPC（シングルプロセッサ）上に仮想デュアルプロセッサマシンを構築 その仮想機械上でLinuxをブートさせる まだ実装がナイーブなため非常に遅いが イメージ図

目標とする性能 VMWareとの性能比 100% 1 2 4 8 16 32 プロセッサ数 ※それほどスケーラビリティは求めない ある程度で十分 グリッド計算という話の流れとは反してしまうが 1 2 4 8 16 32 プロセッサ数

発表の流れ 背景 基本設計 VMMの実装 共有メモリの一貫性制御 関連研究 まとめと今後の課題

基本設計 仮想機械のインターフェース 対象とするプロセッサ システム構成 仮想ハードウェアと実ハードウェアの対応

仮想機械のインターフェース Instruction Set Architecture (ISA)を仮想化 IA-32を対象とする Paravirtualization 仮想機械と実機械は基本的には同一アーキテクチャ ただし、一部カーネルコードの改変が必要 仮想機械のプロセッサ数 = 実機の総プロセッサ数

対象とするプロセッサの詳細 Pentium 4, Intel® XeonTM, P6 Pentium®, Intel486TM ゆるい メモリの　　　　　　　　　　一貫性 厳しい

システムの構成 Hosted architecture VMMはホストOS上のユーザプロセス 仮想機械 実機械 ゲストOS VMM プロセッサ メモリ VMM ホストOS プロセッサ プロセッサ プロセッサ プロセッサ 実機械 メモリ メモリ メモリ メモリ

Hosted Architectureの特徴 IA-32の仮想化に適している sensitiveな特権命令の扱い（後述） 数多くの周辺デバイスを扱うのに適している ホストOSのドライバが利用可能なので インストール済みのホストOSとゲストOSとを共存させることができる ※ハードウェアの上に直にVMMが置かれる場合と比較すると、性能面では劣る

仮想ハードウェアと実ハードウェアの対応 プロセッサ  1対1対応 メモリ、I/Oデバイス  1対多 仮想機械 実機械 ゲストOS VMM

仮想ハードウェアと実ハードウェアの対応 プロセッサ  1対1対応 メモリ、I/Oデバイス  1対多 仮想機械 実機械 ゲストOS VMM

発表の流れ 背景 基本設計 VMMの実装 共有メモリの一貫性制御 関連研究 まとめと今後の課題

VMMの実装 以下のハードウェアを仮想化する プロセッサ （共有）メモリ I/Oデバイス

プロセッサの仮想化 ほとんどの命令は、実機上でNative実行 実機やホストOSの状態と干渉する命令のみ、ソフトウェアでエミュレーション実行 以降、エミュレーションを必要とする特殊な命令をsensitive命令と呼ぶ

Sensitive命令の例 in命令、out命令 mov cr3命令 invtlb命令 I/Oポートへの入出力 ページディレクトリを指す物理アドレスの書き換え invtlb命令 TLBのフラッシュ

Sensitive命令の分類 特権命令 非特権命令 例）lgdt命令（GDTRレジスタへの書き込み） CPUの特権レベルがもっとも高い時のみ実行可能 低い特権レベルで実行すると、例外が発生 非特権命令 例）sgdt命令（GDTRレジスタからの読み込み） CPUの特権レベルに関わらず実行可能

Sensitive命令のエミュレーション 以下の2つのプロセスを用意する VMプロセス ゲストOS上のコードをNativeに実行 モニタプロセス VMプロセスを監視 sensitive命令の実行を捕捉し エミュレーション VMプロセス 監視 モニタプロセス

Sensitive命令の実行の捕捉 特権命令の場合 非特権命令の場合 ※LiLyVMと基本的には同じ手法 実行時に発生する例外を捕捉 ※ユーザプロセスなので、特権レベルが低い 非特権命令の場合 カーネルコードを（静的に）書き換え、　　　　　　　　実行時に例外が発生するようにする そうして発生した例外を捕捉 ※LiLyVMと基本的には同じ手法

Sensitiveな非特権命令の エミュレーション (1/4) カーネルのコードをコンパイル時に変換 非特権命令の直前にundefined instructionを挿入 ※アセンブリからアセンブリへの簡単な変換器を作成 変換前 変換後 … sgdt 0x012345 … ud2a sgdt 0x012345

Sensitiveな非特権命令の エミュレーション (2/4) VMプロセスがundefined instructionを実行  シグナルが発生する シグナル … ud2a sgdt 0x012345 VMプロセス 監視 モニタプロセス

Sensitiveな非特権命令の エミュレーション (3/4) 発生したシグナルをモニタプロセスが捕捉 ptraceシステムコールを利用 シグナル … ud2a sgdt 0x012345 VMプロセス 監視 モニタプロセス

Sensitiveな非特権命令の エミュレーション (4/4) 命令をデコードし、エミュレーション実行 エミュレーション終了後、VMプロセスの実行を再開 0f 0b … ud2a sgdt 0x012345 VMプロセス 監視 0f 01 05 45 23 01 00 モニタプロセス

メモリの仮想化 ページング機構の仮想化 LiLyVMとほぼ同様 共有メモリ機構の仮想化

ページング機構の仮想化 ページの物理メモリへのマップ カーネル空間の重複の回避 ページフォルトのエミュレーション 仮想機械のページディレクトリ・テーブルを参照 カーネル空間の重複の回避 ゲストOSのカーネルコードを書き換え ページフォルトのエミュレーション SIGSEGVシグナルを捕捉

仮想機械の物理メモリを 保持するための領域 ページの物理メモリへのマップ (1/3) ユーザアドレス空間を以下のよう分割 仮想機械のリニアアドレス空間 仮想機械の物理メモリを　保持するための領域 0x00000000 0xc0000000 0xffffffff ユーザ空間 （ホストOSの）カーネル空間

仮想機械の物理メモリを 保持するための領域 ページの物理メモリへのマップ (1/3) ユーザアドレス空間を以下のよう分割 リニアアドレス空間の開始アドレス 仮想機械のリニアアドレス空間 物理メモリの開始アドレス 仮想機械の物理メモリを　保持するための領域 0x00000000 0x00000000 0x00000000 0xc0000000 0xffffffff ユーザ空間 （ホストOSの）カーネル空間

ページの物理メモリへのマップ (2/3) 仮想機械のページディレクトリ・テーブルを 参照し、ページのマッピングを行う 仮想機械のページディレクトリ・テーブルを 参照し、ページのマッピングを行う mmap、munmapシステムコールを利用 リニアアドレス 物理アドレス 0x10001000 0x00001000 0x90002000 0x00002000 … 0x１0001000 0x00001000 0x00000000 0x00000000 リニアアドレス空間 物理メモリ 0x00000000 0xc0000000 0xffffffff

ページの物理メモリへのマップ (2/3) 仮想機械のページディレクトリ・テーブルを 参照し、ページのマッピングを行う 仮想機械のページディレクトリ・テーブルを 参照し、ページのマッピングを行う mmap、munmapシステムコールを利用 リニアアドレス 物理アドレス 0x10001000 0x00001000 0x90002000 0x00002000 … 0x90002000 0x00002000 0x00000000 0x00000000 リニアアドレス空間 物理メモリ 0x00000000 0xc0000000 0xffffffff

ページの物理メモリへのマップ (3/3) ページディレクトリ・テーブルの更新にあわせてマッピングも更新 例）cr3レジスタの値が更新された際 例）TLBのフラッシュされた際

カーネル空間の重複の回避 ゲストOSとホストOSのカーネル空間が同じ領域を使用  ゲストOSのカーネル空間のベースアドレスを変更 ゲスト・ホストともにLinuxの場合  ゲストOSのカーネル空間のベースアドレスを変更 ゲストOSのカーネル空間 0x00000000 0xa0000000 リニアアドレス空間 物理メモリ ホストOSの カーネル空間 0x00000000 0xc0000000 0xffffffff

共有メモリ機構の仮想化 ソフトウェアDSMと同様の仕組みで実現 ハードウェアのメモリ保護機能を利用

Naïveな実装 (1/2) ページごとに以下の状態を管理 Exclusively Shared Shared Invalid （自プロセッサのみが）最新の状態をローカルに保持しているページ 読み込み・書き込み可能 Shared （複数プロセッサが）最新の状態をローカルに保持しているページ 読み込みのみ可能なページ Invalid 読み込み・書き込み共に不可能なページ

Naïveな実装 (2/2) 動作例 Invalidなページへの読み込み 仮想プロセッサ1 仮想プロセッサ2 Invalid Ex. shared shared shared メモリ メモリ VMプロセス VMプロセス ページの最新の状態を送信 SIGSEGVを捕捉 モニタプロセス モニタプロセス

～注意～ SIGSEGVシグナルの取り扱い InvalidなページへのアクセスによるSIGSEGVと、ページフォルトによるSIGSEGVとを、　　　　　　　　　　　　　　きちんと区別して扱う必要がある 普通のDSMにはない点

I/Oデバイスの仮想化 全I/Oデバイスの状態を監視するサーバを用意 各プロセッサは、I/Oをエミュレーションする際に このサーバと通信する 仮想プロセッサ1 仮想プロセッサ2 I/Oサーバ VMプロセス VMプロセス モニタプロセス モニタプロセス

I/Oポートへの読み込みをエミュレーション 基本的な動作例 I/Oポートからの読み込み … in命令 I/Oポートへの読み込みをエミュレーション 仮想プロセッサ VMプロセス in命令を捕捉 in命令のソースオペランドに値を格納 I/Oサーバ モニタプロセス サーバに リクエストを送信 読み込み結果を返信

特殊なI/Oデバイス Advanced Programmable Interrupt Controller (APIC) Memory Mapped I/O 例）物理アドレス0xee00020への読み込み  APICのIDを返す 例）物理アドレス0xee0300への書き込み  プロセッサ間割り込みを発生 例）、CPUの起動要求 プロセッサ間割り込み = リモートプロセッサに割り込みを発生させる機構 （TLBのフラッシュ要求、CPUの起動要求などに用いる）

APICのエミュレーション APICのmapされた物理アドレス領域への 読み書きを捕捉し、エミュレーションする ページを読み書き禁止にしておく プロセッサ間割り込みなども、適宜マシン間で通信することによりエミュレーションする

発表の流れ 背景 基本設計 VMMの実装 共有メモリの一貫性制御 関連研究 まとめと今後の課題

共有メモリの一貫性制御 前述のNaïveな実装は非常に遅い IA-32のメモリモデルを満たす限りにおいて、最適化する

IA-32のメモリモデル あるPUから見えるメモリの状態と、別のPUから見えるメモリの状態とは、必ずしも一致しない ただし以下の制約を満たす Processor consistency Write atomicity アドレス0x1000の値は0 アドレス0x1000の値は1 プロセッサ プロセッサ メモリ

Processor Consistency (1/2) あるプロセッサが行った書き込みは， 同一プロセッサには，すぐに反映される 異なるプロセッサには，遅れて反映されうる PU1 PU2 write X to p 書き込み反映 read from p 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

（アドレスpに対する）読み書きは，この間に 発生しない Write Atomicity 書き込みはリモートプロセッサにatomicに　　　　　　　　反映される PU1 PU2 PU3 write X to p （アドレスpに対する）読み書きは，この間に　　　　　　　　　　発生しない 書き込みがリモートプロセッサに反映されるときは，全てのプロセッサに対して同時に反映される あるプロセッサが行った書き込みは，他の全てのリモートプロセッサに同じタイミングで反映される 同じアドレスに対する書き込み 最初のwriteが反映され終わってない間はread, writeは起こらない

同期命令 一時的にメモリ一貫性を強めるために用いる 直列化命令 アトミック命令

直列化命令 例） mfence命令 書き込みがリモートプロセッサに反映されたことを保障 PU1 PU2 PU3 write X to p write Y to q write Z to r mfence

アトミック命令 LOCK prefix Exchange命令 例）lock; cmpxchg このprefixのついたread-modify-write命令は，atomicに実行されることが保証される Exchange命令 例） XCHG命令 Exchange Register/Memory with Register

最適化の例 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) 全てのページを書き込み禁止にする mprotectシステムコールを利用 PC1 PC2 Twins Memory Memory Write X to p Write Y to q Write Z to r mfence …

Multiple Writes (3/4) ページに対して書き込みがあると そのページのコピー(= twin)を作成する ページに対して書き込みがあると　 そのページのコピー(= twin)を作成する そのページへの書き込みを許可する PC1 PC2 Twins Memory Memory Write X to p Write Y to q Write Z to r mfence p X q Y r Z …

Multiple Writes (4/4) 直列化命令を実行する時に， twinと現在のメモリを比較してdiffを作成する PC1 PC2 Twins Memory Memory Write X to p Write Y to q Write Z to r mfence p X Y Z q r …

発表の流れ 背景 基本設計 VMMの実装 共有メモリの一貫性制御 関連研究 まとめと今後の課題

関連研究 (1/3) Virtual Machine Montiors (VMMs) VMWare ESX Server [6], Disco [7] 仮想的にマルチプロセッサマシンを構築可能 ただし、実機もマルチプロセッサであることが前提 LilyVM [8], FAUmachine [9] Hosted architecture VMMはホストOSのユーザプロセス ただし、シングルプロセッサマシンのみ対象

関連研究 (2/3) シミュレータ・エミュレータ SimOS [10] Bochs [11] マルチプロセッサマシンをシミュレーション可能 ただし、実機もマルチプロセッサであることが前提 Bochs [11] マルチプロセッサマシンをエミュレーション可能 ただし、エミュレーションは逐次 定期的にエミュレーションするプロセッサを切り替え

関連研究 (3/3) ソフトウェアDSMシステム Shasta [12] 既存の並列プログラムをソースコードの変更なしに動作させることができる ただし、ユーザプログラムのみ実行可能 OSのカーネルなどは実行不可能

発表の流れ 背景 基本設計 VMMの実装 共有メモリの一貫性制御 関連研究 まとめと今後の課題

まとめ 複数の分散した計算機上に　　　　　　　　　　　　　　　　　　　　　仮想的な並列計算機を構築するシステム 分散環境を簡便に利用するための枠組みを提供

当面の課題 実装のチューニング メモリ一貫性制御アルゴリズムの改良 性能評価 今現在は、コンテクストスイッチなどがナイーブに実装されている シングルプロセッサのエミュレーション自体が遅い メモリ一貫性制御アルゴリズムの改良 性能評価

今後の課題 より現実的な環境で動作可能にする 耐故障性 ヘテロな環境における効率のよいスケジューリング 動的な計算機の追加・削除への適応

参考文献

[1] Amr Awadallah and Mendel Rosenblum [1] Amr Awadallah and Mendel Rosenblum. “The "vMatrix: A Network of Virtual Machine Monitors for Dynamic Content Distribution”. In Proceedings of the 7th International Workshop on Web Content Caching and Distribution (WCW’02), 2002 [2] Ananth I. Sundararaj and Peter A. Dinda. “Towards Virtual Networks for Virtual Machine Grid Computing”. In Proceedings of the 3rd Virtual Machine Research and Technology Symposium (VM’04), 2004 [3] Ivan Victor Krsul and Arijit Ganguly and Jian Zhang and Jose A.B. Fortes and Renato J. Figueiredo. “VMPlants: Providing and Managing Virtual Machine Execution Environments for Grid Computing”. In Proceedings of the SC2004, 2004 [4] R. Figueriredo and P.Dinda and J.Fortes. “A Case for Grid Computing on Virtual Machines”. In Proceedings of the 23rd IEEE International Conference on Distributed Computing (ICDCS’03), 2003

[5] Xuxian Jiang and Dongyan Xu [5] Xuxian Jiang and Dongyan Xu. “SODA: a Service-On-Demand Architecture for Application Service Hosting Utility Platforms”. In Proceedings of the 12th IEEE International Symposium on High Performance Distributed Computing (HPDC-12), 2003 [6] Carl A. Waldspurger. “Memory Resource Management in VMWare ESX Server”. In Proceedings of the 5th Symposium on Operating System Design and Implementation (OSDI’02), 2002 [7] Edouard Bugnion and Scott Device and Mendel Rosenblum. “Disco: Running Commodity Operating Systems on Scalable Multiprocessors”. In Proceedings of the 16th ACM Symposium on Operating Systems Principles (SOSP), 1997. [8] Hideki Eiraku and Yasushi Shinjo. “Running BSD Kernels as User Processes Linux by Partial Emulation and Rewriting of Machine Instructions”. In Proceedings of the BSDCon 2003, 2003

[9] Hoxer, H. -J. and Buchacker, K. and Sieh, V [9] Hoxer, H.-J. and Buchacker, K. and Sieh, V. “Implementing a User-Mode Linux with Minimal Changes from Original Kernel”. In Proceedings of Linux-Kongress 2002, 2002 [10] Mendel Rosenblum and Stephen A. Herrod and Emmett Witchel and Anoop Gupta. “Complete Machine Simulation: The SimOS Approach”. IEEE Parallel and Distributed Technology: Systems and Applications, 1995 [11] Bochs: The Open Source IA-32 Emulation Project. http://bochs.sourceforge.net/ [12] Daniel J. Scales and Kourosh Gharachorloo and Chandramohan A. Thekkath. “Shasta: A Low Overhead, Software-Only Approach for Supporting Fine-Grain Shared Memory”. In Proceedings of the 7th ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-VII), 1996 [13] IA-32 Intel® Architecture Software Developer’s Manual , 2003