全体ミーティング 金田憲二

Agenda Progress Report Survey 1 paper from USENIX Virtual Machine Research and Technology (VM’04) 5 papers from USENIX Operating Systems and Design and Implementation (OSDI’04) ※ OSDIではセキュリティ関係の話が多かった

Progress Report

何を作っているか 分散した複数の計算機上に 並列計算機を仮想的に構築するシステム virtual physical Processor 分散した複数の計算機上に 並列計算機を仮想的に構築するシステム Processor Processor Memory virtual physical Processor Processor Memory Memory Network

何がうれしいか 分散資源を簡便に利用することができる 例）ゲストOS のスケジューラーが、個々の計算機に プロセスを割り振ってくれる

現在の実装状況 2種類の方式で実装している Full-virtualization (いわゆるCPU emulator) Bochs [http://bochs.sourceforge.net]を改造 Para-virtualization (いわゆるVMWare型) スクラッチから実装 ※ IA-32上でIA-32を仮想化 ホストOS、ゲストOS共にLinux

Full-virtualizationによる実装 一応ブートするところまでいった ところどころ動作がおかしい（遅い） 原因は？ Tickなどのエミュレーションが不十分なため？ 各仮想CPUにおいて、tickの経過速度が異なる HLT命令を発行しても少しの間しか止まらない

Para-virtualizationによる実装 ブートの途中でおかしくなる start_kernel() { printk(linux_banner); setup_arch(); parse_options(); trap_init(); init_IRQ(); sched_init(); softrq_init(); time_init(); console_init(); kmem_cache_init(); … … console_init(); kmem_cache_init(); mem_init(); kmem_cache_size_init(); pgtable_cache_init(); fork_init(); proc_cache_init(); vfs_cache_init(); buffer_init(); signals_init(); smp_init(); rest_init(); } ここまで

残りの発表の流れ Para-virtualizationによるVMの実装 シングルプロセッサマシンの場合 マルチプロセッサマシンの場合

シングルプロセッサの場合のVMの実装 実装の概要 特権命令のエミュレーション アドレス空間のエミュレーション

シングルプロセッサの場合のVMの実装 実装の概要 特権命令のエミュレーション アドレス空間のエミュレーション

VMの実装の概要 基本的にはゲストOSのコードをNativeに実行 必要に応じてハードウェアをエミュレーション 特権命令 アドレス空間 デバイス …

シングルプロセッサの場合のVMの実装 実装の概要 特権命令のエミュレーション アドレス空間のエミュレーション

特権命令とは CPUが特権レベルでないと実行できない命令 例）in命令、out命令 例）mov cr3命令 例）invtlb命令 I/Oポートとの入出力 例）mov cr3命令 ページディレクトリの物理アドレスの設定 例）invtlb命令 TLBのフラッシュ 実ハードウェアに影響する命令なので、　　　　　　　　ソフトウェアでエミュレーションする必要がある

特権命令のエミュレーション の概要 特権命令の実行直前にシグナルが発生する ようにする 特権命令の実行直前にシグナルが発生する　　ようにする カーネルのソースコードをコンパイル時に変換 そのシグナルを捕捉することにより、　　　　　　　　　　　Native実行とエミュレーション実行を切り替える

特権命令のエミュレーション の詳細 (1/5) 以下の2つのプロセスを用意する VMプロセス モニタプロセス VMプロセス モニタプロセス ゲストOSのコードをNativeに実行する モニタプロセス VMプロセスを監視する VMプロセス 監視 モニタプロセス

特権命令のエミュレーション の詳細 (1/5) カーネルのコードをコンパイル時に変換 変換前 変換後 特権命令の直前にundefined instructionを挿入 ※アセンブリからアセンブリへの簡単な変換器を作成 変換前 変換後 … mov %eax,%cr3 … ud2a mov %eax,%cr3

特権命令のエミュレーション の詳細 (3/5) VMプロセスがundefined instructionを実行  シグナルが発生する … ud2a mov %eax,%cr3 VMプロセス 監視 モニタプロセス

特権命令のエミュレーション の詳細 (4/5) 発生したシグナルをモニタプロセスが補足 VMプロセス モニタプロセス ptraceシステムコールを利用 シグナル … ud2a mov %eax,%cr3 VMプロセス 監視 モニタプロセス

特権命令のエミュレーション の詳細 (5/5) 命令をデコードし、ソフトウェアで エミュレーション実行 VMプロセス モニタプロセス 命令をデコードし、ソフトウェアで　　　　　　　　　　　　　　　　エミュレーション実行 0f 0b … ud2a mov %eax,%cr3 VMプロセス 90100055: 0f 0b ud2a 90100057: 0f 22 d8 mov %eax,%cr3 監視 0f 22 d8 モニタプロセス

シングルプロセッサの場合のVMの実装 実装の概要 特権命令のエミュレーション アドレス空間のエミュレーション

アドレス空間のエミュレーションにおける問題 ゲストOSのカーネル領域の配置 デフォルトだと、ホストのカーネル領域と同じ領域を確保しようとする ホストOSのユーザ領域中に確保する必要がある Linuxの仮想アドレス空間 0xc000000 0xffffffff ユーザ領域 カーネル領域

アドレス空間のエミュレーション (1/2) ゲストOSのコードを改変しカーネル領域をずらす エミュレーションのための領域も確保する 0xc000000 0xffffffff ホストOSのユーザ領域 ホストOSのカーネル領域

アドレス空間のエミュレーション (2/2) ゲストOSのページテーブルを参照して、ゲストOSの物理メモリと、ゲストOSのユーザ・カーネル領域を対応付ける mmapシステムコールを利用 ゲストOSのユーザ領域 ゲストOSのカーネル領域 エミュレーションのための領域 （ゲストOSの物理メモリの状態を保持） 0xc000000 0xffffffff

マルチプロセッサの場合のVMの実装 実装の概要 共有メモリのエミュレーション プロセッサ間割り込みのエミュレーション

マルチプロセッサの場合のVMの実装 実装の概要 共有メモリのエミュレーション プロセッサ間割り込みのエミュレーション

実装の概要 (1/2) 個々のプロセッサを別々のマシンがエミュレーション virtual physical Processor Memory virtual physical Processor Processor Memory Memory Network

実装の概要 (2/2) シングルプロセッサマシンの場合と比べ 共有メモリ プロセッサ間割り込み のエミュレーションがさらに必要になる

マルチプロセッサの場合のVMの実装 実装の概要 共有メモリのエミュレーション 概要 IA-32のメモリモデル 実装方式 プロセッサ間割り込みのエミュレーション

共有メモリのエミュレーション 通常のソフトウェアDSMの実装とほぼ同様 ただし、IA-32のメモリモデルを満たす必要がある virtual OSの提供するページ保護機構を利用 ただし、IA-32のメモリモデルを満たす必要がある Processor Processor write read Memory virtual physical Comm. Processor Processor write read Memory Memory

マルチプロセッサの場合のVMの実装 実装の概要 共有メモリのエミュレーション 概要 IA-32のメモリモデル 実装方式 プロセッサ間割り込みのエミュレーション

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

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

Processor Consistency (3/3) 直列化命令 E.g.) mfence命令 書き込みがリモートプロセッサに反映されたことを保障 PU1 PU2 PU3 write X to p write Y to q write Z to r mfence

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

マルチプロセッサの場合のVMの実装 実装の概要 共有メモリのエミュレーション 概要 IA-32のメモリモデル 実現方式 プロセッサ間割り込みのエミュレーション

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

Processor Consistencyの保障 (2/4) 全てのページを書き込み禁止にする mprotectシステムコールを利用 PC1 PC2 Twins Memory Memory Write X to p Write Y to q Write Z to r mfence …

Processor Consistencyの保障 (3/4) ページに対して書き込みがあると　 そのページのコピー(= 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 …

Processor Consistencyの保障 (4/4) 直列化命令を実行する時に， twinと現在のメモリを比較してdiffを作成する 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 …

Write Atomicityの保障 省略 各ページにownerなどを導入することにより実現

マルチプロセッサの場合のVMの実装 実装の概要 共有メモリのエミュレーション プロセッサ間割り込みのエミュレーション

プロセッサ間割り込みとは リモートプロセッサで割り込みを発生する機構 例）TLBのフラッシュ要求、CPUの起動要求 APICというハードウェアにより実現されている

プロセッサ間割り込みの エミュレーション APICのmapされた物理アドレス領域への 読み書きを捕捉し、エミュレーションする 例）物理アドレス0xee00020への読み込み  APICのIDを返す 例）物理アドレス0xee0300への書き込み 　　  プロセッサ間割り込みを発生

まとめと今後の課題

まとめ 分散した複数の計算機上に 並列計算機を仮想的に構築するシステム

今後の課題 実装の完成（10月中？） 性能評価