vCPUをどうpCPUに割り当てるかを決定する機構　Xenにおける2つの主要スケジューラのアルゴリズムと性能

スケジューラやVM間通信機構の機能を提供するXenの仕組み

西村啓佑氏：西村です。「Xenのスケジューラがぜんぜんわからん」というタイトルで発表します。

出オチとして、タイトルどおりXenのスケジューラの話をしようと思いますが、そもそもXenってなんぞやというところから説明したいと思います。XenはVMMの一種で、例えば今回話すスケジューラやVM間通信機構といった機能を提供しています。

Xenのアーキテクチャの世界観の中で、VMMに対するVMはドメインと呼ばれていて、（スライドを示して）この図のように、1つのVMM上で複数のドメインを立ち上げることができます。

各ドメインはvCPUのバーチャルCPUという概念を持っていて、そのvCPUがpCPUに割り当てられることで初めて実行できます。VMMにおけるスケジューラは、vCPUをどうやってpCPUに割り当てるかを決定する機構です。

vCPUスケジューリングについて、もう少し検討していきます。vCPUスケジューリングの目的は計算資源の再配分なので、OSのスケジューラとまったく同じです。OSのスケジューリングの概念と比較すると、スケジューリングに関する単位がVMとProcessのように異なっていたり、実際に動作するアプリケーションに関するセマンティックな情報の粒度が異なっていたりします。つまり、一般的にはOSのほうがアプリケーションに詳しいといったことが起こり得ます。

いろいろありますが、基本的にOSから見た時のCPUの世界観は少し違っていて、常にCPUが使える環境とは限りません。従来の一般的なOSはCPUが常に使えることが前提でした。例えば、I/Oの発生時には、すぐCPUに割り込みが来る想定ですし、IPCの発生時にはすべてのコアが動作しているという想定ですが、このような過程は一切使えないのが仮想化の現状です。

Creditスケジューラのアルゴリズム

すごく一般的なXenのスケジューラの話をしましたが、具体的なアルゴリズムについて話そうと思います。いろいろなスケジューラが提案されていて、実際にマージされていますが、今回のLTの対象はCreditスケジューラとCredit2スケジューラの2つです。

これらは一般的な汎用スケジューラで、リアルタイムスケジューラと言われるものではありません。元デフォルトスケジューラと、今のデフォルトスケジューラなので、Xenが一般的に使われているかはさておき、それぞれがかなり一般的に使われています。

Creditスケジューラについて説明します。Creditスケジューラは、Xenのバージョン3.0から4.11までがデフォルトでした。Xenは確か2003年にリリースされているはずなので、すごく長い期間デフォルトのスケジューラはCreditスケジューラでした。最新のXenのバージョンは4.15なので、つい最近までCreditスケジューラだったと言えます。

Creditスケジューラの特徴は、固定のタイムスライスとProportional Shareという概念です。Proportional share schedulingがCreditスケジューラの特徴で、デフォルトではタイムスライスは30ミリセコンドに固定されています。

また、Proportional Shareは、各VMあるいはvCPUがWeightで、優先度に比例した時間割り当てを受けるといったスケジューリングのストラテジーです。

名前の「Credit」はWeightに応じて配分された実行時間を指しています。Creditを使い果たした、つまりCreditがゼロ以下のVMあるいはvCPUはOVERと呼ばれ、残っているvCPUはUNDERと呼ばれます。CreditスケジューラはUNDERのvCPUをラウンドロビンで、順にスケジューリングしていく実装になっています。

ここで重要なのはCreditの値には依存しないということです。「ゼロより大きいか」が重要な要素となっています。

I/O Latencyを削減するために工夫がされている

（スライドを示して）基本的なスケジューリングのアルゴリズムをフローチャートにまとめました。まず、すべてのvCPUに対してWeightに応じたCreditを加算します。すると、Creditが正のvCPUを1つ選んで実行します。そして、TS時間が経ったあとに実行時間分のCreditを消費します。Creditスケジューラは、これをグルグル繰り返します。

基本的なアルゴリズムはこうですが、実際それだけでは機能として不十分です。具体的にはI/Oが発生した時のLatency（I/O Latency）を削減する工夫がなされています。

具体的にはUNDERなVMへのEvent、つまりI/Oが発生したら、一時的にそのUNDERより強いBOOSTという最高優先度でvCPUを実行できます。（スライドを示して）この図にその概念を表しました。基本的にUNDERの間で、ラウンドロビンでスケジューリングが行われています。しかし、I/Oが発生して、BOOSTという優先度が割り当てられたvCPUは、UNDERでどんなvCPUが実行していようが優先して実行されるため、UNDERの中に割り込んで実行されることになります。

そのようなBOOSTの影響を定量化する実験を行いたいと思います。実験の目的として、あるVMが別のVMのI/O Latencyに与える影響についても同時に調査したいと思います。方法として、バックグラウンドで動作するVMで全体に負荷をかけつつ、別のVM間のpingのラウンドトリップタイムを計測します。

負荷は2つ用意します。1つ目は、iperfで別マシンと通信するネットワークバウンドなタスク。2つ目は、yesコマンドを用いたCPUバウンドなタスクです。

補足として、厳密にはVM間通信はI/Oではないのですが、VMから見ればほとんど同じ、かつ外乱が少ないというメリットがあるので、今回実験に採用しました。また、誤差を減らすためにpingのアプリケーションはLinux上でリアルタイムタスクとして作動させていて、DVFSは無効化しています。

（スライドを示して）結果がこちらです。この結果には、大きく3つの着眼点があります。まず、バックグラウンドがない時は、もちろん普通0.ホニャララミリセコンドくらいでpingができます。これはほとんどLatencyがないと言っていいと思います。一方、CPUバウンドのタスクが後ろで実行されている時も、BOOSTのお陰でLatencyが小さいと言えます。

さらにネットワークバウンドなバックグラウンドが動作している時も、meanの平均は小さいですがmaxは非常に悪化していることが観測されました。

Tail Latencyが悪化する原因と解決策

なぜTail Latencyが悪化しているのか。一番の問題は、BOOSTしたvCPU間の調停がないという点にあります。つまり、同じマシンに複数のI/OバウンドなVMが存在する場合にこの問題が起こり得ます。

Tail Latencyの大幅な悪化が観測されているわけですが、BOOSTで割り込んだたくさんのvCPUがOVERにならない程度に長い時間の処理を続けていることが原因です。

1つ目の単純な解決策として、タイムスライスを短くする。つまり、デフォルトのタイムスライスが長すぎることが元凶の1つと言えます。

一方、短いタイムスライスは相対的にContext Switchのコストが上がってしまうので、ここにはトレードオフの関係があると言えますが、タイムスライスを短くするのが無難です。ただちょっと限界があります。

もう1つの解決策が、バックグラウンドのVMに対してCapを設定することです。スライドで説明します。Capは、vCPUの1pCPUに対する実行可能時間（割合）の上限をパーセントで表記したものです。例を見ればわかると思います。

まず4つのpCPUがあるマシン上で、3つvCPUがあるVMを実行します。その状態でCap値を200パーセントで動作させると、最大で全体の50パーセント、つまり2分の1のpCPUを使用できます。

これは、このCap値200を4つのpCPU×100（100パーセント）、つまり4×100を400で割った2分の1の50パーセントという値が、全体の4つのpCPUを50パーセント使用できるという意味を持ちます。

参考までに、Capがない場合は最大で全体の75パーセントです。つまり、3つのvCPUが同時に割り当てられると、最大で全体の75パーセントのCPUを利用することができるということになり、結果として使用量に上限が設けられています。

この是非について議論する時に「Work Conservation」という性質を考えるとすごく見通しがよくなります。Work Conservationは、一般にidleなCPUがある時に、ほかのCPUで実行待ちのタスク、つまりこの場合はvCPUがないという性質ですが、平たくいうと無駄がありません。

Cap値を設けるメリットとしてCPUの空きが保証されますが、Work Conservationが満たされないので無駄が発生してしまうというデメリットもあります。ここにもトレードオフがあります。

Capを設定することで、どれくらいLatencyが改善するのかを示したグラフです。先ほどの結果で示したデフォルトの設定が、この一番左のグラフです。タイムスライスを5ミリセカンドにしたり、バックグラウンドタスクに対するCapを設けたりすると、このようにTail Latencyが大幅に改善されることがわかります。以上がCreditスケジューラの説明です。

変動タイムスライスでProportional share schedulingを実現するCredit2スケジューラ

次に、Credit2スケジューラの話をします。Credit2スケジューラは、Xenのバージョン4.8からサポートが開始されて、4.12からデフォルト化されているはず。Wikipediaは2017年くらいで更新が止まっていて「Credit2 is not in use by default.」と書いてありますが、ほぼ間違いなく今がデフォルトです。

このCredit2スケジューラの特徴を一言でいうと、変動タイムスライスでProportional Shareなスケジューリングを実現しています。つまり、タイムスライスは実行時間に応じて計算される動的な値です。

Credit2スケジューラも、先ほどと同様にCreditというweightに応じて消費される実行時間、同じような概念を使いますが、先ほどとは異なり、UNDERやOVERというものは直接存在しません。Creditスケジューラは、よりLatencyを抑えたいシステム向きのスケジューラです。

Credit2スケジューラのアルゴリズム

（スライドを示して）基本的なアルゴリズムはこのようになっています。すべてのvCPUに同様のCreditを配布したのち、Credit最大のvCPUを、あるアルゴリズムに基づいた時間で実行します。そして、実行した分のCreditを消費してRunqをソートし、Credit最大のvCPUを実行するというループを、Creditが正のvCPUがなくなるまで実行します。

タイムスライスの決定アルゴリズムについてです。Runqに他の実行待ちのvCPUがある場合は、実行予定（Creditが最大のvCPU）のCreditの値から次に大きなCreditの値を引きます。そして、この値を時間に変換します。Runqに他の実行待ちCPUがない場合は、単純にこの2つ目をゼロとして扱います。この値は、次のCapやRate Limitという最短実行時間の概念を使って調整します。

この実行時間分のCreditの消費は、（スライドを示して）この枠で囲った式で消費Credit量が計算されます。基本原理としては、大きなWeightを持つほどCreditの減りが遅く、最大Weightを持つvCPUは1ナノセコンドで1Creditを消費します。

参考までに、Creditスケジューラは時間に応じた消費Credit量はすべてVM共通で、Creditの分配量のみが異なっていました。

I/Oが発生した時はどうなるか

さらに、Event（I/O）が発生した時のvCPUですが、Credit2はBOOSTという機能がない代わりに、Eventが発生したvCPUがRunqに突っ込まれてCredit順にソートされて、最大Creditを持つvCPUを実行するという、先ほどと同じアルゴリズムが走ります。この操作をtickleといいます。

このアルゴリズムの気持ちなのですが、基本的にこのI/OバウンドなVMは待ち時間が多いのでCreditが残っていないことが想定されます。つまりCreditが大きいです。

結果的にEvent発生VMがかなり優先されたスケジューリングが行われます。しかし、複数のスケジュールが同時にI/Oしている状況に対してもCreditという値で実際にその優先度が数値化されているので、先ほどのようなI/Oがたくさん起きる環境でも対応しやすいという特徴があります。

（スライドを示して）実際にCredit2スケジューラの性能を評価してみました。これを見ればわかりますが、Tailの悪化がかなり抑制されています。絶対時間で見ると、だいたいTailで2ミリセコンドくらいかかっていることがわかります。

これは、先ほどのパラメーター調整をしたCreditスケジューラの値ですね。単純にTailの比較をしてもあまり意味がありませんが、おおよその数値としてTailが5から10ミリセコンドくらいあるのに対して、ここは最大でも2ミリセコンドくらいになっています。しかも、特にパラメーターを設定せずデフォルトでこうなっているので、かなり優秀なスケジューラと言えるのではないかと思います。

以上が今回の内容です。スケジューラの説明をすると言いつつ、ロードバランシング、スケーラビリティ、Realtime系のスケジューラについてはまったく触れていないので、また機会があれば話そうと思います。

まとめ

まとめに入ります。このLTではXenのスケジューラの主要な2つを説明しました。1つ目がCreditスケジューラで、固定タイムスライスでProportional Shareという特徴があります。I/O Latencyを削減するためにBOOSTという機能を使っていましたが、複数のBOOSTが起こる環境ではLatencyが大きくなるという問題がありました。

Credit2スケジューラは、変動タイムスライス、Proportional Shareなスケジューリングをして、Latencyの観点ではCreditスケジューラよりも性能が改善していることがわかりました。

発表は以上です。ありがとうございました。