REAL-TIME SYSTEMS TECHNOLOGY

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

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOSの授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校コンピュータサイエンス学部2021年の世界大学学術ランキングで20位)で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発
  • プログラミング歴15年以上,習得している言語: C/C++Solidity,Java,Python,Ruby,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開

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

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

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

こういった私から学べます. 前回を読んでいない方はこちらからどうぞ. リアルタイムシステムの記事一覧はこちらからどうぞ. 目次1 Rate Monotonic(RM)スケジューリング2 RMの最適性の ...

続きを見る

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

リアルタイムシステム
元東大教員から学ぶリアルタイムシステム

こういった私から学べます. リアルタイムシステムとは,決められた時間(デッドライン)までに処理を完了しなければならない性質をもつシステムのことです. リアルタイムシステムは,ロボット,自動車や航空機な ...

続きを見る

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)\)で実行します(下図).

Interval of Continuous Utilization in EDF Schedule before Deadline Miss

時刻\(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\)610
\(\tau_2\)515

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

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社で自分に合うスクールを見つけましょう.後悔はさせません!

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

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

こういった私から学べます. 前回を読んでいない方はこちらからどうぞ. リアルタイムシステムの記事一覧はこちらからどうぞ. 目次1 Deadline Monotonic(DM)スケジューリング2 DMの ...

続きを見る

-REAL-TIME SYSTEMS, TECHNOLOGY
-, , , , , , , , , , , , , , , , , , , , , , , , ,