【第6回】元東大教員から学ぶリアルタイムシステム「CPU利用率の深掘りとタイムラインスケジューリング」

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

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

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

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

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

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

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

CPU利用率の深掘り

今回はCPU利用率を深掘りします．

前回の復習ですが，タスク\(\tau_i\)のCPU利用率は\(U_i=C_i/T_i\)，タスクセット\(\Gamma\)にあるn個のタスクの合計CPU利用率は以下になります．

$$U=\sum_{i=1}^n U_i$$

合計CPU利用率は，周期タスクのセットのCPUの計算負荷の測定に使います．

タスク\(\tau_i\)の最悪実行時間\(C_i\)が長くなるか，周期\(T_i\)が短くなるとCPU利用率は増えます．

タスクのCPU利用率の上限（UP：Upper Bound）は\(U_i\)，タスクセット\(\Gamma\)の合計CPU利用率の上限は\(U\)になります．

この上限は，タスクセットやタスクをスケジューリングするアルゴリズムに強く依存します（※タスクの周期の関係にも依存しますが，後の回で説明します）．

\(U_{ub} (\Gamma, A)\)をアルゴリズム\(A\)におけるタスクセット\(\Gamma\)のCPU利用率の上限とします．

\(U=U_{ub} (\Gamma, A)\)の場合，タスクセット\(\Gamma\)はCPUを最大限に利用しているという意味になります．

※CPUを100%利用しているとは限らないことに注意して下さい．

この状況では，タスクセット\(\Gamma\)はアルゴリズムAによりスケジュール可能ですが，どのタスクの最悪実行時間が少しでも長くなったらスケジュール不可能になります．

タスクセットのスケジュール例

2つのタスクを持つタスクセットのスケジュール例を紹介します．

タスク\(\tau_1\)はタスク\(\tau_2\)より優先度が高いです．

\(\tau_i\)：タスク	\(C_i\)：最悪実行時間	\(T_i\)：周期
\(\tau_1\)	2	4
\(\tau_2\)	2	6

タスクセットの合計CPU利用率は，\(U_{ub}=5/6 \simeq 0.83\)です．

この状況では，どのタスクの最悪実行時間が少しでも長くなったらタスクセットがスケジュール不可能になります．

理由としては，\(\tau_2\)の最初のジョブがデッドラインミスするからです．

他のタスクセットの例を紹介します．

先程のタスクセットの違いは，タスク\(\tau_2\)の周期が6から5に短くなったことです．

\(\tau_i\)：タスク	\(C_i\)：最悪実行時間	\(T_i\)：周期
\(\tau_1\)	2	4
\(\tau_2\)	2	5

タスクセットの合計CPU利用率は，\(U_{ub}=0.9\)です．

タスク\(\tau_2\)の周期を短くしてもデッドラインミスせずにスケジュール可能であることがわかります．

下記のように，タスク\(\tau_2\)の周期は4まで短くしてもスケジュールすることは可能です．

\(\tau_i\)：タスク	\(C_i\)：最悪実行時間	\(T_i\)：周期
\(\tau_1\)	2	4
\(\tau_2\)	2	4

タスクセットの合計CPU利用率は，\(U_{ub}=1.0\)です．

これ以上は，どのタスクの最悪実行時間を長くしたり，もしくは周期を短くしたりした場合は，スケジュール不可能になります．

理由としては，合計CPU利用率が1.0より大きくなるからです．

スケジュール可能上限（LUB：Least Upper Bound）

アルゴリズム\(A\)において，タスクセット\(\Gamma\)の合計CPU利用率のスケジュール可能上限（LUB：Least Upper Bound）\(U_{lub} (A)\)は下式になります．

$$U_{lub} (A) = \underset{\Gamma}{min}\ U_{ub} (\Gamma, A)$$

スケジューリングアルゴリズム\(A\)における\(U_{lub}\)の意味を解説します（下図）．

タスクセット\(\Gamma_i\)はタスクの数や周期，最悪実行時間が異なります．

アルゴリズム\(A\)でタスクセット\(\Gamma_i\)をスケジュールする時，合計CPU利用率の上限は\(U_{ubi}\)になります．

もしタスクセット\(\Gamma_i\)の合計CPU利用率が\(U_{ubi}\)以下の場合，\(\Gamma_i\)はスケジュール可能です．

もしタスクセット\(\Gamma_i\)の合計CPU利用率が\(U_{ubi}\)より大きい場合，\(\Gamma_i\)はスケジュール不可能です．

※各々のタスクセットは異なる上限を持つかもしれないことに注意して下さい．

スケジュール可能上限\(U_{lub} (A)\)は，全ての上限の最小値ですので，\(U_{lub} (A)\)以下の合計CPU利用率を持つ全てのタスクセットはアルゴリズム\(A\)でスケジュール可能です．

スケジュール可能上限\(U_{lub} (A)\)は，スケジューリングアルゴリズムにおけるタスクセットのスケジュール可能性を簡単に検証するために役に立ちます．

実際，スケジューリングアルゴリズムにおけるタスクセットの合計CPU利用率がスケジュール可能上限以下であればスケジュール可能です．

他方，\(U_{lub} < U \leq 1.0\)であれば，スケジュール可能性はタスクの周期の関係によってスケジュール可能かどうかが決まります（詳しくは後の回で説明します）．

もしタスクセットの合計CPU利用率が1.0を超える場合は，そのタスクセットはあらゆるアルゴリズムでスケジュール不可能になります．

この結果を示すために，\(H\)をタスクセットと置きます．

もし\(U>1\)ならば，\(UH>H\)になるので，以下のように示します．

$$\sum_{i=1}^n \frac{H}{T_i}C_i > H.$$

\((H/T_i)\)はタスク\(\tau_i\)がハイパーピリオドの区間中に何回実行するかを示します．

また，\((H/T_i) C_i\)は，タスク\(\tau_i\)がハイパーピリオドの区間中の合計の最悪実行時間を示します．

左辺はタスクセットが区間\([0, H)\)に要求する合計の最悪実行時間です．

合計の最悪実行時間は利用可能なCPU時間\(H\)を明らかに超えているので，タスクセットはスケジュール不可能になります．

タイムラインスケジューリング

タイムラインスケジューリング（TS: Timeline Scheduling）は，防衛軍事システムやトラフィック制御システムのようなリアルタイムシステムで周期タスクを扱うためによく使われる方法の一つです．

この方法は，時間軸を同じ長さのタイムスロットに分割します．

アプリケーションは1つもしくは複数のタスクを実行するために，このタイムスロットの時間を確保します．

このタイムスロットの長さはアプリケーションの要求により長さが変わります．

タイマは各々のタイムスロットの最初のタスクの起動に同期します．

タイムラインスケジューリングの例

タイムラインスケジューリングの例を紹介します．

タスクA，B，Cの周期が下表のような場合で実行するとします．

\(\tau_i\)：タスク	\(T_i\)：周期 [ms]
\(\tau_1\)	25
\(\tau_2\)	50
\(\tau_3\)	100

最適なタイムスロットの長さは25ms（全てのタスクの周期の最大公約数）と計算できます．

要求される周期を満たすためには，タスクAは毎回のタイムスロット，タスクBは2回毎のタイムスロット，タスクCは4回毎のタイムスロットで実行しなければなりません．

このタスクセットのスケジューリング例は下図になります．

タイムスロットの長さはMinor Cycle，スケジューリング自身が繰り返す最短の間隔（ハイパーピリオド）はMajor Cycleと呼ばれます．

一般的には，Major Cycleは全ての周期の最小公倍数（この例だと100ms）になります．

このCPUにおいてスケジュール可能であることをあらかじめ保証するためには以下の条件を満たす必要があります．

• タスクの最悪実行時間を知っていること
• 各々のタイムスロット内の最悪実行時間の合計がMinor Cycle以下であること

上図で示した例では，もし\(C_A\)，\(C_B\)，\(C_C\)がタスクの最悪実行時間を示すならば，以下を満たす必要があります．

\begin{cases}
C_A + C_B \leq 25ms \\
C_A + C_C \leq 25ms
\end{cases}

タイムラインスケジューリングの利点と欠点

タイムラインスケジューリングの利点は，シンプルなことです．

この方法の実装方法は以下になります．

• Minor Cycleと同じ周期タイマで割り込みを発生させる
• Major Cycleに与えられた順番でタスクを呼び出すためのメインプログラムを書く
• 各々のMinor Cycleの最初に時刻同期ポイントを挿入する

タスクの実行順序は，カーネルのスケジューリングアルゴリズムにより決まりません．

タスクはメインプログラムの呼び出しにより起動します．

この方法は，コンテキストスイッチが不要なので，実行時のオーバヘッドがとても小さいです．

さらには，スケジュール時のタスクの実行順序がいつも同じなので，簡単に可視化することができます．

また，ジッタがあまり大きくなりません．すなわち，タスクの開始時刻と応答時間は大きく変動しません．

これらの利点にも関わらず，タイムラインスケジューリングは多くの欠点があります．

例えば，オーバロード（過負荷）の状態にとても脆弱です．

もしタスクがMinor Cycleの境界までに終了しなくてデッドラインミスした場合，実行を継続するか中断しなければなりません．

両方のケースで，システムは危険な状況で実行しなければなりません．

実際，デッドラインミスしたタスクが実行を継続する場合，他のタスクのドミノ倒しを引き起こして全体のスケジュールが破綻します．

他方，デッドラインミスしたタスクが共有データを更新している間に実行を中断した場合，システムは一貫性を保てない状態になり，正しく処理できなくなるかもしれません．

タイムラインスケジューリングの他の大きな問題は，アプリケーションの変更に敏感であることです．

タスクを更新することで最悪実行時間が長くなったり，周期が短くなったりする場合，全体のスケジューリングの順序がスクラッチから再構成する必要があるかもしれません．

以前の例でタスクBがB'に更新してB'の最悪実行時間\(C_B'\)が長くなり，\(C_A + C_{B'} > 25ms\)になった場合を考えます．

この場合，タイムラインの利用可能な時間を確保するために，タスクB'は2つかより多くのサブタスクに分割しなければなりません．

タスクの周期の変更は，スケジューリングの根本的な変更を引き起こすかもしれません．

例えば，タスクBの周期を50msから40msに変更した場合，以前のスケジュールは有効ではなくなります．

理由としては，新しいMinor Cycleが5msになり，新しいMajor Cycleが200msになるからです．

この変更の後，Minor Cycleが以前より短くなったことで，全てのタスクが新しいタイムスロットに割り当てられる小さいサブタスクに分割する必要があるかもしれません．

最後に，タイムラインスケジューリングの他の制限は，タスクの実行順序の変更なしに効率的に非周期タスクを扱うことが難しいことです．

これらの問題は優先度に基づくスケジューリングアルゴリズムで解決することができます．

まとめ

今回は，CPU利用率の深掘りとタイムラインスケジューリングを解説しました．

次回はLiuとLaylandのモデルにおける優先度に基づくスケジューリングアルゴリズムを紹介します．

代表的なアルゴリズムなので是非きちんと理解しましょう！

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

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

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

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

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