タスク スケジューラに取り組んでおり、EDF スケジューリングを使用したいと考えています。スケジュールする必要があるタスク セットには、期限がその期間と等しいタスクのみが含まれており、タスクは定期的にスケジュールする必要があります。私が抱えている問題は、実行を開始するとタスクを中断できないことです。
EDF が最適なスケジューリング アルゴリズムであるのは、タスクが単一のプロセッサでプリエンプティブにスケジュールされる場合のみであることを知っているので、タスク セットを使用してタスク セットをスケジュールできることを確認するために、タスクに課す可能性のあるテストまたは制約があるかどうか疑問に思っていました。非プリエンプティブ EDF。
どんな助けでも大歓迎です。ありがとうございました
タスクiの実行時間をe_i、その周期をP_i、e_m=max_i(e_i)とする。次に、タスク セットが実行可能であることを保証できます。
U = sum_i ((e_i + e_m)/P_i) <= 1
正当化: Liu/Layland 基準 sum_i(e_1/P_i) <= 1 はご存知でしょう。プリアム化不可能なタスクは、優先度の高いタスクをブロックしていると見なすことができます。ブロッキング時間は、追加の実行時間と見なすことができます。最悪のケースは、最も長い (優先度の低い) タスクが開始された直後に、優先度の高いタスクが準備完了になる場合です。
編集: 上記のアドホックな条件を導き出しました。しかし、それだけで十分です。より正確な分析のために、あるタスクは、より大きな相対的な期限を持つ別のタスクによってのみブロックされる可能性があることを考慮する必要があります。つまり、使用されたモデルに関して、より長い期間のタスク、cfeg、[JL00]*、定理 6.18 .
したがって、期間が P_1 < P_2 < ... < P_n のタスク T_1、...、T_n で構成されるタスク セットの場合、次のように計算できます。
L'_i = e_i + max_{j=i...n}(e_j).
次に、タスクセットは実行可能です
sum_i L'_i/P_i <= 1.
[JL00]、ノンプリエンプティブ クリティカル セクションに関するセクション 8.3 を参照してください。
* [JL00] Jane WS Liu、リアルタイム システム、プレンティス ホール、2000 年