REAL-TIME SYSTEMS TECHNOLOGY

【第29回】元東大教員から学ぶリアルタイムシステム「資源アクセスプロトコルの例」

本記事の信頼性

  • リアルタイムシステムの研究歴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にオープンソースとして公開

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

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

第28回リアルタイムシステム
【第28回】元東大教員から学ぶリアルタイムシステム「資源アクセスプロトコル」

こういった私から学べます. 前回を読んでいない方はこちらからどうぞ. リアルタイムシステムの記事一覧はこちらからどうぞ. 目次1 資源アクセスプロトコルの紹介2 資源アクセスプロトコルにおける優先度逆 ...

続きを見る

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

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

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

続きを見る

資源アクセスプロトコルの例

資源アクセスプロトコルの例として,以下の2つのシンプルなプロトコルを紹介します.

  • Non-Preemptive Protocol(NPP)
  • Highest Locker Priority(HLP)Protocol

Non-Preemptive Protocol(NPP)

ブロック時間の上限がない優先度逆転問題を回避する簡単な解決策は,任意のクリティカルセクションの実行中にプリエンプションを許可しないことです.

この方法は,Non-Preemptive Protocol(NPP)と呼ばれ,共有資源に入るたびにタスクの優先度を最高優先度に引き上げることで実装できます.

特に,タスク\(\tau_i\)が資源\(R_k\)を獲得するとすぐに,そのアクティブ優先度\(p_i\)が最高優先度になります.

$$p_i(R_k) = \max_{h} \{P_h\}$$

Example of NPP Preventing Priority Inversion

タスクがクリティカルセクションを終了すると,アクティブ優先度は通常の優先度\(P_i\)にリセットされます.

上図に,NPPがどのように優先度逆転問題を解決しているかを示します.

しかし,不必要なブロックが発生するので,この方法はタスクが短いクリティカルセクションを利用する場合にのみ適しています.

例えば,下図のような場合を考えてみましょう.

タスク\(\tau_1\)は資源を利用しない最高優先度タスクであり,\(\tau_2\)と\(\tau_3\)は排他的資源を共有する低優先度タスクです.

もし優先度の低いタスク\(\tau_3\)が長いクリティカルセクションに入ると,不要に長い時間ブロックされる可能性があります.

Example in which NPP Causes Unnecessary Blocking on Task1

NPPにおけるタスクのブロック時間の算出

もしタスク\(\tau_j\)がクリティカルセクション内にある場合,タスク\(\tau_i\)は低優先度タスク\(\tau_j\)をプリエンプションできないので,低優先度タスクに属するクリティカルセクションによって\(\tau_i\)は潜在的にブロックされる可能性があります.

したがって,\(\tau_i\)をブロックできる最長クリティカルセクションの集合\(\gamma_i\)は下式になります.

$$\gamma_i = \{Z_{j,k} | P_j < P_i, k = 1,...,m \}$$

また,資源\(R\)を獲得したタスクをプリエンプションできないので,常に1つの資源のみをロックできます.

したがって,タスク\(\tau_i\)は,最大でも低優先度タスクに属する1つのクリティカルセクションの長さ分だけブロックされる可能性があります.

結果として,タスク\(\tau_i\)の最大ブロック時間\(B_i\)は,低優先度タスクに属するものの中で最も長いクリティカルセクションの持続時間になります.

$$B_i = \underset{j,k}{\max} \{ \delta_{j,k} - 1 | Z_{j,k} \in \gamma_i \}$$

\(Z_{j,k}\)はブロックされる\(\tau_i\)の到着前に開始しなければならないので,1ユニット時間が\(\delta_{j,k}\)から減算されることに注意してください.

上図に示された不要なブロックは,その資源を共有していない時に,高優先度タスクがプリエンプションするのを妨げない適切な優先度レベルにクリティカルセクション内の優先度を高くすることで容易に回避できます.

Highest Locker Priority(HLP)Protocol

Highest Locker Priority(HLP)Protocolは,資源\(R_k\)に入るタスクの優先度を,その資源を共有するタスクの中で最高優先度にすることで,NPPを改善します.

具体的には,タスク\(\tau_i\)が資源\(R_k\)に入るとすぐに,そのアクティブ優先度が最高優先度になります.

$$p_i (R_k) = \underset{h}{\max} \{ P_h | \tau_h\ {\rm uses}\ R_k \} \tag{29.1}$$

タスクがクリティカルセクションを終了すると,アクティブ優先度\(p_i\)は通常優先度\(P_i\)にリセットされます.

式\((29.1)\)の優先度のオンライン(実行時の)算出は,資源\(R_k\)に\(R_k\)を共有するタスクの最高優先度に等しい(オフライン(実行前)に算出された)優先度上限\(C(R_k)\)を割り当てることで単純化することができます.

$$C(R_k) \overset{{\rm def}}{=} \underset{h}{{\rm max}} \{ P_h | \tau_h\ {\rm uses}\ R_k \}$$

タスク\(\tau_i\)が資源\(R_k\)を獲得するとすぐに,そのアクティブ優先度を資源の上限まで高くします.

このため,このプロトコルはImmediate Priority Ceilingとも呼ばれます.

共有資源の上限が\(P_1\)の場合のHLPによる優先度逆転問題を解決するスケジュール例は,NPPの例(最初の図)と同じになります.

下図に,共有資源の上限が\(P_2\)である場合の別の例を示します.

\(\tau_1\)はクリティカルセクション内で\(\tau_3\)をプリエンプションできますが,\(\tau_2\)は\(\tau_3\)がそのクリティカルセクションを出るまでブロックされます.

また,実行中のプロトコルによって\(\tau_3\)のアクティブ優先度がどのように変化するかを示しています.

Example of Schedule under HLP

HLPにおけるタスクのブロック時間の算出

HLPでは,タスク\(\tau_i\)は通常優先度\(P_i\)以上の資源の上限を持つ低優先度タスクに属するクリティカルセクションによってのみブロックされます.

$$\gamma_i = \{ Z_{j,k} | (P_j < P_i)\ {\rm and}\ C(R_k) \geq P_i$$

さらに,以下の定理で形式的に述べられているように.1つのタスクは最大1回までブロックされます.

定理29.1:HLPでは,タスク\(\tau_i\)は最大でも\(\gamma_i\)の集合に属する1つのクリティカルセクションの間だけブロックされる.

証明:\(\tau_i\)が2つのクリティカルセクション\(z_{1,a}\)と\(z_{2,b}\)によりブロックされると仮定し,矛盾を導くことで,この定理を証明します.

これを実現するためには,両方のクリティカルセクションは\(P_i\)よりも低い優先度を持つ異なるタスク (\(\tau_1\)と\(\tau_2\)) に属していなければならず,両方とも\(P_i\)以上の上限を持たなければなりません.

つまり,前提として以下を持つ必要があります.

\begin{eqnarray} P_1 \leq P_i \leq C(R_a) \\ P_2 \leq P_i \leq C(R_b) \end{eqnarray}

\(\tau_i\)が到着した時,\(\tau_1\)と\(\tau_2\)が両方とも資源を獲得している場合に限り,\(\tau_i\)は2回ブロックされます.

これはどちらか(例えば\(\tau_1\))がクリティカルセクションの中で他方をプリエンプションした場合にのみ発生します.

しかし,もし\(z_{2,b}\)の中で\(\tau_1\)が\(\tau_2\)をプリエンプションしたとすると,\(P_2 > C(R_b)\)となり,これは矛盾します.

したがって,定理は証明されました.□

タスク\(\tau_i\)は最大1回ブロックできるので,\(\tau_i\)が被る最大ブロック時間\(B_i\)は,\(\tau_i\)をブロックできる最も長いクリティカルセクションの持続時間になります.

$$B_i = \underset{j,k}{{\rm max}} \{ \delta_{j,k} - 1 | Z_{j,k} \in \gamma_i \}$$

\(\tau_j\)が\(\tau_i\)の前に\(Z_{j,k}\)に入るために,1ユニット時間が\(\delta_{j,k}\)から減算されることに注意してください.

HLPはNPPを改善しましたが,まだ悲観的な要素が多いので,不要なブロックが発生する可能性があります.

実際には,資源を必要とする前に,タスクはプリエンプションしようとした時点でブロックされます.

クリティカルセクションが条件文の1つのブランチ(例:if-else文のどちらかの実行先)にしか含まれていない場合,資源を獲得しないブランチを実行する可能性があるため,タスクが不要にブロックされてしまう可能性があります.

まとめ

今回は資源アクセスプロトコルの例を紹介しました.

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

  • Non-Preemptive Protocol(NPP)
  • Highest Locker Priority(HLP)Protocol

どちらもシンプルなプロトコルですが,あまり効果的ではないので,次回は実用的な資源アクセスプロトコルを紹介します.

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

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

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

友だち追加

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

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

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

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

続きを見る

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