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

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

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

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

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

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

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

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

Sporadic Server（SS）

Sporadic Server（SS）は，Spruntらにより提案された非周期サーバです．

SSは周期タスクセットのスケジュール可能上限を低下させることなく，非周期タスクの応答時間を向上させることができます．

DSのように，SSは非周期タスクを処理するために高優先度で生成され，非周期タスクが到着するまで高優先度レベルでサーバの容量を保持します．

しかし，SSは容量の補給方法に関してDSと異なります．

DSとPEは各々のサーバの周期の最初に満タンまで容量を周期的に補給しますが，SSは非周期タスクの実行までに消費された後にのみ容量を補給します．

SSにより利用される補給方法の記述を簡略化するために，以下の用語を定義します．

\(P_{exe}\)	現在実行しているタスクの優先度レベル
\(P_s\)	SSに関連する優先度レベル
アクティブ	\(P_{exe} \geq P_s\)の場合
アイドル	\(P_{exe} < P_s\)の場合
RT	SSの容量が補給される時刻
RA	RTで容量に追加される補給量

これらの用語を利用することで，非周期タスクにより消費される容量\(C_s\)は以下のルールで補給されます．

• 補給時刻RTはSSがアクティブかつ\(C_s > 0\)の場合，すぐに設定されます．
  \(t_A\)を補給時刻とした場合，RTの値は\(t_A\)とサーバの周期の和（\(RT=t_a+T_s\)）になります．
• 補給時刻RTで補給される補給量RAは，SSがアイドルまたは\(C_s\)が空の場合に算出されます．
  \(t_I\)を補給時刻とした場合，RAの値は区間\([t_A, t_I)\)内で消費される容量と同じになります．

\(\tau_i\)：タスク	\(C_i\)：最悪実行時間	\(T_i\)：周期
\(\tau_1\)	1	10
\(\tau_2\)	4	15
\(\tau_s\)（非周期タスク）	5	10

上図にSSの中間優先度の例を示します．

補給ルールの理解を簡単にするために，SSがアクティブの間隔を示します．

• 時刻\(t=0\)：最高優先度タスク\(\tau_1\)がスケジュールされ，SSがアクティブになります．
  \(C_s > 0\)なので，補給時刻は時刻\(RT_1=t+T_s=10\)に設定されます．
• 時刻\(t=1\)：タスク\(\tau_1\)が終了し，非周期タスクがないので，SSはアイドルになります．
  容量が区間\([0, 1)\)で消費されなかったので，時刻\(RT_1=10 (RA_1 = 0)\)で補給が行われないことに注意して下さい．
• 時刻\(t=4\)：最初の非周期タスクが到着し，\(C_s>0\)なので，SSはアクティブになり，非周期タスクはすぐに実行します．
  結果として，補給時刻は\(RT_2=t+T_s=14\)に設定されます．
• 時刻\(t=5\)：非周期タスクはタスク\(\tau_1\)にプリエンプションされます．
• 時刻\(t=6\)：非周期タスクが復帰して実行します．
• 時刻\(t=7\)：非周期タスクが終了します．
  時刻\(RT_2\)で補給される補給量は区間\([4, 7)\)で消費される容量（\(RA_2=2\)）と同じになります．
  プリエンプションされる区間の間では，SSがアクティブであることに注意して下さい．
  たとえSSが非周期タスクの不連続なサービスを提供する場合でも，SSは単一の補給が行われることを許可します．
• 時刻\(t=8\)：SSはまたアクティブになり，新しい補給時刻が\(RT_3=t+T_s=18\)になります．
• 時刻\(t=11\)：SSはアイドルになり，補給時刻\(RT_3\)で補給される補給量は\(RA_3=2\)になります．

\(\tau_i\)：タスク	\(C_i\)：最悪実行時間	\(T_i\)：周期
\(\tau_1\)	3	10
\(\tau_2\)	4	15
\(\tau_s\)（非周期タスク）	2	8

上図にSSが最高優先度タスクの非周期タスクの例を示します．

ここで，最初の非周期タスクは時刻\(t=2\)で到着し，全てのサーバの容量を消費します．

したがって，補給量\(RA_1=2\)は補給時刻\(RT_1=10\)で設定されます．

2番目の非周期タスクは\(C_s=0\)の時に到着します．

このケースでは，補給時刻\(RT_2\)は容量が0より大きくなるとすぐに設定されます．

時刻\(t=10\)で容量が0より大きくなるので，次の補給時刻は\(RT_2=18\)に設定されます．

対応する補給量は2番目の非周期タスクが完了し，\(RA_2=2\)と同じ時に確定します．

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

SSは，標準の周期タスクの実行が守っている基本的な想定の一つを違反します．

この想定は周期タスクが最高優先度タスクで実行可能状態の場合，そのタスクは実行しなければならないことを要求します．

実際，DSのようにSSは実行を遅延し，非周期タスクがない場合は容量を保ちます．

しかし，SSで利用される補給ルールはあらゆる遅延実行を補償し，スケジューリングの観点から，SSは周期\(T_s\)と最悪実行時間\(C_s\)の普通の周期タスクとして扱うことができます．

具体的には，以下の定理が証明されています．

定理16.1：タスク\(\tau_i\)を持つスケジュール可能な周期タスクセットは，もしタスク\(\tau_1\)が同じ周期と最悪実行時間を持つSSに置換された場合もまたスケジュール可能になります．

証明：あらゆるタスクのタイプで，SSは1つ以上の周期タスクと同等に実行することを示すことで，この定理を証明することができます．

\(t_A\)を\(C_s\)が満タンかつSSがアクティブになる時刻，\(t_I\)をSSがアイドルになる時刻とします．

\([t_A,t_I)\)はSSがアクティブの連続した区間になります．

区間\([t_A,t_I)\)におけるサーバの実行は以下の3つのケースの1つになります（下図）．

1. サーバの容量が消費されない．
2. サーバの容量が完全に消費された．
3. サーバの容量が部分的に消費された．

ケース1：もし\([t_A,t_I)\)で非周期タスクが到着しない場合，SSは容量を保持し，補給は時刻\(t_I+T_s\)より前に行われません．

非周期タスクに多くとも\(C_s\)が区間\([t_A,t_I+T_s)\)に実行されることを意味します．

したがって，SSはリリース時刻が\(t_A\)から\(t_I\)まで遅延した周期タスク\(\tau_s (C_s, T_s)\)と一致します．

RMの証明と同様に，周期タスクのリリースの遅延は他の周期タスクの応答時間を増やしませんので，このケースはスケジュール可能性を低下させません．

ケース2：もし\(C_s\)が区間\([t_A,t_I)\)で完全に消費された場合，\(C_s\)分の時間の補給は時刻\(t_A+T_s\)に置きます．

したがって，SSは，時刻\(t_A\)でリリースされる周期\(T_s\)と最悪実行時間\(C_s\)を持つ周期タスクのように振る舞います．

ケース3：もし\(C_s\)が区間\([t_A,t_I)\)で部分的に消費された場合，補給は時刻\(t_A+T_s\)で行われ，残りの容量は将来の非周期タスクのために保持されます．

このケースでは，非周期サーバの実行は2つの周期タスク\(\tau_x\)と\(\tau_y\)と同様です．

タスク\(\tau_x\)と\(\tau_y\)の周期が\(T_x=T_y=T_s\)，最悪実行時間が\(C_x=C_R\)と\(C_y=C_s-C_R\)，タスク\(\tau_x\)が時刻\(t_A\)，タスク\(\tau_y\)が時刻\(t_I\)でリリースします．

ケース1のように，タスク\(\tau_y\)の遅延はスケジュール可能性に影響しません．

あらゆるケースにおいて，SSのは1つ以上の周期タスク（周期\(T_s\)，合計の最悪実行時間\(C_s\)）として表されます．

なので，SSのCPU利用率は\(U_s=C_s/T_s\)になります．

したがって，スケジュール可能性の観点から，SSは同じCPU利用率を持つ周期タスクに置換することが可能になります．□

SSは普通の周期タスクのように振る舞うので，周期タスクセットはPSから派生するスケジュール可能性判定テストにより保証されます．

したがって，合計CPU利用率\(U_p\)を持つ\(n\)個の周期タスクセット\(\Gamma\)と，CPU利用率\(U_s\)を持つSSがある場合，以下の条件を満たす場合にRMでスケジュール可能になります．

$$U_p \leq n \left[ \left( \frac{2}{U_s+1} \right)^{1/n} - 1 \right] $$

\(n\)が大きくなる場合，\(\Gamma\)は以下の条件を満たす場合にスケジュール可能になります．

$$U_p \leq \ln{\left( \frac{2}{U_s+1} \right)}$$

Hyperbolic Boundを利用する場合，合計CPU利用率\(U_p\)の周期タスクセットは以下の条件を満たす場合にRM+SSでスケジュール可能になります．

$$P \stackrel{\mathrm{def}}{=} \prod_{i=1}^n (U_i + 1) \leq \left( \frac{2}{U_s + 1} \right) $$

SSの最大CPU利用率は以下になります．

$$U_{SS}^{max} = \frac{2 - P}{P} \tag{16.1} $$

ファーム非周期タスクを考慮する限り，SSのスケジュール可能性解析は簡単ではありません．

この理由として，一般的には，補給ルールによりサーバの容量を小さい部分にフラグメント（断片化）するからです．

結果として，非周期タスクの終了時刻の算出は，タスクのデッドラインまでに発生する全ての補給を追跡する必要があります．

まとめ

今回は，非周期サーバSporadic Server（SS）を紹介しました．

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

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

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

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

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

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

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