sedfスケジューラの実装を理解する【後編】仮想マシンモニタ Xen 3.0解読室(2/4 ページ)

» 2007年10月03日 01時45分 公開
[高橋浩和(VA Linux Systems Japan),ITmedia]

sedfスケジューラの実装をのぞいてみよう

リスト1

 ここまでの説明を前提知識として、sedfスケジューラのコードを読んでみましょう。まず、sedfスケジューラの中心機能となる再スケジューリング関数sedf_do_schedule()から見ていきます。

 sedf_do_schedule関数は、

  • 仮想CPU自ら実行権を手放したとき
  • 割り当て時間を使い切ったとき
  • プリエンプションが発生したとき

に呼び出されます。この関数は、現在実行中の仮想CPUに代わって、実行権を与えるべき仮想CPUを選び出します(リスト1)。sedf_do_schedule関数が最初に行うのは、現在実行中のドメイン(仮想CPU)をどうするかという判断です。

編集部注:リスト1には多くの注釈線が含まれているため、画像として用意しました。下記アイコンをクリックいただくことでご覧いただけます

現在実行中の仮想CPUを処理

 現在実行中の仮想CPUがアイドルドメインの仮想CPUであれば、runnableqキューに実行可能な仮想CPUが存在しないことを意味しています(A1)。この場合、まずwaitqキューに仮想CPUが存在しないか確認します。もしかするとwaitqキュー上には、次の周期に入りrunnableqキューへ移動できるようになった仮想CPUがあるかもしれないし、もしなくても、補償時間や有効利用時間を利用して動作しようとしている仮想CPUが存在するかもしれません。

 もし、現在実行中の仮想CPUが待機状態(もしくは中断状態)に遷移したのであれば、その状態を示すフラグを立てています(A2)。待機状態に遷移する場合、その時刻を記録しておきます(A3)

 また、もし現在実行中の仮想CPUが、補償時間もしくは有効利用時間を使って動作しているのであれば(A4)、extraqキュー(penaltyキュー、もしくはutilizationキュー)上で、仮想CPUを操作します(A5、desched_extra_dom関数)。現在実行中の仮想CPUがプリエンプトされた場合、つまり実行可能状態を継続している場合は、そのままextraqキューに残します。ただし、実行した分だけ実行優先度が下がるため、extraqキュー上で並べ替えを行います。待機状態になったときは、extraqキューおよびwaitqキューから、その仮想CPUを外してしまいます。

 あるいは、もし現在実行中の仮想CPUが、標準の割り当て時間を利用して動作していた場合は、runnableqキュー上で仮想CPUを操作します(A6、desched_edf_dom関数)。自ら実行権を譲った場合(do_yieldを呼び出したときなど)は、実行可能状態を維持しているため、そのままrunnableqキュー上に仮想CPUを残しておきます。

 実行割り当て時間を使い果たしたことによって本関数が呼び出されたときは、runnableqから外してwaitqキューにつなぎ直し、次の周期のデッドラインを設定します。現仮想CPUが待機状態になったために本関数が呼び出されたときは、runnableqキュー、waitqキューのどちらにもつなぎません。

実行権を与えるべき仮想CPUの選択

 現在実行中の仮想CPUの扱いを決定した後は、次に実行権を与えるべき仮想CPUを選び出します。

 まず、waitqキュー上に次の周期に入った仮想CPUがないか確認し(A7)、あればその仮想CPUをrunnableqキューにつなぎ直します。また同時に、割り当て時間を使い切った仮想CPUがrunnableqキュー上に残っていないか調べ、残っていれば、この仮想CPUをwaitqキューに移動します。

  • runnableqキュー上に仮想CPUが存在する場合

 runnableqキュー上に仮想CPUが存在すれば(A8)、キューの先頭の仮想CPUを選択します(A9)。これは、最もデッドラインに近い(周期切れに近い)仮想CPUです。このとき、ドメインスケジューラを自動的に呼び出すべき時刻も求めます。

 このとき、waitqキュー上に仮想CPUがなければ(A10)、新しく選択した仮想CPU(A9)が、割り当て時間を使い果たす予定時刻を選択します(A12)。waitqキュー上に仮想CPUがあれば(A10)、新しく選択した仮想CPU(A9)が割り当て時間を使い果たす予定時刻と、次にwaitqキューからrunnableqキューに移ってくる仮想CPUの時刻とを比較し、近い方の時刻を選択します(A11)

 sedf_do_schedule関数の呼び出し元である__enter_scheduler関数は、ここで設定された時刻に再スケジューリングを行います。

  • runnableキュー上に仮想CPUが存在しない場合

 runnableキュー上に仮想CPUが存在しなければ、割り当て時間を使い切った仮想CPUから、実行すべき仮想CPUを選び出します。このとき、もしwaitqキュー上に1つも仮想CPUがなければ(A13)、実行可能な仮想CPUは存在しないという意味です。その場合、アイドルドメインの仮想CPUを選択します(A15)。また、もしwaitqキュー上に仮想CPUが存在すれば、動作可能な仮想CPUが、extraq上に存在するかもしれません。この場合は、extraqキューを、penaltyキュー、utilizationキューの順で走査し、動作可能な仮想CPUを見つけ出します(A14、sedf_do_extra_schedule関数)。仮想CPUがextraqキュー上にも存在しなければ、アイドルドメインの仮想CPUが選択されます。

Copyright © ITmedia, Inc. All Rights Reserved.

注目のテーマ