REAL-TIME SYSTEMS TECHNOLOGY

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

2021年1月31日

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOS(Linuxカーネル)の授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校(UNC)コンピュータサイエンス学部で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発.
  • プログラミング歴15年以上,習得している言語: C/C++PythonSolidity/Vyper,Java,Ruby,Go,Rust,D,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開
  • 2020年1月~現在はアメリカのノースカロライナ州チャペルヒルにあるGuarantee Happiness LLCのCTOとしてECサイト開発やWeb/SNSマーケティングの業務.2022年6月~現在はアメリカのノースカロライナ州チャペルヒルにあるJapanese Tar Heel, Inc.のCEO兼CTO.
  • 最近は自然言語処理AIイーサリアムに関する有益な情報発信に従事.
    • (AI全般を含む)自然言語処理AIの論文の日本語訳や,AIチャットボット(ChatGPT,Auto-GPT,Gemini(旧Bard)など)の記事を50本以上執筆.アメリカのサンフランシスコ(広義のシリコンバレー)の会社でプロンプトエンジニア・マネージャー・Quality Assurance(QA)の業務委託の経験あり.
    • (スマートコントラクトのプログラミングを含む)イーサリアムや仮想通貨全般の記事を200本以上執筆.イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり.

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

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

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

リアルタイムシステムで使われているリアルタイム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社で自分に合うスクールを見つけましょう.後悔はさせません!

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

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