【第33回】元東大教員から学ぶリアルタイムシステム「資源アクセスプロトコルのスケジュール可能性解析とまとめ」

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

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

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

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

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

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

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

資源アクセスプロトコルのスケジュール可能性解析

ここでは，共有資源の存在下で周期的なタスクセットのスケジュール可能性を解析する方法を説明します．

独立したタスクのために提示されたすべてのスケジュール可能性解析テストは，その値がスケジュールで採用されている特定の並行制御プロトコルに依存するブロッキング時間を含むように拡張できます．

一般的に，すべての拡張テストは，その計算時間\(C_i\)にブロッキング係数\(B_i\)を追加することで，一度に1つのタスク\(\tau_i\)を保証します．

また，プリエンプティブなスケジューリングで必要十分条件のスケジュール可能性判定テストは，ブロッキング係数の存在下でのみ十分条件になります．

ブロッキング条件は，タスクごとに異なるだけでなく同時に発生することのない最悪のシナリオで導き出されるからです．

Rate Monotonic（RM）向けLiuとLaylandのテスト

ブロッキング係数と相対デッドラインが周期に等しい周期的なタスクの集合は，以下の場合，RMによりスケジュール可能です．

$$\forall i = 1, ..., n \ \ \ \sum_{h: P_h > P_i} \frac{C_h}{T_h} + \frac{C_i + B_i}{T_i} \leq i (2^{1/i} - 1)$$

Earliest Deadline First（EDF）向けLiuとLaylandのテスト

ブロッキング係数と相対デッドラインが周期に等しい周期的なタスクの集合は，以下の場合，EDFによりスケジュール可能です．

$$\forall i = 1, …, n \ \ \ \sum_{h: P_h > P_i} \frac{C_h}{T_h} + \frac{C_i + B_i}{T_i} \leq 1$$

Hyperbolic Boundテスト

Hyperbolic Boundを利用して，ブロッキング係数と相対デッドラインが周期に等しい周期的なタスクの集合は，以下の場合，RMによりスケジュール可能です．

$$\forall i = 1, …, n \ \ \ \prod_{h: P_h > P_i} \left( \frac{C_h}{T_h} + 1 \right) \left( \frac{C_i + B_i}{T_i} + 1 \right) \leq 2 $$

応答時間解析（RTA：Response Time Analysis）

ブロッキング条件を利用して，固定優先度を持つ一般的なタスク\(\tau_i\)の応答時間は，以下の反復関係により算出されます．

\begin{cases}
R_i^{(0)} &=& C_i + B_i \\
R_i^{(s)} &=& C_i + B_i + \sum_{h: P_h > P_i} \left\lceil \frac{R_i^{(s-1)}}{T_h} \right\rceil C_h \\
\end{cases}

ワークロード解析

同様に，ワークロード解析を利用して，ブロッキング係数を持つタスクセットが以下の場合，固定優先度でスケジュール可能です．

$$\forall i = 1, …, n\ \ \ \exists t \in {\cal TS_i}: B_i + W_i(t) \leq t $$

集合\({\cal TS_i}\)は，定理9.1で定義されています．

Processor Demand

ブロッキング用語の存在下でのProcessor Demandは，ブロッキング関数\(B(L)\)の概念を利用して，Baruahにより拡張され，\(L\)以下の相対デッドラインを持つタスクが，\(L\)より長い相対デッドラインを持つタスクによりブロックされる可能性がある時間の最大量として定義されています．

\(\delta_{j,h}\)を\(\tau_j\)が\(\tau_h\)により必要とされる資源を保持する最長時間と定義する場合，ブロッキング関数は次のように算出されます．

$$B (L) = \max \{ \delta_{j,h} \ | \ (D_j > L) {\rm \ and \ } (D_h \leq L ) \} $$

そして，\(U < 1\)かつ以下であれば，タスクセットはEDFによりスケジュール可能になります．

$$\forall L \in {\cal D} \ \ \ B(L) + g(0, L) \leq L $$

\(\cal D\)は，ハイパーピリオド\(H\)と次の式の間の最小値によって与えられる，ある時点よりも長くないすべての絶対デッドラインの集合である．

$$\max \left( D_{max}, \frac{\sum_{i=1}^n (T_i - D_i) U_i }{1 - U} \right)$$

ここで，\(D_{max} = \max \{ D_1, ..., D_n \}\)になります．

資源アクセスプロトコルのまとめ

資源アクセス プロトコル	優先度	ブロック数	悲観性	ブロック時	透過性	デッドロック回避	実装の複雑さ
NPP	全て	1	高	到着時	✓	✓	簡単
HLP	固定	1	中	到着時		✓	簡単
PIP	固定	\(\alpha_i\)	低	アクセス時	✓		困難
PCP	固定	1	中	アクセス時		✓	普通
SRP	全て	1	中	到着時		✓	簡単

これまでに紹介した並行制御プロトコルは，いくつかの性質に関して比較します．

上表は，優先度の割り当て，ブロック数，悲観性，ブロック時，透過性，デッドロック回避，実装の複雑さの観点によるアルゴリズムの定性的な評価です．

ここで，透過性とは，プロトコルがプログラミングインターフェースに与える影響のことを指します．

（NPPやPIPのような）透過的なプロトコルは，タスクのコードを変更せずに実装することができ，つまり，古典的なセマフォで利用されるのと同じプリミティブを利用できます．

この機能は，新しいカーネルプリミティブを導入することなく予測性を向上できる（VxWorks等のような）商用OSにとって，このようなプロトコルはとても魅力的です．

逆に，(HLP，PCP，SRP等の）資源の上限を利用するプロトコルは，アプリケーションでそのような値を指定するための追加のシステムコールが必要です．

C言語でLinuxにおける資源アクセスプロトコルPIPの実装を知りたいあなたはこちらからどうぞ．

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

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

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

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

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