REAL-TIME SYSTEMS TECHNOLOGY

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

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOSの授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校コンピュータサイエンス学部2021年の世界大学学術ランキングで20位)で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発
  • プログラミング歴15年以上,習得している言語: C/C++,Java,Python,Ruby,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開

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

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

第32回リアルタイムシステム
【第32回】元東大教員から学ぶリアルタイムシステム「Stack Resource Policy」

こういった私から学べます. 前回を読んでいない方はこちらからどうぞ. リアルタイムシステムの記事一覧はこちらからどうぞ. 目次1 Stack Resource Policy(SRP)2 SRPで使う用 ...

続きを見る

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

リアルタイムシステム
元東大教員から学ぶリアルタイムシステム

こういった私から学べます. リアルタイムシステムとは,決められた時間(デッドライン)までに処理を完了しなければならない性質をもつシステムのことです. リアルタイムシステムは,ロボット,自動車や航空機な ...

続きを見る

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

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

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

一般的に,すべての拡張テストは,その計算時間\(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等の)資源の上限を利用するプロトコルは,アプリケーションでそのような値を指定するための追加のシステムコールが必要です.

最後まで読んで頂きありがとうございました.

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

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

友だち追加

独学が難しいあなたは,C言語を学べるおすすめのオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう.

-REAL-TIME SYSTEMS, TECHNOLOGY
-, , , , , , , , , , , , , , , , , , , , , , ,