REAL-TIME SYSTEMS TECHNOLOGY

【第10回】元東大教員から学ぶリアルタイムシステム「相対デッドラインが周期より短いEDFスケジューリング」

2020年9月30日

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOS(Linuxカーネル)の授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校(UNC)コンピュータサイエンス学部で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発.
  • プログラミング歴15年以上,習得している言語: C/C++PythonSolidity/Vyper,Java,Ruby,Go,Rust,D,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開
  • 2020年1月~現在はアメリカのノースカロライナ州チャペルヒルにあるGuarantee Happiness LLCのCTOとしてECサイト開発やWeb/SNSマーケティングの業務.2022年6月~現在はアメリカのノースカロライナ州チャペルヒルにあるJapanese Tar Heel, Inc.のCEO兼CTO.
  • 最近は自然言語処理AIイーサリアムに関する有益な情報発信に従事.
    • (AI全般を含む)自然言語処理AIの論文の日本語訳や,AIチャットボット(ChatGPT,Auto-GPT,Gemini(旧Bard)など)の記事を50本以上執筆.アメリカのサンフランシスコ(広義のシリコンバレー)の会社でプロンプトエンジニア・マネージャー・Quality Assurance(QA)の業務委託の経験あり.
    • (スマートコントラクトのプログラミングを含む)イーサリアムや仮想通貨全般の記事を200本以上執筆.イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり.

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

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

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

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

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

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

友だち追加

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

相対デッドラインが周期より短いEarliest Deadline First(EDF)スケジューリング

Earliest Deadline First(EDF)スケジューリングで相対デッドラインが周期より短い場合は,Processor Demandによりスケジュール可能性を解析することができます.

Processor DemandはBaruahらにより提案されました.

Processor Demand

一般的には,区間\([t_1, t_2)\)におけるタスク\(\tau_i\)のProcessor Demandは処理時間\(g_i(t_1, t_2)\)になります.

処理時間\(g_i(t_1, t_2)\)は,タスク\(\tau_i\)が区間\([t_1, t_2)\)に起動して,この区間内に終了するために必要な長さで,下式になります.

$$g_i(t_1, t_2) = \sum_{r_{i,k} \geq t_1, \ d_{i,k} \leq t_2} C_i$$

全体のタスクセットにおいて,\([t_1, t_2)\)のProcessor Demandは下式になります.

$$g(t_1, t_2) = \sum_{i=1}^n g_i(t_1, t_2)$$

次に,タスクセットのスケジュール可能性は,あらゆる区間においてProcessor DemandがCPUの利用可能な時間を超えない場合においてのみ保証されます.

すなわち,下式を満たす場合においてのみ保証されます.

$$\forall t_1, t_2 \ \ \ g(t_1, t_2) \leq (t_2 - t_1)$$

Jobs of Blue Rectangles are Those Contributing to Processor Demand in [t1, t2)
青色の長方形がProcessor Demandに含まれるジョブです.

上図によると,区間\([t_1, t_2)\)におけるタスク\(\tau_i\)のジョブ数は下式になります.

$$\eta_i (t_1, t_2) = \max \left\{ 0, \left\lfloor \frac{t_2 + T_i - D_i - \Phi_i}{T_i} \right\rfloor - \left\lceil \frac{t_1 - \Phi_i}{T_i} \right\rceil \right\}$$

区間\([t_1, t_2)\)におけるProcessor Demandは下式になります.

$$g(t_1, t_2) = \sum_{i=1}^n \eta_i (t_1, t_2) C_i$$

もし相対デッドラインが周期より短いか同じで,周期タスクが全て時刻\(t=0\)に同時に起動する場合(全てのタスクの位相\(\Phi_i = 0\)の場合),区間\([0, L)\)におけるProcessor Demandに含まれるジョブ数は下式になります.

$$\eta_i (0, L) = \left\lfloor \frac{L + T_i - D_i}{T_i} \right\rfloor $$

区間\([0, L)\)におけるProcessor Demandは下式になります.

$$g(0, L) = \sum_{i=1}^n \left\lfloor \frac{L + T_i - D_i}{T_i} \right\rfloor C_i $$

関数\(g(0, L)\)はDemand Bound Function(DBF)と呼ばれます.

$${\sf dbf} (t) \stackrel{\mathrm{def}}{=} \sum_{i=1}^n \left\lfloor \frac{t + T_i - D_i}{T_i} \right\rfloor C_i $$

相対デッドラインが周期より短いか同じ場合の周期タスクセットは,以下の条件を満たす場合においてのみEDFでスケジュール可能です.

$$\forall t > 0 \ \ \ {\sf dbf}(t) \leq t \tag{10.1}$$

タスクの相対デッドラインが周期と同じ場合,Processor Demandによるスケジュール可能性判定テストは,スケジュール可能上限の1(100%)になります.

この結果は,JeffayとStoneにより以下の定理で証明されています.

定理10.1:相対デッドラインが周期と同じタスクセットは以下の条件を満たす場合においてのみスケジュール可能である.

$$\forall L > 0 \ \ \ \sum_{i=1}^n \left\lfloor \frac{L}{T_i} \right\rfloor C_i \leq L \tag{10.2}$$

証明:この定理は,LiuとLaylandのスケジュール可能上限と同様であることを示すことで証明できます.

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

式\((10.3) \Rightarrow (10.2)\)は,\(U \leq 1\)の場合,全ての\(L (L \geq 0)\)において以下を満たすことで証明できました.

$$ L \geq UL = \sum_{i=1}^n \left( \frac{L}{T_i} \right) C_i \geq \sum_{i=1}^n \left\lfloor \frac{L}{T_i} \right\rfloor C_i $$

式\((10.3) \Leftarrow (10.2)\)の証明は,対偶である式\(\lnot (10.3) \Rightarrow \lnot (10.2)\)を示します.

すなわち,\(U > 1\)かつ\(L \geq 0\)で式\((10.2)\)が成立しないことを示します.

\(U > 1\)の場合,\( L = H = \operatorname{lcm}(T_1, ..., T_n)\)により下式になるので,対偶を証明できました.

$$H < HU = \sum_{i=1}^n \left( \frac{H}{T_i} \right) C_i = \sum_{i=1}^n \left\lfloor \frac{H}{T_i} \right\rfloor C_i$$

テスト区間の削減によるProcessor Demandの改良

式\((10.1)\)のスケジュール可能性判定テストは,検証しなければならない間隔の数を減らすことで簡略化できます.

まずは,以下の2つを調査します.

  1. もしタスクが周期的で時刻\(t=0\)で同時に起動する場合,スケジュールはハイパーピリオド\(H\)毎に繰り返します.
    この場合,式\((10.1)\)は\(L\)の値が\(H\)以下の場合のみ検証する必要があります.
  2. \(g(0, L)\)は,\(L\)が大きくなって絶対デッドライン\(d_k\)以上になるが,次の絶対デッドライン\(d_{k+1}\)未満になるステップ関数である.
    すなわち,\(L = d_k\)において\(g(0, L) < L\)が成立する場合,全ての\(L\)において\(d_k \leq L < d_{k+1}\)も成立する.
    結果として,式\((10.1)\)は\(L\)の値が絶対デッドラインと同じであるかどうかのみ検証すれば良いことがわかります.

テストポイントの数は下式により減らすことができます.

$$\left\lfloor \frac{L + T_i - D_i}{T_i} \right\rfloor \leq \left( \frac{L + T_i - D_i}{T_i} \right)$$

また,\(G(0, L)\)を定義します.

$$G(0, L) = \sum_{i=1}^n \frac{L + T_i - D_i}{T_i} C_i = \sum_{i=1}^n \frac{T_i - D_i}{T_i} C_i + \frac{L}{T_i} C_i$$

\(G(0, L)\)により,下式の関係になります.

$$\forall L > 0, \ \ \ g(0, L) \leq G(0, L)$$

ここで\(G(0, L)\)は下式のように表せます.

$$G(0, L) = \sum_{i=1}^n (T_i - D_i) U_i + LU$$

Maximum Value of L

上図によると,\(G(0, L)\)は勾配\(U\)による直線とする\(L\)の関数になります.

もし\(U < 1\)の場合,どの\(G(0, L) = L\)においても\(L=L^*\)となる値が存在します.

明らかに,全ての\(L \geq L^*\)において,\(g(0, L) \leq G(0, L) \leq L\)になりますので,スケジュール可能性が保証できます.

結果として,\(L \geq L^*\)において,式\((10.1)\)を検証する必要はありません.

\(L^*\)の値は\(G(0, L^*)\)になる時刻です.すなわち,下式が成立する場合です.

$$\sum_{i=1}^n (T_i - D_i) U_i + L^* U = L^*$$

上式は下式に変形できます.

$$L^* = \frac{\sum_{i=1}^n (T_i - D_i) U_i}{1 - U} $$

タスクセットは少なくとも最大相対デッドライン\(D_{max}\)までにテストしなければならないことを考慮すると,式\((10.1)\)は以下の定理に組み合わせることができます.

定理10.2:相対デッドラインが周期より短いか同じ周期タスクセットは\(U < 1\)かつ以下の条件を満たした場合においてのみEDFでスケジュール可能になる.

$$\forall t \in {\cal D} \ \ \ {\sf dbf}(t) \leq t \tag{10.4}$$

ここで,\(\cal D\)は下式になります.

$${\cal D} = \{ d_k : d_k \leq \min[H, \max(D_{max}, L^*)] \}$$

\(L^*\)は下式になります.

$$L^* = \frac{\sum_{i=1}^n (T_i - D_i) U_i}{1 - U} $$

\(\tau_i\):タスク\(C_i\):最悪実行時間\(D_i\):相対デッドライン\(T_i\):周期
\(\tau_1\)246
\(\tau_2\)258
\(\tau_3\)379

上表のタスクセットを使ってProcessor Demandを説明します.

これらの相対デッドラインが周期より短い3つの周期タスクはEDFでスケジュールできることが保証されています.

パラメータ\(U\),\(L^*\),\(H\)は下式で算出できます.

$$U = \frac{2}{6} + \frac{2}{8} + \frac{3}{9} = \frac{11}{12} $$

$$L^* = \frac{\sum_{i=1}^n (T_i - D_i) U_i}{1 - U} = 25$$

$$H = \operatorname{lcm}(6, 8, 9) = 72$$

式\((10.4)\)は25未満のあらゆるデッドラインでテストしなければなりません.

チェックポイントのセットは\({\cal D} = \{ 4, 5, 7, 10, 13, 16, 21, 22\}\)になります.

下表にテストの結果を示します.

\(L\)\(g(0, L)\)テストの結果
42OK
54OK
77OK
109OK
1311OK
1616OK
2118OK
2220OK

下図に上記のタスクセットをEDFでスケジュールする例を示します.

Schedule Produced by EDF

まとめ

今回は,相対デッドラインが周期より短いEarliest Deadline First(EDF)スケジューリングを解説しました.

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

  • Processor Demand
  • テスト区間の削減によるProcessor Demandの改良

次回はRMとEDFの比較を説明します.

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

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

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

友だち追加

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

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

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