本記事の信頼性
- リアルタイムシステムの研究歴12年．
- 東大教員の時に，英語でOS（Linuxカーネル）の授業．
- 2012年9月～2013年8月にアメリカのノースカロライナ大学チャペルヒル校（UNC）コンピュータサイエンス学部で客員研究員として勤務．C言語でリアルタイムLinuxの研究開発．
- プログラミング歴15年以上，習得している言語: C/C++，Python，Solidity/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社で自分に合うスクールを見つけましょう．後悔はさせません！
資源アクセスプロトコルの例
資源アクセスプロトコルの例として，以下の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\}$$
タスクがクリティカルセクションを終了すると，アクティブ優先度は通常の優先度\(P_i\)にリセットされます．
上図に，NPPがどのように優先度逆転問題を解決しているかを示します．
しかし，不必要なブロックが発生するので，この方法はタスクが短いクリティカルセクションを利用する場合にのみ適しています．
例えば，下図のような場合を考えてみましょう．
タスク\(\tau_1\)は資源を利用しない最高優先度タスクであり，\(\tau_2\)と\(\tau_3\)は排他的資源を共有する低優先度タスクです．
もし優先度の低いタスク\(\tau_3\)が長いクリティカルセクションに入ると，不要に長い時間ブロックされる可能性があります．
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\)のアクティブ優先度がどのように変化するかを示しています．
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_1 > 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社で自分に合うスクールを見つけましょう．後悔はさせません！
次回はこちらからどうぞ．
