【第21回】元東大教員から学ぶリアルタイムシステム「Dynamic Sporadic Server」

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

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

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

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

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

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

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

Dynamic Sporadic Server（DSS）

Dynamic Sporadic Server（DSS）はSpuriとButtazzoらにより提案された非周期サーバで，Sporadic Server（SS）を拡張して動的優先度スケジューリング（EDF）に適用可能にしたものです．

他の非周期サーバと同様に，DSSは周期\(T_s\)と容量\(C_s\)を持ちます．

しかし，他の非周期サーバとは異なり，各々の周期の最初で容量は最大値まで補給せず，消費された時にのみ補給されます．

補給が行われる時刻は，補給ルールにより選択され，システムがCPU利用率をフル活用することを許可します．

従来のSSとDSSの主な違いは，非周期サーバに割り当てる優先度の方法です．

SSはRM（すなわち，周期\(T_s\)）による固定優先度で割り当てるのに対して，DSSは適切な絶対デッドラインにより動的優先度を割り当てます．

絶対デッドラインの割り当てと容量の補給は，以下のルールにより定義されます．

• 非周期サーバを生成した時，容量\(C_s\)は最大値に初期化されます．
• 次の補給時刻\(RT\)と現在の非周期サーバの絶対デッドライン\(d_s\)は，\(C_s > 0\)かつ非周期タスクがある場合にすぐに設定されます．
  もし\(t_A\)が補給時刻の場合，\(RT=d_s=t_A+T_s\)になります．
• 補給時刻\(RT\)で行う補給量\(RA\)は，最後の非周期タスクが終了するか，\(C_s\)が空になった時に算出されます．
  もし\(t_I\)が補給時刻の場合，補給量\(RA\)は区間\([t_A, t_I)\)内で消費される容量と同じになります．

上図に，2つの周期タスク（周期\(T_1=8\)と\(T_2=12\)，最悪実行時間\(C_1=2\)と\(C_2=3\)）とDSS（周期\(T_s=6\)，容量\(C_s=3\)）がEDFでスケジュールする例を示します．

• 時刻0：非周期サーバの容量はフル（\(C_s=3\)）に初期化されます．非周期タスクがないので，CPUは最も早い絶対デッドラインを持つタスク\(\tau_1\)に割り当てます．
• 時刻3：最悪実行時間が2の非周期タスクが到着します．\(C_s > 0\)なので，最初の補給時刻かつ非周期サーバの絶対デッドラインは，\(RT_1=d_s=3+T_s=9\)に設定されます．
  \(d_s\)が最も早い絶対デッドラインなので，DSSはシステムの最高優先度タスクになり，非周期タスクが終了するまで実行します．
• 時刻5：非周期タスクが終了し，他の非周期がないので，2ユニット時間の補給は時刻\(RT_1=9\) で行うようにスケジュールします．
• 時刻6：2番目の非周期タスクが到着します．\(C_s > 0\)なので，次の補給時刻と新しい非周期サーバの絶対デッドラインは\(RT_2=d_s=6+T_s=12\)に設定されます．
  非周期サーバがシステムの最高優先度タスクになり（タスク間のタイブレーク方式は非周期サーバの方を優先），非周期タスクはすぐに実行します．
  しかし，容量はユニット時間1しかありません．
• 時刻7：容量が空になります．したがって，1ユニット時間の補給は時刻\(RT_2=12\)にスケジュールされ，非周期タスクは\(C_s\)が0より大きくなる時刻\(t=9\)まで遅延します．
• 時刻9：次の補給時刻と新しい非周期サーバの絶対デッドラインは，\(RT_3=d_s=9+T_s=15\) に設定されます．
  従来通り，DSSは最高優先度になるので，非周期タスクはすぐに実行され，時刻\(t=10\)で終了します．
  1ユニット時間の補給は時刻\(RT_3=15\)に設定されます．
• 時刻\(t=14\)：最後の2つの非周期タスクが同じ絶対デッドライン\(d_s=20\)で実行される時，非周期サーバの容量は0より大きいので，全ての非周期タスクは同じ絶対デッドラインで実行されます．

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

DSSのスケジュール可能上限を証明するために，非周期サーバは周期\(T_s\)，最悪実行時間\(C_s\)を持つ周期タスクのように振る舞うことを示します．

上図のように，区間\([t_1, t_2)\)においてタスク\(\tau_i\)が時刻\(t_1\)でリリースした場合，時刻\(t_2\)以下の絶対デッドラインのジョブをEDFでスケジュールされる算出時間は下式になります．

$$C_i (t_1, t_2) \leq \left\lfloor \frac{t_2 - t_1}{T_i} \right\rfloor C_i$$

以下の補題は同じ性質がDSS向けに正しいことを示します．

補題21.1：各々の区間\([t_1, t_2)\)において，\(t_1\)はDSSが実行可能状態になる時刻とする場合（すなわち，非周期タスクが到着し，他の非周期タスクが実行していない場合），区間\([t_1, t_2)\)でDSSにより実行される非周期タスクの最長実行時間は，以下の関係を満たす．

$$C_{ape} \leq \left\lfloor \frac{t_2 - t_1}{T_s} \right\rfloor C_s$$

証明：補給はいつも消費された時間と同じなので，非周期サーバの容量は，いつでも初期値以下になります．

また，補給ポリシーは，消費された容量が\(T_s\)ユニット時間より前や非周期サーバが実行可能状態になった後に回収できないことを設定しています．

これは，時刻\(t_1\)から非周期サーバが実行可能状態になり，最長で\(C_s\)時間を間隔\(T_s\)で消費することを意味します．

したがって，補題は証明されました．□

DSSは周期タスクのように振る舞うので，以下の定理はCPUを100%利用可能なことを示します．

定理21.2：合計CPU利用率が\(U_p\)の\(n\)個の周期タスクセットと，CPU利用率が\(U_s\)のDSSにおいて，全体のタスクセットは以下の条件を満たす場合においてのみスケジュール可能である．

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

\(U_p + U_s \leq 1\)を想定し，時刻\(t\)でオーバーフローした（\(U_p + U_s > 1\)になった）と仮定します．

そのオーバーフローは，連続したCPU利用率の周期により先行します．

さらに，ある時点\(t' (t' < t)\)から，時刻\(t'\)以降で実行可能状態になるか，時刻\(t\)までの絶対デッドラインを持つタスクのジョブのみ実行します．（非周期サーバはこれらのタスクの一つになるかもしれません．）

時刻\(t\)でオーバーフローするので，\(t - t' < C\)が成立しなければなりません．

また，下式が成立します．

\begin{eqnarray}
C &\leq& \sum_{i=1}^n \left\lfloor \frac{t - t'}{T_i} \right\rfloor C_i + C_{ape} \\
&\leq& \sum_{i=1}^n \left\lfloor \frac{t - t'}{T_i} \right\rfloor C_i + \left\lfloor \frac{t - t'}{T_s} \right\rfloor C_s \\
&\leq& \sum_{i=1}^n \frac{t - t'}{T_i} C_i + \frac{t - t'}{T_s} C_s \\
&\leq& (t - t')(U_p + U_s) \\
\end{eqnarray}

上式から下式が導きます．

$$U_p + U_s > 1$$

矛盾を導きました．

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

DSSは周期\(T_s\)と最悪実行時間\(C_s\)を持つ周期タスクのように振る舞うので，非周期サーバのCPU利用率は\(U_s=C_s/T_s\)になり，全体の合計のCPU利用率は\(U_p+U_s\)になります．

したがって，もし全体のタスクセットがスケジュール可能な場合，定理8.1のEDFのスケジュール可能上限から\(U_p+U_s \leq 1\)であることを証明できます．□

まとめ

今回は，Dynamic Sporadic Server（DSS）について紹介しました．

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

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

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

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

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

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

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