仮想マシン間にまたがるプロセススケジューリング

仮想マシン間にまたがる
プロセススケジューリング
1
田所秀和
光来健一
東京工業大学
千葉滋
仮想マシン環境でのスケジューリング
 仮想マシン(VM)を使ったサーバ統合

リソースの利用効率の向上
 システム全体で優先度を付けたい
例: DB > WEB > backup
 データベースプロセス
 ウェブプロセス
 バックアッププロセス
VM1
VM2


ウェブやデータベースの
サービスを阻害させない
DB
WEB
backup
優
先
度
VMM
Hardware
2
システム全体でのスケジューリングは難しい
 OSのスケジューリングとVMのスケジューリングだけで
はうまくいかない

OSのスケジューリングのみ


VM1 ＜ VM2


WEB と DB, backup 間に
優先度はつけられない
DBが止まった場合、
WEB ＜ backup になってしまう
VM1
WEB
VM2
？
DB
backup
優
先
度
VM1 ＞ VM2

DB ＜ WEBになってしまう
3
システム全体でのスケジューリングは難しい
 OSのスケジューリングとVMのスケジューリングだけで
はうまくいかない

OSのスケジューリングのみ


VM1 ＜ VM2


WEB と DB, backup 間に
優先度はつけられない
DBが止まった場合、
WEB ＜ backup になってしまう
VM2
VM1
WEB
DB
backup
優
先
度
VM1 ＞ VM2

DB ＜ WEBになってしまう
4
システム全体でのスケジューリングは難しい
 OSのスケジューリングとVMのスケジューリングだけで
はうまくいかない

OSのスケジューリングのみ


VM1 ＜ VM2


WEB と DB, backup 間に
優先度はつけられない
DBが止まった場合、
WEB ＜ backup になってしまう
DBが止まると
backupが動く
VM2
VM1
backup
WEB
DB
優
先
度
VM1 ＞ VM2

DB ＜ WEBになってしまう
5
システム全体でのスケジューリングは難しい
 OSのスケジューリングとVMのスケジューリングだけで
はうまくいかない

OSのスケジューリングのみ


VM1 ＜ VM2


WEB と DB, backup 間に
優先度はつけられない
DBが止まった場合、
WEB ＜ backup になってしまう
VM1 ＞ VM2

DB ＜ WEBになってしまう
VM1
WEB
VM2
DB
優
先
度
backup
6
VM間で協調するスケジューラの問題
 複雑なスケジューリングが必要

止めてはならないプロセス


協調して
スケジューリング
スケジューリングスレッド自身
無視すべきプロセス

syslogd
sched
 OSを変更する必要

スケジューリングスレッドを
動かす
sched
DB
WEB
優
先
度
backup
7
仮想マシンモニタによるプロセススケジューリング
 仮想マシンモニタ(VMM)が
直接ゲストOSのランキューを操作


ゲストOSのスケジューリングポリシーを変更
VM1
ゲストOSの変更が不要
 ポリシー例


DB
WEBまたはDBが動いているときは
backupを止める
VM1 ＜ VM2

VM2
WEBとDBだけが動いているときは、
DBの優先度を最高にする
WEB
ランキューを直接操作
backup
VMM
8
ゲストOSのランキューを操作する手順
 一定時間毎に全てのVMをチェック
1.
2.
VMを一時停止
ゲストOSがランキューを操作していないことを確認
データ構造を破壊しないように
 ランキューを操作していたらそのままVMを再開

3.
4.
ポリシーに従ってランキューを操作する
VMを再開
9
システムの構成
 スケジューラプロセス
ドメイン0のプロセスで実装
 ランキュー操作
 VMの優先度操作

VMMとしてXenを利用
ゲストOSはLinuxを対象
ドメイン0 ドメインU
 ドメイン0はスケジュール対象
外


DB
sched
スケジューラプロセスが常に動く
ように
ドメイン0では通常のアプリケー
ションは動かさない
ドメインU
WEB
backup
Xen VMM
10
スケジューリングのためのランキュー操作
 プロセスの一時停止

タスク構造体を取り除く
 プロセスの実行の再開

タスク構造体を戻す
 注意点

ランキューにつながれたプロセスの数も更新


ゲストOSの意味を保つ
実行中のプロセスは取り除かない
OS内のいろいろな場所にプロセスの情報が残っているので難しい
 今後の課題

11
一貫性を保ったランキューの操作
 ゲストOSが操作していないときのみランキューを操
作

VMMがランキューのスピンロックを調べる


メモリを読むことでチェック
SMP カーネルを使用

SMPカーネルの場合スピンロックを用いて排他制御を行う
ドメインUのスケジューラ
schedule() {
spin_lock(runqueue);
ランキューの操作
spin_unlock(runqueue);
};
12
ドメインUのカーネルメモリへのアクセス
 ドメインUのページをドメイン0上
のプロセス空間にマップ

ドメインUの仮想アドレスが含まれ
るマシンメモリのページ番号を求
める
仮想アドレス
ドメイン0
ページテーブル
ドメインU
マップ
 ページ境界をまたがないように
アクセス


構造体のメンバ変数など
メモリマップはページ単位
Xen VMM
P2Mテーブル
13
マシンメモリ
ドメインUのメモリ操作のための型情報取得
 カーネルのデバッグ情報から型情報を取得



カーネルを CONFIG_DEBUG_KERNEL=y でコンパイル
デバッグ情報から型情報の取得には gdb を使用
カーネルのコンフィグやマクロの解析が不要

コンパイラが解析する
struct runqueue {
spinlock_t lock;
unsigned long nr_running;
#ifdef CONFIG_SMP
unsigned long long cpu_load[3];
#endif
…
};
ソースコード
% gdb vmlinux-debug
(gdb) ptype runqueue_t
type = struct runqueue {
spinlock_t lock;
long unsigned int nr_running;
long unsigned int cpu_load[3];
…
}
デバッグ情報
14
ランキューのアドレスの取得
 仮想CPUのGSレジスタからrunqueueのアドレスを取得



Linux 2.6 ではCPU毎にランキューが存在
レジスタの値はVMMへのハイパーコールを用いて取得
x8664_pda は各CPU毎に固有のデータを管理(x86_64)
ドメインUのメモリ
GSレジスタ
x8664_pda
runqueue
struct x8664_pda {
task_t * current;
ulong data_offset;
…
};
data_offset
+
PER_CPU_RUNQUEUES
15
スケジューリング性能を調べる実験
 4つの実験をおこなった
ドメインUへのメモリアクセスによるオーバーヘッド
 優先度による性能の変化
 スケジューリングを行う間隔の影響
 プロセススケジューリングの挙動


環境
CPU: PentiumD 3.4GHz
 Memory: 2G (Dom0/DomU 1Gbyte/512Mbyte)
 Xen 3.0.4 (x86_64)
 Linux kernel 2.6.16.33

16
ドメインUのメモリアクセスのオーバーヘッド
 ドメイン0のプロセスにドメインUのメモリをマップして
アクセス
 仮想アドレスからフレーム番号の取得がボトルネック

ゲストOSのページテーブルを引くのに時間がかかる

ランキュー上のプロセスをたどるのに必要なマップの回数
最大 (42+実行待ちプロセスの数)*VCPUの数*ドメインの数
処理
時間（マイクロ秒）
ドメインの一時停止と再開
14.84
仮想アドレスに対応するフレーム番号の取得
68.95
ページをドメイン0のプロセスにマップ・アンマップ
13.72
1ワードのメモリアクセス
0.00
17
優先度をつけたことによる性能の変化
 lighttpdとtripwireを同時に動かす
同じドメインと、別ドメイン
 ポリシー

lighttpdの優先度をあげる
 lighttpdの性能は単独の時と
ほぼ同じ
 別ドメインの場合でもlighttpdを
優先できた
100万アクセスを処理するのにかかる時間 (秒)

lighttpd単独
lighttpdを優先
lighttpdとtripwireを同じ優先度
300
250
200
150
100
50
0
同じドメイン
別ドメイン
18
スケジューリング精度
 円周率を計算するpi1とpi2を同時に起動

同じドメイン上
 ポリシー

pi1が動いている間はpi2は実行しない

スケジューラプロセスが
動く間隔を変える
pi1
pi2
60
 間隔が長い

精度低下
 間隔が短い
オーバーヘッド大
 精度は上がる

実行時間 (秒)
50
40
30
20
10
19
0
0
2
4
ポーリングの間隔 (秒)
6
プロセススケジューリングの挙動 (1/2)
 4つのプロセスをスケジューリング


ドメインU1で3つ、ドメインU2で1つ
プロセスはすべて円周率を計算するプログラム
 ポリシー

Pi1の優先度を最低にする

pi1をドメインUの中で他にプロセスが動いていないときのみ動かす
ドメインU1
ドメインU2
pi2
pi3
優先度最低
pi4
20
pi1
Xen VMM
プロセススケジューリングの挙動 (2/2)
 ポリシーが実現できた
グラフの各線が下のときはプロセスが止まっている
 上のときは動いている
 pi1が20秒付近で動いているのはバグ

デーモン等その他のプロセス
ドメインU1のプロセスpi3
ドメインU2のプロセスpi4
ドメインU1のプロセスpi2
優先度最低のプロセスpi1
0
20
40
経過時間 (秒)
60
80
21
関連研究
 Virtual
Machine Introspection [NDSS'03, Garfinkel
et al.] [SOSP'05, Joshi et al.]

VMMからゲストOSの状態を取得
 Antfarm
[USENIX'06, Jones et al.], Geiger
[ASPLOS'06, Jones et al.]

VMM からゲストOSを仮定せずにプロセスやキャッシュ
の状態を取得する技術
 FoxyTechnique

[VEE'07, Yamada et al.]
VMMが仮想デバイスの振舞いを変更することで、ゲスト
OSの振舞いを間接的に変更する技術
22
まとめと今後の課題
 仮想マシンモニタによるプロセススケジューリングを
提案
ゲストOSのメモリを直接操作し、スケジューリングを変更
 システム全体でプロセスに優先度を付けることが可能
 実際にスケジューリングが行えることを確認

 今後の課題



I/Oバウンドなプロセスの制御
CPUで実行中のプロセスの制御
ゲストOSがWindowsの場合でのプロセス制御
23

Download Report