期限が早い順にスケジュール

最も早い期限優先( EDF ) または残り時間最小は、リアルタイム オペレーティング システムでプロセスを優先キューに配置するために使用される動的優先度スケジューリング アルゴリズムです。スケジューリング イベント (タスクの終了、新しいタスクのリリースなど) が発生するたびに、キュー内で期限に最も近いプロセスが検索されます。このプロセスが次に実行がスケジュールされます。

EDF は、次の意味で、プリエンプティブ ユニプロセッサ上の最適なスケジューリング アルゴリズムです。到着時間、実行要件、期限によって特徴付けられる独立したジョブのコレクションを、すべてのジョブが期限までに完了するように (任意のアルゴリズムによって) スケジュールできる場合、EDF はこのジョブのコレクションを、すべてのジョブが期限までに完了するようにスケジュールします。

期限が周期に等しい周期的プロセスをスケジュールすると、EDF の利用率は 100% になります。したがって、EDF のスケジュール可能性テスト^[1]は次のようになります。

${\displaystyle U=\sum _{i=1}^{n}{\frac {C_{i}}{T_{i}}}\leq 1,}$

ここで、はプロセスの最悪ケースの計算時間であり、はそれぞれの到着間隔（相対的な期限に等しいと仮定）である。^[2]${\displaystyle \left\{C_{i}\right\}}$${\displaystyle n}$${\displaystyle \left\{T_{i}\right\}}$

つまり、EDF は、CPU の合計使用率が 100% を超えない限り、すべての期限が守られることを保証できます。レートモノトニック スケジューリングなどの固定優先度スケジューリング手法と比較すると、EDF は、より高い負荷でもシステム内のすべての期限を保証できます。

期限を期間としてスケジュール可能性テストの式を使用することに注意してください。期限が期間より短い場合は、状況が異なります。次に例を示します。4 つの定期的なタスクをスケジュールする必要があります。各タスクは TaskNo( 計算時間、相対期限、期間) として表されます。これらは、T0(5,13,​​20)、T1(3,7,11)、T2(4,6,10)、および T3(1,1,20) です。このタスク グループは、使用率が 1.0 以下であることを満たしており、使用率は 5/20+3/11+4/10+1/20 = 0.97 (2 桁を四捨五入) として計算されますが、まだスケジュールできません。詳細については、EDF スケジュール失敗の図を確認してください。

EDF は非プリエンプティブな単一プロセッサ上でも最適なスケジューリングアルゴリズム ですが、挿入されたアイドル時間を許可しないスケジューリングアルゴリズムのクラスに限られます。期限が周期に等しい周期プロセスをスケジュールする場合、EDF の十分な（ただし必須ではない）スケジュール可能性テストは次のようになります。^[3]

${\displaystyle U=\sum _{i=1}^{n}{\frac {C_{i}}{T_{i}}}\leq {1-p},}$

ここで、p は非プリエンプションのペナルティを表し、max / minで与えられます。この係数を小さく保つことができれば、実装オーバーヘッドが低いため、非プリエンプティブ EDF が有益になります。 ${\displaystyle \left\{C_{i}\right\}}$ ${\displaystyle \left\{T_{i}\right\}}$

ただし、システムが過負荷になると、期限に間に合わない一連のプロセスは、ほとんど予測不可能になります (これは、過負荷が発生する正確な期限と時間の関数になります)。これは、リアルタイム システムの設計者にとって大きなデメリットです。また、このアルゴリズムはハードウェアに実装するのが難しく、期限をさまざまな範囲で表すという難しい問題があります (期限は、スケジュールに使用されるクロックの粒度よりも正確にすることはできません)。現在を基準とした将来の期限を計算するためにモジュラー演算を使用する場合、将来の相対期限を格納するフィールドには、少なくとも ((「期間」{完了までの最長予想時間} * 2) + 「現在」) の値が収まる必要があります。したがって、EDF は、産業用リアルタイム コンピュータ システムではあまり使用されません。

代わりに、ほとんどのリアルタイム コンピュータ システムでは、固定優先度スケジューリング(通常はレート単調スケジューリング) が使用されます。固定優先度を使用すると、過負荷状態によって優先度の低いプロセスが期限に間に合わなくなる一方で、優先度の最も高いプロセスは期限に間に合うことが容易に予測できます。

リアルタイム コンピューティングにおける EDF スケジューリングを扱った重要な研究が行われています。EDF 内のプロセスの最悪ケースの応答時間を計算したり、周期的なプロセス以外の種類のプロセスを処理したり、サーバーを使用して過負荷を調整したりすることが可能になっています。

プリエンプティブ ユニプロセッサでスケジュールされた 3 つの定期プロセスについて考えます。実行時間と期間は次の表のようになります。

この例では、時間単位はスケジュール可能なタイムスライスと考えることができます。期限は、各周期プロセスがその期間内に完了する必要があることです。

タイミング図では、列は右に行くほど時間が長くなるタイムスライスを表し、すべてのプロセスはタイムスライス 0 で期間を開始します。タイミング図の青と白の交互の網掛けは各プロセスの期間を示し、色が変わるところに期限があります。

EDF によってスケジュールされる最初のプロセスは P2 です。これは、その期間が最も短く、期限が最も早いためです。同様に、P2 が完了すると、P1 がスケジュールされ、その後に P3 がスケジュールされます。

タイム スライス 5 では、P2 と P3 の両方に同じ期限があり、タイム スライス 10 の前に完了する必要があるため、EDF はどちらか一方をスケジュールできます。

利用方法は次のとおりです。

${\displaystyle \left({\frac {1}{8}}+{\frac {2}{5}}+{\frac {4}{10}}\right)=\left({\frac {37}{40}}\right)=0.925={\mathbf {92.5\%} }}$

期間の最小公倍数は 40なので、スケジューリング パターンは 40 タイム スライスごとに繰り返すことができます。ただし、その 40 タイム スライスのうち、P1、P2、または P3 によって使用されるのは 37 タイム スライスのみです。使用率は 92.5% で、100% を超えないため、システムは EDF でスケジュール可能です。

EDF スケジューリングでは、望ましくない期限の入れ替えが発生する場合があります。プロセスは、期限が早い別のプロセスのために事前にスケジュール解除されるのを防ぐために、クリティカル セクション内で共有リソースを使用する場合があります。その場合、リソースを待機している他のプロセスの中で最も早い期限を実行中のプロセスに割り当てることがスケジューラにとって重要になります。そうしないと、期限が早いプロセスが期限に間に合わない可能性があります。

これは、クリティカル セクションを実行しているプロセスがクリティカル セクションを完了して終了するまでの時間がかなり長く、共有リソースの解放が遅れる場合に特に重要です。ただし、期限が早いがクリティカル リソースを共有していない他のプロセスに優先される可能性があります。期限交換の危険性は、固定優先度のプリエンプティブ スケジューリングを使用する場合の優先度の逆転に似ています。

準備完了キュー内での期限の検索を高速化するために、キューのエントリは期限に従ってソートされます。新しいプロセスまたは定期的なプロセスに新しい期限が与えられると、そのプロセスは、期限が遅い最初のプロセスの前に挿入されます。このようにして、期限が最も早いプロセスは常にキューの先頭になります。

期限を最早優先とするスケジュール ポリシーと期限の超過を伴う単一サーバー キューの挙動に関する高トラフィック分析では、^[4]プロセスには期限があり、期限が経過するまでしか処理されません。期限が経過したために処理されなかった残りの作業として定義される「期限を超過した作業」の割合は、重要なパフォーマンス測定基準です。

固定優先度プリエンプティブ スケジューリング(FPS)の実装は、EDF のような動的優先度スケジューラよりも簡単であることが一般的に認められています。ただし、固定優先度での最適スケジューリングの最大使用率 (各スレッドの優先度はレート単調スケジューリングによって指定) を比較すると、EDF は 100% に達する可能性がありますが、レート単調スケジューリングの理論上の最大値は約 69% です。さらに、周期的および/または散発的なタスクに対する EDF 実装 (完全プリエンプティブまたは限定的/非プリエンプティブ) の最悪のオーバーヘッドは、デジタル検索木を使用して、特定のシステム (期限と期間をエンコードするため) に必要な最大の時間表現の対数に比例させることができます。^[5]固定の 32 ビット時間表現を使用する組み込みシステムなどの実際のケースでは、この実装を使用して、システム タスクの数に依存しない小さな固定定数時間でスケジューリングの決定を行うことができます。このような状況では、実験では、（比較的）大きなカーディナリティのタスクセットであっても、EDFとFPSのオーバーヘッドにほとんど違いがないことがわかりました。^[5]

EDFはタスクの周期性について特別な仮定をしていないことに注意してください。そのため、EDFは周期的タスクだけでなく非周期的タスクのスケジュールにも使用できます。^[2]

EDF 実装は商用のリアルタイム カーネルでは一般的ではありませんが、EDF を実装しているオープン ソース カーネルとリアルタイム カーネルのリンクをいくつか示します。

• SHARK EDFスケジューリングとリソース予約スケジューリングアルゴリズムのさまざまなバージョンを実装したSHArK RTOS
• ERIKA Enterprise ERIKA Enterprise は、 OSEK APIに類似した API を備えた小型マイクロコントローラ向けに最適化された EDF の実装を提供します。
• Everyman Kernel Everyman Kernel は、ユーザーの構成に応じて、EDF または Deadline Monotonic スケジューリングのいずれかを実装します。
• MaRTE OS MaRTE OS は Ada アプリケーションのランタイムとして機能し、EDF を含む幅広いスケジューリング アルゴリズムを実装します。
• AQuoSAプロジェクトは、 Linux カーネルに EDF スケジューリング機能を追加してプロセス スケジューラを強化するものです。スケジューリングのタイミングは、上記のハード リアルタイム オペレーティング システムほど正確ではありませんが、予測可能性を大幅に向上させるには十分な精度であり、マルチメディア アプリケーションのリアルタイム要件を満たします。AQuoSA は、適切に設計されたアクセス制御モデルを使用して、システム上の権限のないユーザーに制御された方法でリアルタイム スケジューリング機能を提供する数少ないプロジェクトの 1 つです。^[6]
• Linuxカーネルには、SCHED DEADLINEリリース 3.14 以降で利用可能な、 という名前の最も早い期限優先実装があります。
• IRMOSヨーロッパプロジェクトのコンテキストで開発されたリアルタイム スケジューラは、Linux カーネル用のマルチプロセッサ リアルタイム スケジューラで、複雑なマルチスレッド ソフトウェア コンポーネントや仮想マシン全体に対する時間的分離と QoS 保証のプロビジョニングに特に適しています。たとえば、Linux をホスト OS として、KVM をハイパーバイザとして使用する場合、IRMOS を使用して個々の VM にスケジュール保証を提供し、同時にそれらのパフォーマンスを分離して、望ましくない時間的干渉を回避することができます。IRMOS は、EDF/FP を組み合わせた階層型スケジューラを備えています。外側のレベルでは、使用可能な CPU 上にパーティション化された EDF スケジューラがあります。ただし、予約はマルチ CPU であり、内側のレベルでは、各外側の EDF 予約にアタッチされたスレッド (および/またはプロセス) をスケジュールするために、マルチプロセッサ上のグローバル FP が使用されます。この主題に関する一般的な概要と短いチュートリアルについては、lwn.net のこの記事も参照してください。
• Xen には以前から EDF スケジューラが搭載されています。マニュアル ページには簡単な説明が記載されています。
• ベル研究所のPlan 9 OSには、EDFと共有リソースの期限継承を組み合わせた軽量のリアルタイムスケジューリングプロトコルであるEDFIが組み込まれています。^[7]
• RTEMS: EDFスケジューラはバージョン4.11で利用可能になります。RTEMS SuperCore
• Litmus-RT は、マルチプロセッサのリアルタイム スケジューリングと同期に重点を置いた Linux カーネルのリアルタイム拡張機能です。そのリアルタイム アルゴリズム セットには、Partitioned-EDF、Global-EDF、および Clustered-EDF スケジューラが含まれます。
• XNU クラッチ スケジューラ 2018 年現在、Apple の XNU カーネルは、応答性の向上を目的として、クラッチ スケジューラに EDF アルゴリズムを実装しています。

• 動的優先度スケジューリング
• 最も早い適格な仮想締め切りの最初のスケジュール
• スタックリソースポリシー