【第8回】元東大教員から学ぶリアルタイムシステム「Earliest Deadline Firstスケジューリング」

こういった私から学べます．

前回を読んでいない方はこちらからどうぞ．

リアルタイムシステムの記事一覧はこちらからどうぞ．

リアルタイムシステムで使われているリアルタイムOSは，主にC言語で書かれています．

私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．

私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！

独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！

Earliest Deadline First（EDF）スケジューリング

Earliest Deadline First（EDF）スケジューリングは，絶対デッドラインの早いタスクに高い優先度を割り当てる動的スケジューリングです．

RMスケジューリングと同様に，EDFスケジューリングもLiuとLaylandが提案しました．

EDFは代表的なリアルタイムスケジューリングで，LinuxにもSCHED_DEADLINEとして実装されています．

つまり，LiuとLaylandがリアルタイムスケジューリングの研究の歴史を作った創始者です！

周期タスク\(\tau_i\)の\(j\)番目のジョブの絶対デッドライン\(\tau_{i,j}\)は以下になります．

$$d_{i,j} = \Phi_i + (j - 1) T_i + D_i$$

RMとは異なり，EDFは動的に優先度を割り当てます．

現在実行しているタスクより早い絶対デッドラインのジョブがリリースされた時，そのタスクはプリエンプションされます．

EDFは，タスクが周期的に実行するという明確な想定はありません．

なので，EDFは周期タスクと非周期タスクを同様にスケジュールすることができます．

このEDFの特徴が，周期の短いタスクに高い優先度を割り当てるRMとの大きな違いです．

EDFのスケジュール可能性解析

第5回リアルタイムシステムで紹介した想定A1，A2，A3，A4において，EDFのスケジュール可能性解析はCPU利用率により検証することができます．

※想定A1，A2，A3，A4は以下になります．

A1：周期タスク\(\tau_i\)のジョブは一定の周期で起動する．2つの連続した起動の間の間隔\(T_i\)はタスクの周期である．

A2：全ての周期タスク\(\tau_i\)のジョブは同じ最悪実行時間\(C_i\)を持つ．

A3：全ての周期タスク\(\tau_i\)のジョブは同じ相対デッドライン\(D_i\)を持ち，周期\(T_i\)と同じである．

A4：タスクセット\(\Gamma\)にある全ての周期タスクは独立している．すなわち，タスク間の依存関係やリソース制約がない．

https://hiroyukichishiro.com/real-time-systems-vol5/

このケースでは，スケジュール可能上限は\(1\)になります．

したがって，CPU利用率が100%のタスクセットはスケジュール可能です．

具体的には，以下の定理が証明されています．

定理8.1：周期タスクセットは以下の条件を満たす場合（if）かつ，この場合においてのみ（only if）EDFでスケジュール可能になる（if and only if）．

$$\sum_{i=1}^n \frac{C_i}{T_i} \leq 1$$

証明：まず，「この場合においてのみ（only if）」を証明します．

タスクセットの合計CPU利用率が100%を越える場合（\(U > 1\)），スケジュール不可能であることを示します．

実際，\(T=T_1 T_2 ... T_n\)を置くことで，\(T\)にある全てのタスクが必要な最悪実行時間は下式で算出できます．

$$\sum_{i=1}^n \frac{T}{T_i} C_i = UT$$

もし\(U > 1\)ならば，全てのタスクが必要な最悪実行時間\(UT\)は利用可能なCPU時間\(T\)を越えてしまいますので，タスクセットがスケジュール不可能なことは明らかです．

次に，「条件を満たす場合（if）」を背理法により証明します．

条件\(U \leq 1\)を満たす場合にスケジュール不可能なタスクセットがあると想定します．

\(t_2\)がデッドラインミスをした最初の時刻，区間\([t_1,t_2)\)が連続して実行する最長の間隔とします．

時刻\(t_2\)までは，\(t_2\)以下の絶対デッドラインを持つジョブのみを区間\([t_1,t_2)\)で実行します（下図）．

時刻\(t_1\)は，あるジョブのリリース時刻でなければならないことに注意して下さい．

\(C_p (t_1, t_2)\)を区間\([t_1,t_2)\)で周期タスクが必要な最悪実行時間と置くと，下式で算出できます．

$$C_p (t_1, t_2) = \sum_{r_k \geq t_1, d_k \leq t_2} C_k = \sum_{i=1}^n \left\lfloor \frac{t_2 - t_1}{T_i} \right\rfloor C_i$$

以下のことに気づきます．

$$C_p (t_1, t_2) = \sum_{i=1}^n \left\lfloor \frac{t_2 - t_1}{T_i} \right\rfloor C_i \leq \sum_{i=1}^n \frac{t_2 - t_1}{T_i} C_i = (t_2 - t_1) U$$

時刻\(t_2\)でデッドラインミスするので，最悪実行時間\(C_p (t_1, t_2)\)は利用可能なCPU時間\((t_2 - t_1)\)より長くなければなりません．

なので，下式の関係になります．

$$(t_2 - t_1) < C_p (t_1, t_2) \leq (t_2 - t_1) U$$

\(U > 1\)なので，矛盾を導きました．□

EDFのスケジュール例

周期タスクセットのスケジュール例を紹介します．

タスクセットのパラメータは下表になります．

\(\tau_i\)：タスク	\(C_i\)：最悪実行時間	\(T_i\)：周期
\(\tau_1\)	6	10
\(\tau_2\)	5	15

RMとEDFのスケジュール例は下図になります．

タスクセットのCPU利用率は以下になります．

$$U = \frac{6}{10} + \frac{5}{15} = \frac{14}{15} \simeq 0.933$$

CPU時間の93.3%は周期タスクを実行し，残りの6.7%はCPUのアイドル時間になります．

\(U > 2 (\sqrt{2} - 1) \simeq 0.828\)なので，タスクセットのRMにおけるスケジュール可能性は保証できませんが，EDFにおけるスケジュール可能性は保証できます．

確かに，RMはスケジュールが失敗して，時刻\(t=15\)でデッドラインミスしていることがわかります．

※区間\([16, 17)\)でタスク\(\tau_2\)は実行していますが，デッドライン時刻である\(t=15\)までに終了していないことに注意して下さい．

また，EDFは全てのタスクがデッドラインまでに実行が終了してスケジュールが成功していることがわかります．

RMとEDFの違いは，スケジュール中のプリエンプション数にあります．

RMでは，タスク\(\tau_1\)の\(2\)番目のジョブ\(\tau_{1,2}\)が時刻\(t=10\)で起動した時，タスク\(\tau_2\)の\(1\)番目のジョブ\(\tau_{2,1}\)をプリエンプションしています．

これに対して，EDFでは1度もプリエンプションしていません．

EDFの方がプリエンプション数が少ない理由は，動的優先度割り当ての直接的な結果になります．

つまり，タスクの周期とは独立して，絶対デッドラインの早いタスクに高い優先度を割り当てるからです．

まとめ

今回は，Earliest Deadline First（EDF）スケジューリングを解説しました．

具体的には，以下の内容を解説しました．

• EDFは絶対デッドラインの早いタスクに高い優先度を割り当て
• EDFは最適な動的優先度スケジューリング
• EDFのスケジュール可能上限\(U_{lub} = 1\)

EDFはRMと同様に代表的なリアルタイムスケジューリングなので是非きちんと理解しましょう！

次回は相対デッドラインが周期より短いDeadline Monotonic（DM）スケジューリングを説明します．

リアルタイムシステムで使われているリアルタイムOSは，主にC言語で書かれています．

私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．

私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！

独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！

次回はこちらからどうぞ．