sedfスケジューラの実装を理解する【前編】：仮想マシンモニタ Xen 3.0解読室（1/3 ページ）

現在のXenでは、2種類のスケジューリング方針を提供しています。ここでは標準スケジューリング方式であるsedfスケジューラの実装について解説していきます。

[高橋浩和（VA Linux Systems Japan），ITmedia]

　現在のXenでは、2種類のスケジューリング方針を提供しています。これらは同時に利用できず、Xenの起動パラメータによって、利用するスケジューリング方針を選択しなければなりません。これまで解説してきたドメインスケジューリングに関するトピックの最終回として、標準スケジューリング方式であるsedfスケジューラの実装について解説していきます。

sedfスケジューラの方針

　sedfは「Simple Early Deadline First scheduler」の略です。sedfスケジューラはその名前が示すように、非常に単純なリアルタイム（実時間）スケジューリング方式を採用しています。

スケジューリング基本方針

　sedfスケジューラは、次の基本方針でドメインをスケジューリングします。

1-1：各ドメインの仮想CPUに対し、周期的に一定時間の実行権を与える*（この時間を、割り当て時間と呼ぶことにします。図1）

1-2：デッドライン（現在の周期の終了）に近い仮想CPUから実行する。デッドラインとしては、それぞれの仮想CPUの周期の終了時刻を用いる

1-3：仮想CPUが与えられた時間を使い切るか、もしくは自ら実行権を手放すとその周期での実行権を失う

　要するに、「一番早く処理を完了させねばならないものから順番に実行する」という単純なアルゴリズムで、ドメインの仮想CPUに実行権を与えています。このアルゴリズムは非常に単純ですが、その単純さに比べて効果が大きく、ほとんどの場合に期待通りうまくスケジューリングされます。

図1　周期と割り当て時間

基本方針の動作例

　一例を挙げます。現在、仮想CPU A、仮想CPU B、仮想CPU Cがスケジューリング対象になっており、仮想CPU D、仮想CPU Eは割り当て時間を使い切っているとします（図2）。ドメインスケジューラは、スケジューリング対象の仮想CPUの中で、最もデッドラインが近い仮想CPU Aに実行権を与えます。仮想CPU Aの実行が終了した場合、次に動作する候補は、2番目にデッドラインが近い仮想CPU Bとなります。

図2　割り当て時間とドメインスケジューリング（1）

　ここで仮想CPU Aの実行が終了する前に、仮想CPU Dの次の周期が始まったとしましょう。仮想CPU Dはスケジューリング対象に加えられます。仮想CPU Dのデッドラインは、仮想CPU Bよりも早く来るので、次に動作する候補は仮想CPU Dに代わります（図3）。

図3　割り当て時間とドメインスケジューリング（2）

　仮想CPU Aが割り当て時間を使い切ると、スケジューリング対象から外れます。ドメインスケジューラは、次の候補である仮想CPU Dに実行権を与えます。仮想CPU Aは次の周期が来るまで、スケジューリング対象になりません（図4）。

図4　割り当て時間とドメインスケジューリング（3）

このページで出てきた専門用語

周期的に一定時間の実行権を与える

周期や割り当て時間は、ドメインごとに別々の値を指定できる。