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

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

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

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

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

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

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

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

Total Bandwidth Server（TBS）

Sporadic Server（SS）の特徴を見ると，非周期サーバが長い周期を持つ場合，非周期タスクの実行が大幅に遅延することがわかります．

この理由は，周期が長いと非周期サーバはいつも長い絶対デッドラインでスケジュールされるからです．

非周期タスクの応答時間を減らすためには，主に2つの方法があります．

1つ目は，SSを短い周期にすることです．

しかし，この方法は実行時のオーバヘッドを増加します．

非周期サーバのCPU利用率を一定に保つためには，非周期サーバの容量を比例して減らさなければなりませんが，高い頻度で容量を補給すると，周期タスクとのコンテキストスイッチの回数が増えてしまいます．

2つ目の方法は，可能な限り早い絶対デッドラインを各々の非周期タスクに割り当てることです．

この割り当ては，全体の非周期タスクのCPU利用率が最大値\(U_s\)を超えないようにしなければなりません．

この方法は，Total Bandwidth Server（TBS）と呼び，SpuriとButtazzoらにより提案されたシンプルかつ効率的な非周期サーバです．

この非周期サーバの名前は，各々の時刻で非周期タスクがシステムに到着する時に，可能であればいつでも非周期サーバの全体のバンド幅がすぐに割り当てられるという事実から由来します．

具体的には，\(k\)番目の非周期タスクが時刻\(t=r_k\)で到着した時，その絶対デッドライン\(d_k\)は以下になります．

$$d_k = \max(r_k, d_{k-1}) + \frac{C_k}{U_s} $$

ここで，\(C_k\)は非周期タスクの最悪実行時間，\(U_s\)は非周期サーバのCPU利用率（バンド幅）になります．

また，\(d_0=0\)になります．

絶対デッドラインの割り当てルールでは，前の非周期タスクに割り当てられるバンド幅は，絶対デッドライン\(d_{k-1}\)を考慮することに注意して下さい．

絶対デッドラインが割り当てられた時，非周期タスクはシステムのレディキューに挿入され，他の周期タスクのジョブのようにEDFでスケジュールされます．

結果として，TBSの実装のオーバヘッドは実質的に無視できます．

上図に，2つの周期タスク（周期\(T_1=6\)，\(T_2=8\)，最悪実行時間\(C_1=3\)，\(C_2=2\)）とTBS（CPU利用率\(U_s=1-U_p=0.25\)）をEDFでスケジュールする例を示します．

• 時刻3：最初の非周期タスクが到着し，絶対デッドライン\(d_1 = r_1 + C_1 / U_s = 3 + 1 / 0.25 = 7\) で実行します．\(d_1\)はシステムで最も早い絶対デッドラインなので，非周期タスクはすぐに実行します．
• 時刻9：同様に，2番目の非周期タスクが到着し，絶対デッドライン\(d_2 = r_2 + C_2 / U_s = 17\) になりますが，すぐに実行しません．
  周期タスク\(\tau_2\)が実行状態で，絶対デッドラインが16と早いからです．
• 時刻14：3番目の非周期タスクが到着し，絶対デッドライン\(d_3 = \max(r_3, d_2) + C_3 / U_s = 21\) になりますが，すぐには実行しません．
  周期タスク\(\tau_1\)が実行状態で，絶対デッドラインが18と早いからです．

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

TBSが存在する場合のEDFでスケジュールされる周期タスクセットのスケジュール可能性を判定するために，TBSにより実行される非周期タスクのCPU利用率は\(U_s\)を超えないことを示します．

補題22.1：各々の区間\([t1, t2)\)において，もし\(C_{ape}\)が\(t_1\)以降に到着し，時刻\(t_2\)以下の絶対デッドラインで実行する非周期タスクにより要求される合計実行時間の場合，以下が成立します．

$$C_{ape} \leq (t_2 - t_1)U_s$$

証明：\(C_{ape}\)の定義は以下になります．

$$C_{ape} = \sum_{t_1 \leq r_k,\ d_k \leq t_2} C_k$$

TBSの絶対デッドラインの割り当てルールにより，インデックス\(k_1\)と\(k_2\)の2つの非周期タスクが存在しなければなりません．

$$\sum_{t_1 \leq r_k,\ d_k \leq t_2} C_k = \sum_{k=k_1}^{k_2} C_k$$

したがって，以下が導けます．

\begin{eqnarray}
C_{ape} &=& \sum_{k=k_1}^{k_2} C_k \\
&=& \sum_{k=k_1}^{k_2} [d_k - \max(r_k, d_{k-1})] U_s \\
&\leq& [d_{k_2} - \max(r_{k_1}, d_{{k_1}-1})] U_s \\
&\leq& (t_2 - t_1) U_s
\end{eqnarray}

□

これから，TBSのスケジュール可能性の主要部分を証明します．

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

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

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

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

さらに，ある時点\(t' (t' < t)\)から，時刻\(t'\)以降で実行可能状態になるか，時刻\(t\)までの絶対デッドラインを持つタスクのジョブのみ実行します．

\(C\)をこれらのジョブにより要求される合計の最悪実行時間とします．

時刻\(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 \frac{t - t'}{T_i} C_i + (t - t') U_s \\
&\leq& (t - t')(U_p + U_s) \\
\end{eqnarray}

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

$$U_p + U_s > 1$$

矛盾を導きました．

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

もし非周期タスクが周期的にシステムに到着する場合，周期\(T_s\)と最悪実行時間\(C_s = T_s U_s\)を持つので，非周期サーバは周期\(T_s\)と最悪実行時間\(C_s\)を持つ周期タスクのように振る舞い，全体のタスクセットの合計CPU利用率は\(U_p + U_s\)になります．

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

まとめ

今回は，Total Bandwidth Server（TBS）について紹介しました．

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

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

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

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

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

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

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