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

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

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

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

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

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

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

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

Priority Exchange（PE）

Priority Exchange（PE）は，ハード周期タスクセットでソフト非周期タスクを実行するための非周期サーバです．

DSに対して，PEは非周期タスクの応答性に関して若干悪い性能ですが，周期タスクセットのスケジュール可能性は高くなります．

DSと同様に，PEは非周期タスクを実行するために（普通は最高優先度を持つ）周期タスクを生成します．

しかし，PEは非周期サーバの容量をDSと同じ方法で保持しません．

PEは，低優先度の周期タスクの実行時間と交換するために，自分の高優先度の容量を保持します．

各々のサーバの周期の最初に，容量は満タンまで補給します．

もし中断された非周期タスクがあり，非周期サーバが最高優先度で実行可能状態の場合，非周期タスクを利用可能な容量で実行します．

そうでなければ，容量\(C_s\)は最高優先度の実行可能状態の周期タスクと優先度を交換して実行します．

優先度交換が周期タスクとPEで発生した場合，非周期サーバが周期タスクの優先度レベルで容量を蓄積している間，周期タスクは非周期サーバの優先度レベルで実行します．

周期タスクは先に実行し，非周期サーバの容量は空にならずに低優先度で保持します．

もし非周期タスクが到着し容量を使う場合，容量が非周期サーバに使われるか，バックグラウンド処理の優先度レベルが低下するまで，優先度交換が他の低優先度タスクと行われます．

PEの目的は非周期タスクの応答性を高くすることなので，全ての優先度のタイブレーク方式は非周期タスクを優先します．

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

上表にタスクのパラメータ，上図にPEによる非周期タスクのスケジューリング例を示します．

この例では，PEは周期\(T_s=5\)，容量\(C_s=1\)で実行します．

PEにより管理される非周期タスクの実行時間は全ての周期タスクに交換可能なので，時間関数としての各々の優先度レベルで蓄積される容量は，関連する周期タスクのスケジュールの重なりで表します．

具体的には，図の最初のタイムラインはシステムに到着する非周期タスクを表します．

2番目のタイムラインは，PEの優先度で利用可能な容量を可視化します．

3番目と4番目のタイムラインは，優先度交換メカニズムの結果として対応する優先度レベルで累積される容量を表します．

• 時刻\(t=0\)：PEは満タンまで容量を補給しますが，非周期タスクがないので，容量\(C_s\)はタスク\(\tau_1\)の実行と交換されます．
  結果として，タスク\(\tau_1\)は先に実行し，非周期サーバはタスク\(\tau_1\)の優先度レベルで1ユニット時間を蓄積します．
• 時刻\(t=4\)：タスク\(\tau_1\)は終了し，タスク\(\tau_2\)が実行開始します．
  非周期タスクがないので，他の優先度交換が\(\tau_1\)と\(\tau_2\)の間で起こります．
• 時刻\(t=5\)：容量が非周期サーバの優先度で補給され，最初の非周期タスクの実行に使われます．
• 時刻\(t=10\)：容量が最高優先度で補給されますが，非周期タスクがないのでタスク\(\tau_1\)の優先度レベルまで優先度が低下します．
• 時刻\(t=12\)：タスク\(\tau_1\)の優先度レベルで累積した容量は2番目の非周期タスクの実行に使われます．
• 時刻\(t=15\)：新しい高優先度の補給が起こりましたが，容量はタスク\(\tau_2\)の実行時間分と交換します．
• 時刻\(t=18\)：タスク\(\tau_2\)の優先度レベルで累積した残りの容量は他のタスクが実行可能状態ではないので，徐々に減ります．

周期タスクのスケジュールに重複する容量は，優先度交換がない場合に関して，タスクが先んじて実行する時間量をいつでも示すことに注意して下さい．

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

上図にPEで非周期タスクをスケジュールする他の例を示します．

• 時刻\(t=5\)：非周期タスクがなくタスク\(\tau_1\)はアイドル状態なので，非周期サーバの容量はタスク\(\tau_2\)の最低優先度レベルまですぐに低下します．
• 時刻\(t=11\)：最初の非周期タスクが到着し，タスク\(\tau_1\)の優先度レベルで累積した容量を利用して，計算時間の最初のユニットはすぐに実行します．
• 時刻\(t=12\)：残りの容量が最低優先度レベルで利用可能でタスク\(\tau_1\)はまだ実行可能状態なので，タスク\(\tau_1\)は非周期タスクをプリエンプションして実行します．
• 時刻\(t=13\)：タスク\(\tau_1\)が終了して，非周期タスクが実行を再開します．

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

最悪の場合，PEは周期タスクとして振る舞うので，PEと一緒に実行する周期タスクセットのスケジュール可能上限はPSの場合と同様のスケジュール可能上限になります．

したがって，PEはシステムの最高優先度タスクと想定しているので，スケジュール可能上限は下式になります．

$$U_{lub} = U_s + n (K^{1/n} - 1)$$

ここで，\(K\)は以下になります．

$$K = \frac{2}{U_s + 1}$$

\(n\)個の周期タスクとPEのCPU利用率がそれぞれ\(U_p\)と\(U_s\)の場合，周期タスクセットは以下を満たす場合にRMでスケジュール可能になります．

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

PE vs. DS

DSとPEは，バックグラウンドやポーリングより非周期タスクの応答性を向上させるための代わりとなる手法です．

ここで，これらの手法は，性能（非周期タスクの応答時間），スケジュール可能性，実際の複雑さの観点で比較されます．

また，特定のリアルタイムアプリケーション向けに一番適切な手法をシステム設計者が選択するための手助けとなります．

DSがPEより実装が簡単な理由は，オリジナルの優先度レベルで容量をいつも維持し，低優先度タスクと実行時間を交換しないからです．

PEは優先度交換の管理及び追跡が必要になります．この実装が，特に周期タスクの数が増えた場合，DSに対してPSのオーバヘッドが大きくなります．

他方，DSはPSより単純な分スケジュール可能上限が低下するというデメリットがあります．

周期タスクセットのCPU利用率\(U_p\)とした場合，周期タスクのリアルタイム性を保証できるDSの最大CPU利用率はPEの最大CPU利用率より小さくなります．

DSとPEの最大CPU利用率は，それぞれ式\((14.3)\)と\((15.1)\)からのCPU利用率の関数として表されます．

PSのように，PEはCPU利用率を持つ周期タスクとして表されます．

したがって，下式になります．

$$U_{DS}^{max} = \frac{2-P}{2P-1}$$

$$U_{PE}^{max} = \frac{2-P}{P}$$

ここで，\(P\)は以下になります．

$$P = \prod_{i=1}^n (U_i + 1)$$

全ての\(n\)個の周期タスクは同じCPU利用率\(U_i=U_p/n\)を持つ場合，\(P\)は\(U_p\)の関数として下式のように表現できることに注意して下さい．

$$P = \left( \frac{U_p}{n} + 1\right)^n$$

全ての周期タスクが同じCPU利用率を保つ場合が，タスクセットの最悪の場合なのはRMの証明から明らかなことに注意して下さい．

上図に（タスク数が多い場合における）\(U_p\)の関数として最大CPU利用率のプロットを示します．

\(U_p=0.6\)の場合，DSの最大CPU利用率は7%ですが，PEの最大CPU利用率は10%になります．

\(U_p=0.3\)の場合，DSは38%を超えませんが，PEは48%を超えています．

ファーム非周期タスクを考慮すればするほど，PEのスケジュール可能性解析はPSより複雑になります．

一般的には，非周期タスクがPEで処理される場合，非周期サーバの容量は\(n+1\)優先度レベルで分散されます．

したがって，非周期タスクの終了時刻の算出が，非周期タスクのデッドラインまで全ての周期タスクのスケジュールの構成が必要になるかもしれません．

まとめ

今回は，非周期サーバPriority Exchange（PE）を紹介しました．

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

• PEの特徴
• PEのスケジュール可能性解析
• PE vs. DS

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

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

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

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

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