Earliest deadline first scheduling

ウィキペディア

Earliest Deadline First

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/09/03 13:44 UTC 版)

Earliest Deadline First (EDF) とは、リアルタイムオペレーティングシステムで使用される動的スケジューリング規則の一種である。プロセスは優先度付きキューに置かれる。スケジューリングイベントが発生すると(タスク終了、新規タスク生成など)、そのキューを探索して最も実行期限(デッドライン)が近いプロセスを選ぶ。そのプロセスが次に実行すべきものとしてスケジュールされる。

特徴

周期的に実行すべきプロセスのデッドラインはその周期に等しく、EDFによるCPU使用率の限界は100%である。すなわちEDFはCPU使用率の合計が100%を超えない限り全てのデッドラインを守ることを保証できる。従って、レートモノトニックスケジューリングのような固定優先度スケジューリングに比較して、EDFはより高負荷な環境でも全てのデッドラインを守ることができる。

しかし、システムが過負荷状態のとき、デッドラインを守れなくなるプロセスを予測できない(デッドラインと過負荷の発生時刻に依存する)。この欠点はリアルタイムシステム設計においては重大である。またこのアルゴリズムを実装するのも難しく、デッドラインを数バイトで表すにはやや技巧を必要とする(デッドラインは数ミリ秒かもしれないし数百分かもしれない)。このため、EDFは実際の産業用リアルタイムシステムではあまり使われない。

EDFスケジューリングに関しては多くの研究がなされている。EDFでプロセスの応答時間の最悪ケースを計算することができ、周期的プロセス以外にも適用可能である。ただし、マルチプロセッシングシステムではEDFはうまく機能しない。

例

3つの周期的プロセスをEDFでスケジュールすると想定する。以下の受け入れ試験によってデッドラインが全て満たされることを示す。

プロセス	実行時間	周期
P1	1	8
P2	2	5
P3	4	10

なお、実行時間も周期も同じ単位の時間(例えば10ミリ秒)であり、P1は8単位周期(80ミリ秒)に起動し、1単位(10ミリ秒)だけ動作することを示している。CPU使用率は以下のようになる:

${\frac {1}{8}}+{\frac {2}{5}}+{\frac {4}{10}}=0.925$

任意の個数のプロセスを動作させる際の論理的なCPU使用率の限界は100%であり、従ってこのシステムはスケジュール可能である。