東京大学大学院情報理工学系研究科
コンピュータ科学専攻米澤研究室
博士課程1年　金田憲二

	1.概要

　本報告書では，今年度に試作した二つのソフトウェアについて述べる．一つは，ネットワークに つながった複数のマシン上で仮想的にマルチプロセッサマシンをエミュレーションするソフトウェアである．これは高速な仮想マシンの実現を可能にする技術で ある．もう一つは，分散環境におけるプログラムの開発・実行を支援する仮想端末である．PCクラスタ等の多数の計算機を簡便に利用することを可能にする．

	2.マルチプロセッサを仮想的に 実現するソフトウェア

	2.1 導入

　仮想マシンとは，ハードウェア（CPU・メモリ・デバイス等）のエミュレーションをソフト ウェアで行い，実マシンと同等の処理（例えばOSの実行）が可能なソフトウェアである．例えば，有名な仮想マシンとしてはVMWare Workstationがあるが，これはWindowsのインストールされた実マシン上で，ユーザアプリケーションとしてLinuxを走らせることが可能 である．仮想マシンは非常に有用なソフトウェアであり，様々な目的のために使用することができる．最もオーソドックスには，異なるOS上で動作するアプリ ケーションを1台の実マシン上で同時に実行するために使用するが，それ以外にも，マシンを破壊する恐れのあるソフトウェア（例えば，Webやメールを経由 して取得した，ウィルスである可能性のあるソフトウェア）を安全に実行するためのサンドボックスとしても利用することもできる．また，実行状態のスナップ ショットの取得・復元が可能であることを利用して，ソフトウェアのインストールによってOSに不具合が生じたらインストール前の状態にOSを復旧する，と いったことも可能である． こうした利点を併せもつ仮想マシンであるが，ハードウェアの性能向上にしたがって実用に耐えうる速度で利用可能な環境が増えるにつれて，目覚ましい普及を みせている．
　しかし，実用に耐えうる速度とはいっても，仮想化のオーバヘッドは非常に大きい．例えば，ソフトウェアでのエミュレーションを必要とする処理（例えば I/O）を頻繁に行うプログラムをVMWare上で実行すると，実機と比較して80% 近い性能低下となる．
　そこで，ネットワークにつながった複数の実マシン上 で1台の仮想マルチプロセッサマシンを実現するシステムを設計・実装する．この仮想マ シンは，複数のマシンのCPUを有効利用することによって高速に処理を行うことを可能にする．
このシステムは以下のモジュールから構成される（図1参照)

図1. システムの構成

VMMは，実マシンと仮想マシンのプロセッサとメモリを以下のように対応づける．

• 個々の実マシンのプロセッサは，仮想マシンのプロセッサの一つ一つと対応
• 複数の実マシンのメモリは，仮想マシンの（一つの）共有メモリと対応

ゲストOSが通常のマルチプロセッサと同様にスケジューリングを行ないプロセスを仮想マシンの 各プロセッサに割り当てると，個々の実マシン上でそのプロセスが走ることとなる．例えば，図2のように2台のWindowsがホストOSである実マシン上 で，デュアルプロセッサマシンをエミュレーションし，ゲストOSとしてLinux を走らせることができる．そして．Linuxのプロセススケジューリングにしたがって，各実マシンにプロセスが割り当てられる．これにより，実行可能なプ ロセスが多数存在するとき（例えば，\ttt{make}コマンドの実行時）などに，高速に処理を行なうことができる．

図2. 動作イメージ：2台の実マシン (Windows)上での仮想デュアルプロセッサマシン (Linux)の実行

また，以上の説明からも分かるように，このソフト ウェアは，PCクラスタなどの分散した計算資源を簡便に有効利用するためのシステムとしても有用である．既存のWindowsやLinuxといったOSの インターフェースのままで，ネットワークにつながって分散している計算資源を扱うことができるからである．
　Virtual Machine Monitorの実装における課題としては，主に，(1) CPUの特権レベルやデバイス等の仮想化と (2) 共有メモリのエミュレーションの二つが挙げられる．(1)のCPUの特権レベル等の仮想化は，仮想マシンを実装する上で共通の問題であり，効率的な実装に 関する既存研究も多く存在するため，ここでは詳しく述べない．この報告書では，(2)の共有メモリのエミュレーションを
中心に述べる．2.2節で今回対象とするIA-32のメモリモデルについて説明し，2.3節で仮想マシンのメモリモデルについて述べる．仮想マシンのメモ リモデルは，IA-32の仕様を満たしつつも効率的にエミュレーション可能なように設計する．2.4節で今回試作したVirtual Machine Monitorの実装について説明し，2.5節でそれを用いて行った予備実験について述べる．命令のエミュレーションにかかるオーバヘッドと，全実行命令 中のエミュレーションの必要な命令の比率を測定した結果，この高速化の手法が有望であることが示された．

	2.2 IA-32のメモリモデルの概要

　今回対象とするCPUは，最も普及していると思われるIA-32とする．つまり実マシン，仮 想マシンともにIA-32であるとする．この節では，IA-32のメモリ順序モデルの概要について述べる．メモリ順序モデルとは，与えられたプログラムに 対してメモリの読み書きがどのような順番で反映されなければいけないかを表すものである．基本的には，IA-32のメモリ順序モデルはプロセッサ順メモリ モデル
(Processor-ordered Memory Model)と呼ばれるものであり，

• 一つのプロセッサ内では，そのプロセッサに与えられたプログラムと同じ順番で，メモリの読み書きは反映される．
• ローカルプロセッサに書き込みが反映されたのと同じ順番で，遠隔プロセッサに対して書き込みは反映される．

	2.2.1 投機実行

　IA-32では読み込みは投機的に実行されうる．書き込みは原則的には\footnote {例えば例外として，String命令はOut-of-order実行されうる}投機的に実行されない．

	2.2.2 ストアバッファ

　IA-32はストアバッファをもつ．これは，書き込み命令が連続するようなときに，次々に発 生する書き込みデータをそのアドレスと共に一時貯めておいて，実際にメモリへの書き込み動作が完了するのを待たずに命令の制御を先に進めてしまう機構であ る．
　ストアバッファに溜っている書き込みデータは，ローカルプロセッサにのみ反映される．遠隔プロセッサに対して書き込みが反映されるのは，ストアバッファ からはき出だされたときである．

	2.3 仮想マシンのメモリモデル

　仮想マシンが提供するメモリモデルは，既存のIA-32用のプログラムを変更を加えることなく動作可能にするため， 前 節で述べたIA-32の仕様を満たす必要がある．ただし，仕様を満たしながらもソフトウェアで効率的にエミュレーション可能なものでなければいけない．例 えば，全ての書き込み命令を捕捉し，毎回遠隔マシンへと反映させるというは非効率である．そこで，基本的にはIA-32の仕様に従うが，” ストアバッファは無限長で，かつ，全ての書き込 み命令は直列化命令が実行されるまでストアバッファに格納され続ける．” というようにメモリモデルを設 計する．これによって，書き込み命令を遠隔マシンへと反映させるのは，直列化命令実行時 だけで済むようになる．

	2.4 Virtual Machinoe Monitorの実装

　前節で述べたメモリモデルを提供する仮想マシンを試作した．通常の命令はnativeに実機上で実行する．共有メモ リのエミュレーションに必要な最低限の命令のみ，ソフトウェアでエミュレーション実行する．
　Native実行中にエミュレーションの必要な同期命令を捕捉する必要がある．そのため，今現在の実装では，実行プログラムを事前に変換を行なってい る．
具体的には，同期命令の直前（直後）に不正な命令を挿入する．例えば，

mfence

といったアセンブリプログラムが与えられたら，

.byte 0x8e, 0xc8
mfence

と変換する．この変換によって，不正な命令を実行した際にシグナルが発生するようになるので，それを捕捉してエミュレーションの開始に移る．
　また，ローカルマシン上で行なわれた書き込みの遠隔マシンへの反映方法であるが，基本的にはオーソドックスなソフトウェア分散共有メモリの実装手法
に従う．mprotectを利用し各ページのアクセス保護を変更することによって実現している．

	2.5 予備実験

この節では，この仮想マシンが本当に性能が出るかを以下の二つを測定することよって評価す る．

• 命令のエミュレーションにかかるオーバヘッド
• エミュレーションの必要な命令が全実行命令中に占める割合

　命令のエミュレーションにかかるオーバヘッドがたとえ大きくても，エミュレーションの必要な命令の比率が少ないことが実験から分かれば，仮想 マシンの高速化が有望であるといえる．

	2.5.1 命令エミュレーションのオーバヘッド

　直列化命令（MFENCE命令）を10,000回実行した時の実行時間を，実マシン上と仮想マシン上とで測定する． 仮想マシンにおいては，MFENCE命令実行間で書き込みが行なわれる場合とそうでない場合のそれぞれにおいて測定を行なった．また，実験には Pentium4 Xeon 2.4GHzを用いた．

表1はこの実験の結果を示している．仮想マシン上での実行時間は実マシンのそれと比較して，書き込みなしの場合とあり の場合でそれぞれ1325倍と4052倍となっている． 書き込みが行なわれた場合の方が，書き込み結果を遠隔マシンに反映させる処理のため，オーバヘッドがより大きくなっている．

	2.5.2 エミュレーションの必要な命令の頻度

　Linux 2.2.19を起動時してから起動後lsコマンドを実行するまでの間に，LOCKプレフィックスのついた命令が実行された回数を測定した．この実験は， Bochs（x86エミュレータ）上で行なった．

図３. LOCKプレフィックスつき命令の，全実行命令中に占める割合

図３はこの実験の結果を示している．エミュレーション命令は，そのオーバーヘッドに対して， 十分高速化が望めるほどの頻度でしか行なわれないことが分かる（もちろん実行アプリケーションにも依存するが）．

	3.まとめ

	3.1 導入

　多数の分散したマシン上で，プログラムの開発・実行を行なうのは簡単ではない．例えば，PCクラスタ等のネットワー クにつながった多数のマシンを利用する際には，クラスタ内の全ノードに対してプロセスの起動・削除を行なったり，プログラムやデータの転送を行なうことが 必要となる．こうしたことを行なう
ために最も一般的な方法は，rsh，rcp，ps, killといった既存のUNIXコマンドをスクリプトを記述することによって利用するものであるが，多数のマシンに対してこうした処理を行なうのは簡単で はない．また，複数のマシンに対してインタラクティブにコマンド実行を行なうことが必要である場合も多いが（例えば管理者パスワードの入力），これも既存 のUNIX環境上ではこれも簡単ではない．既存のexpectというインタラクティブな操作を支援するスクリプト言語も存在するが，分散環境上で用いるの 適しているとはいえない．多数のマシンを簡便に（なるべく既存のUNIX の仮想端末のインターフェースのままで）利用できるソフトウェアが望まれる．

　そこで，分散環境におけるプログラムの開発・実行を支援する仮想端末を試作した．この仮想端末は，以下の機能を提供する．

• 入出力の転送先マシンの切り替え
• 大域ファイルシステム
• 大域プロセス空間

これらの機能を駆使することにより，PCクラスタなどの多数のマシンを簡便に利用することができる．また，この端末は ユーザレベルで実現されているため，OSの改変や管理者権限を必要としない．
　この節の残りは以下のように構成される．3.2節でこの仮想端末が提供する機能を説明する．3.3節でその実装について述べる．

	3.2 仮想端末の提供する機能

この節では，仮想端末の提供する各機能を説明する．

	3.2.1 入出力の転送先マシンの切り替え

端末にgoto hostと入力することにより，端末の入出力先をhostに切替えることができる．例えば，初期状態でmachine1という名前のマシンにログインして いたとする．ここでhostnameコマンドを実行すると，当然ホスト名であるmachine1が返ってくる．

% hostname
machine1

ここで，goto machine2と端末に入力することによって，入出力先をmachnie01からmachine2に切り替えることができる，

% goto machine2

切替え後，例えばhostnameコマンドを実行すると，machine1が返ってくる．

% hostname
machine2

　この機能の特長として，まず，既存のｒshと異なり，端末切替え前後で環境変数などが保存される点がある．例えばmachine1→machine2→machine1 といった順で端末を切替えた時に，最後にmachine1を訪れた時のカレントディレクトリ等の情報は，最初に訪れた時のものと同じものとなる．
　また，正規表現を用いてgoto先のマシンを指定して，複数のマシンに対して同時にコマンド入力を行なうことができる．例えば，

% goto *
% su
Password:
% shutdown

と入力することにより，利用可能な全マシンをシャットダウンすることができる．

	3.2.2 大域ファイルシステム

遠隔マシン上のファイルにアクセスすることができる．ファイルのパスをhost:fileとして指定することによっ て，マシンhost上のファイルfileにアクセスすることができる．例えば，machine2上のファイル/tmp/fooをローカルホストのカレント ディレクトリにコピーするには，

% cp machine2:/tmp/foo ./

と入力すればよい．

	3.2.3 大域プロセス空間

既存のpsコマンドで，遠隔マシン上のプロセスの情報を取得することができる．また，既存のkillコマンドで，遠隔 マシン上で走っているプロセスに対してシグナルをとばすことができる．これによって，例えば，以下のようにmachine2で立ち上げたプロセスを machine1から削除することなどが可能となる．

% goto machine2
% ./a.out &
[1] 101307
% goto machine1
% ps -a
PID TTY TIME CMD
101307 tty1 00:00:02 a.out
% kill 101307
[1]+ Terminated ./a.out

	3.3 実装

この節では，前節に述べた機能をどのように実装しているかについて述べる．

	3.3.1 システムの構成

　システムは，各マシン上で動作するデーモンと，ユーザとの入出力を扱うマルチプレクサからなる．各デーモンはシェル を立ち上げる．ユーザの入力は，gotoで現在指定されているマシン上のシェルへと，マルチプレキサーとデーモンを介して転送される．同様に，シェルの出 力結果もデーモンを介してマルチプレキサに送られ，マルチプレキサがその結果を端末に表示する．
　gotoコマンドが実行されると，マルチプレキサは入出力の転送先をそのコマンドで指定されたマシン上のデーモンへと切り替える．
またデーモンは，トレーサというptraceによってシェルのシステムコールの監視を行なうプロセスも起動する．ptraceは，システムコール発行の直 前・直後を捕捉し，その引数・返り値を変更することができる．これを利用して，大域ファイルシステムと大域プロセス空間を実現している．

	3.3.2 大域ファイルシステム

　ファイルアクセス関連のシステムコールを捕捉することによって実現している．例えば，マシンhost上のファイル fileに対して読み書きをが行なわれる場合は，以下のようにして動作する．
　まず．デーモンはopenシステムコールを実行直前に捕捉し，以下の操作を行なう．

1. マシンhostからファイルfileを取得し，ローカルの適当な ファイル（例えば/tmp/file）に一時的に格納する．
2. システムコールの引数を変更し，その一時ファイルを開くようにする． この例だと，openの第一引数を/tmp/fileに変更する．
3. システムコールの実行を再開させる．

これ以降，このopenシステムコールの返り値のファイル記述子を通しての読み書きは，実際には一時ファイルに対して 行なわれるようになる．
　そして，その一時ファイルがcloseシステムコールによって閉じられると，そのファイルに書き込まれた内容がhost上のfileへと転送する．
　この他にも，stat，getdentsといったシステムコールも，openシステムコールの場合とほぼ同様の方法で捕捉も行なっている．

	3.3.3 大域プロセス空間

　fork，killといったプロセスIDを引数・返り値にとる関数と，/procファイルシステムへのアクセスを捕 捉することによって実現している．
　まず，fork，killなどのシステムコールを捕捉し，通常16ビットであるプロセスIDを32ビットに拡張し，そのプロセスがどのマシンで走ってい るかを識別可能にする．より具体的には以下のような操作を行なう．

• 各ホストに一意な16ビットのIDを割り振る（これをマシンIDと呼ぶ）．
• fork・cloneシステムコールを捕捉し，その返り値である子プロセスのプロセスIDに，ローカルマ シンのマシンIDを付加する．

　そして，killシステムコールが発行された際には，その引数のプロセスIDを元に，プロセスが動作しているマシン を特定する．もし，マシンIDがローカルマシンのものであれば，killシステムコールの引数を拡張前のプロセスIDに変更し，通常通りkilｌを行な う．もし，そのマシンIDが遠隔マシンのものであれば，その遠隔マシンにkillを要求する．
　また，/proc以下のファイルへのopenが発生したら，全てのマシンの/proc以下の情報を取得してくるようにする．これによって，既存のps} コマンド自体を変更することなく，遠隔プロセスの情報の取得が可能となっている．

	4.まとめと今後の活動予定

　本報告書では，今年度に試作した，仮想的にマルチプロセッサマシンを実現するソフトウェア と， 分散環境におけるプログラムの開発・実行を支援する仮想端末について述べた．今後は，以下のような活動を行う予定である．まず，仮想マシンの実装を完成させる．CPUの特権レベルの仮想化などの実装を行い，既 存のLinux等のOSを走らせることを可能にする．次に，仮想マシンに耐故障などの機能を追加することを目指す．