連載
» 2007年09月26日 04時33分 UPDATE

仮想マシンモニタ Xen 3.0解読室:sedfスケジューラの実装を理解する【前編】 (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 図1 周期と割り当て時間

基本方針の動作例

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

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

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

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

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

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

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

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

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


関連キーワード

CPU | Xen | アルゴリズム | Linux | カーネル


       1|2|3 次のページへ

Copyright© 2017 ITmedia, Inc. All Rights Reserved.

ピックアップコンテンツ

- PR -

注目のテーマ

マーケット解説

- PR -