【第23回】元東大教員から学ぶリアルタイムシステム「Earliest Deadline Late Server」

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

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

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

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

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

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

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

Earliest Deadline Late （EDL）Server

Total Bandwidth Server（TBS）はとてもシンプルなので，非周期タスクの応答性が高くなります．

しかし，より応答性を高くするためには，より複雑な方法で達成することができます．

例えば，前回のTBSのスケジュール例では，システムのスケジュール可能性を低下させずに，2番目と3番目の非周期タスクが到着したらすぐに実行できるかもしれません．

非周期タスクが到着した時，実行可能状態の周期タスクに十分な余裕時間があれば安全にプリエンプションできます．

非周期タスクを実行するために周期タスクの利用可能なスラックを利用することは，Earliest Deadline Late （EDL）Serverの適用が基本理念にあります．

EDL Serverは，固定優先度の非周期サーバのSlack Stealingの動的優先度バージョンになります．

EDLの定義は，ChettoとChettoにより提案された結果を利用しています．（※2人のChettoの名字は同じですが，名前は異なります．）

この論文では，EDFの2つの補完的なバージョンのEDSとEDLを提案しています．（Sはas Soon as possible，Lはas Late as possibleの意味です．）

EDSでは実行可能状態のタスクはできるだけ早く実行し，EDLではできるだけ遅く実行します．

EDLの重要な性質は，あらゆる区間\([0, t)\)で利用可能な最長アイドル時間を保証することです．

この結果は，ハード非周期タスクの受け入れテストや，ソフト非周期タスクの最適な機構に使われます．

EDL Serverの表記を単純化するために，スケジューリングを\(A\)，タスクセットを\(J\)とした場合，利用可能関数\(\omega_J^A (t)\)は以下の表記になります．

\begin{equation}
\omega_J^A (t) = \left \{
\begin{array}{l}
1\ \ \ {\rm もしCPUが時刻tでアイドルの場合} \\
0\ \ \ {\rm そうでない場合}
\end{array}
\right.
\end{equation}

区間\([t_1, t_2)\)における\(\omega_J^A (t)\)の積分は\(\Omega_J^A (t_1, t_2)\)と表記し，特定の区間における合計アイドル時間になります．

前回のTBSの図における関数\(\omega_J^A (t)\)は下図になります．

上図の最適性の結果は以下の定理で証明されています．

定理23.1：\(J\)をあらゆる非周期タスクセット，\(A\)をあらゆるプリエンプティブなスケジューリングとした場合，あらゆる時刻\(t\)において以下が成立する（証明は省略）．

$$\Omega_J^{EDL} (0, t) \geq \Omega_J^A (0, t)$$

この結果は，EDLスケジューラのアイドル時間を利用した最適な非周期サーバを開発できます．

具体的には，周期タスクセット\(J\)において，関数\(\omega_J^A \)（ハイパーピリオド\( H =\mathrm{lcm}(T_1, ..., T_n) \)）は，2つの配列で表現されます．

最初の配列の\(\cal{E} = (e_0, e_1, ..., e_p)\) はアイドル時間が発生した時刻を表し，2番目の配列の \(\cal{D}=(\Delta_0, \Delta_1, ..., \Delta_p)\) はこれらのアイドル時間の長さを表します．

上図の例におけるこれらの2つの配列は下表に示します．

アイドル時間は周期タスクのジョブのリリース後にのみ発生することに注意して下さい．

\(i\)	0	1	2	3
\(e_i\)	0	8	12	18
\(\Delta_i\)	3	1	1	1

EDL Serverの基本的なアイデアは，できるだけ早く非周期タスクを実行するために，EDLスケジューラのアイドル時間を利用することです．

システムに非周期タスクがない時，周期タスクはEDFでスケジュールされます．

新しい非周期タスクがシステムに到着した時はいつでも（非周期タスクが実行可能状態でない時も含む），現在の周期タスクセットに適用するEDLスケジューラのアイドル時間を算出し，非周期タスクをスケジュールするために利用されます．

下図にEDL Serverの機構の例を示します．

ここで，4ユニット時間を持つ非周期タスクが時刻8に到着します．

EDLスケジューラのアイドル時間は現在の周期タスクを利用して再算出されます（上図の上部）．

非周期タスクは算出したアイドル時間によりスケジュールされます（上図の下部）．

非周期サーバは非周期タスクにバンド幅\(1-U_p\)を自動的に割り当てることに注意して下さい．

この手法の応答時間は最適なので，これ以上は良くなりません．

EDLスケジューラのアイドル時間を算出する手順は，ChettoとChettoにより提案されていますが，ここでは紹介しません．

しかし，全てのアイドル時間を再算出する必要はありませんが，現在実行可能状態の周期タスクの中で最も遅い絶対デッドラインを持つタスクの絶対デッドラインよりも前の時間だけを再算出する必要があることが興味深いです．

EDL Serverの最悪計算量は\(\mathcal{O}(nN)\)になります．

ここで，\(n\)は周期タスクの個数，\(N\)はハイパーピリオドで発生する明確な周期タスクの個数になります．

最悪の場合，\(N\)は非常に大きくなり，EDL Serverはあまり実用的ではないかもしれません．

EDL Serverは非周期タスクの応答時間を下限を実現し，ほぼ最適な実装可能なアルゴリズムになります．

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

EDL Serverのスケジュール可能性解析はとても簡単です．

実際，全ての非周期タスクが特別なEDFスケジューラのアイドル時間を利用して実行されます．

周期タスクセットのスケジュール可能性は低下しないことを以下の定理で証明します．

定理23.2：CPU利用率が\(U_p\)の\(n\)個の周期タスクセットとEDL Server（動作は周期タスクセットの特徴に強く依存）において，全体のタスクセットは以下の条件を満たす場合においてのみスケジュール可能である．

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

条件\(U_p \leq 1\)はEDFにおける周期タスクセットのスケジュール可能性を保証するための十分条件なので，EDFの特別な実装であるEDLにおいて十分条件であることを示します．

EDLは非周期タスクの特定の順序に依存して，EDFとEDLのどちらかの実装により周期タスクをスケジュールします．

非周期タスクが実行可能状態の時，周期タスクのあらかじめ算出したアイドル時間の間スケジュールされます．

両方の場合で，周期タスクセットの即時性は影響しないので，デッドラインはミスしません．

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

もし周期タスクセットがEDL Serverでスケジュール可能な場合，EDL Serverなしでもまたスケジュール可能になるので，\(U_p \leq 1\)が成立します．□

最後に，EDL Serverが最適であることを示します．

すなわち，EDL Serverにおける非周期タスクの応答時間が最短になります．

補題23.3：\(A\)をあらゆるオンラインプリエンプティブスケジューリング，\(\tau\)を周期タスクセット，\(J_i\)を非周期タスクとする．もし\(f_{\tau \cup \{J_i\}}^A (J_i)\)を，\(\tau \cup {J_i}\) が\(A\)をスケジュールする時の\(J_i\)の終了時刻とした場合，以下が成立する．

$$ f_{\tau \cup \{J_i\}}^{\rm EDL\ Server} (J_i) \leq f_{\tau \cup \{J_i\}}^A (J_i)$$

証明：\(J_i\)が時刻\(t\)に到着したと仮定した場合，\(\tau (t)\)を現在の実行可能状態の周期タスクのジョブ（実行可能状態で終了していない）と未来の周期タスクのジョブのセットとします．

新しいタスク\(J_i\)は，\(\tau (t)\)にあるタスクと一緒にスケジュールします．

具体的には，\(A\)における\(\tau \cup {J_i}\)のスケジュール\(\sigma\)を考慮します．

\(A'\)を\(\sigma\)における同じ時刻で\(\tau (t)\)におけるタスクをスケジュールするもう一つのスケジューリングとし，\(\sigma '\)を対応するスケジュールとします．

\(J_i\)は\(\sigma '\)のアイドル時間で実行します．

定理23.1を\(t\)に翻訳した時間軸の原点に適用することで（\(A\)はオンラインなので実行可能），各々の\(t' \geq t\)において以下が成立します．

$$\Omega_{\tau (t)}^{EDL} (t, t') \geq \Omega_{\tau (t)}^{A'} (t, t')$$

非周期タスクがある時，EDL ServerはEDLのアイドル時間の正確に実行します．

なので，以下が成立します．

$$\Omega_{\tau (t)}^{EDL} (t, f_{\tau \cup \{J_i\}}^{\rm EDL\ Server} (J_i)) \geq \Omega_{\tau (t)}^{A'} (t, f_{\tau \cup \{J_i\}}^{\rm EDL\ Server} (J_i))$$

したがって，以下が成立します．

$$ f_{\tau \cup \{J_i\}}^{\rm EDL} (J_i) \leq f_{\tau \cup \{J_i\}}^A (J_i)$$

すなわち，EDL Serverにおいて，\(J_i\)は\(A\)より遅く終了しないことを証明しました．□

まとめ

今回は，Earliest Deadline Late （EDL）Serverについて紹介しました．

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

• EDL Serverの特徴
• EDL Serverのスケジュール可能性解析

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

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

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

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

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