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

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

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

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

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

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

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

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

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

資源とはプロセスが実行を進めるために利用できるソフトウェア構造体のことです．

典型的には，資源は，データ構造体，変数のセット，メインメモリ領域，ファイル，または周辺デバイスのレジスタのセットです．

特定のプロセスに特化した資源をプライベート，より多くのタスクで使用できる資源を共有資源と呼びます．

並行アクセスから保護された共有資源を排他的資源と呼びます．

排他的資源の中にあるデータ構造の一貫性を確保するために，任意の並行OSは競合するタスク間の排他制御を保証する適切な資源アクセスプロトコルを利用する必要があります．

排他制御の制約下で実行されるコードの一部をクリティカルセクションと呼びます．

クリティカルセクションに入る必要があるタスクは，他のタスクが資源を保持しなくなるまで待たなければなりません．

排他的資源を待っているタスクは，その資源上でブロックされます．

そうでなければクリティカルセクションに入って進み，資源を保持します．

タスクがクリティカルセクションから離れる時，クリティカルセクションに関連付けられている資源が解放されます．

別の待機中のタスクがあれば，そのタスクに割り当てることができます．

OSは一般的にセマフォと呼ばれる一般的な同期機構を提供しており，クリティカルセクションを構築するためにタスクが利用できます．

セマフォはカーネルのデータ構造体で，初期化とは別に，通常は\(wait\)と\(signal\)と呼ばれる2つのカーネルプリミティブを介してのみアクセスできます．

この機構を利用する場合，排他的資源\(R_k\)は異なるセマフォ\(S_k\)で保護され，資源\(R_k\)上で動作するクリティカルセクションは，\(wait(S_k)\)プリミティブで始まり，\(signal(S_k)\)プリミティブで終わる必要があります．

資源上でブロックされたすべてのタスクは，資源を保護するセマフォに関連付けられたキューに保持されます．

実行中のタスクがロックされたセマフォ上で\(wait\)プリミティブを実行すると，別のタスクがセマフォのロックを解除する\(signal\)プリミティブを実行するまで待機状態になります．

タスクが待機状態から離れるときは，実行状態ではなく実行可能状態になるので，スケジューリングアルゴリズムによりCPUが最高優先度のタスクに割り当てられるようになります．

上述した状態の状態遷移図を下図に示します．

並行実行するタスクが排他的なモードで共有資源を利用する場合に，ユニプロセッサシステム（プロセッサ（コア）が1つのシステム）で発生する可能性のある問題について説明します．

このような問題を回避し，タスクの最大ブロック時間を制限するために設計された資源アクセスプロトコルを紹介します．

次に，このようなブロック時間をスケジュール可能性解析に利用して，周期タスクセットの保証テストを拡張する方法を示します．

資源アクセスプロトコルにおける優先度逆転問題

2つのタスク\(\tau_1\)と\(\tau_2\)が排他的資源\(R_k\) (リスト等) を共有しており，その上で2つの操作 (挿入や削除等) が定義されているとします．

排他制御を保証するためには，両方の操作をクリティカルセクションとして定義する必要があります．

この目的のためにバイナリセマフォ\(S_k\)が利用される場合，クリティカルセクションは\(wait(S_k)\)プリミティブで始まり，\(signal(S_k)\)プリミティブで終わらなければなりません（下図）．

もしプリエンプションが許可されていて，\(\tau_1\)が\(\tau_2\)よりも高い優先度を持っている場合，上図に描かれている状況では，\(\tau_1\)はブロックされます．

ここでは，まずタスク\(\tau_2\)が起動し，しばらくするとクリティカルセクションに入り，セマフォをロックします．

\(\tau_2\)がクリティカルセクションを実行している間にタスク\(\tau_1\)が到着し，優先度が高いため，\(\tau_2\)をプリエンプションして実行を開始します．

しかし，時刻\(t_1\)でクリティカルセクションに入ろうとしたとき，\(\tau_1\)はセマフォ上でブロックされているので，\(\tau_2\)は再開します．

\(\tau_1\)は，\(signal(S_k)\)プリミティブを実行してクリティカルセクションを解放し，セマフォをアンロックする時刻\(t_2\)まで待たなければなりません．

この単純な例では，\(\tau_1\)の最長ブロック時間は，そのクリティカルセクションを実行するために\(\tau_2\)が必要とする時間と等しくなります．

このようなブロックは，競合タスクの並行アクセスから共有資源を保護するために必要な排他制御の直接的な結果であるため，回避できません．

残念ながら，一般的なケースにおいて，ビジー状態（使用中）の資源上のタスクのブロック時間は，低優先度タスクにより実行されるクリティカルセクションの持続時間により制限できません．

実際に，上図に示されている例を考えてみましょう．

ここでは，3つのタスク\(\tau_1\)，\(\tau_2\)，\(\tau_3\)の3つのタスクがあり，\(\tau_1\)と\(\tau_3\)はバイナリセマフォ\(S\)で保護された排他的資源を共有しています．

もし\(\tau_3\)が時刻\(t_0\)で開始する場合，時刻\(t_2\)に\(\tau_1\)が到着し，そのクリティカルセクションの中で\(\tau_3\)がプリエンプションされてしまうことがあります．

時刻\(t_3\)では，\(\tau_1\)は資源を利用しようとしますが，セマフォ\(S\)上でブロックされています．

したがって，\(\tau_3\)はそのクリティカルセクションの中で実行を続けます．

もし\(\tau_2\)が時刻\(t_4\)に到着した場合，優先度が高いので \(\tau_3\)をプリエンプションし，\(\tau_1\)のブロック時間をその全体の持続時間分だけ増加させます．

結果として，\(\tau_1\)の最長ブロック時間は，\(\tau_3\)により実行されるクリティカルセクションの長さだけでなく，\(\tau_2\)の最悪実行時間にも依存します．

これは，他の中程度の優先度のタスクで再発すると，制御不能なブロックにつながり，重要なデッドラインをミスする原因になりかねない状況です．

高優先度タスク\(\tau_1\)は低優先度\(\tau_2\)，\(\tau_3\)の実行を待つので，優先度逆転は区間\([t_3, t_6)\)で発生します．

一般的に，優先度逆転の持続時間は制限されていません．

この理由は，\(\tau_3\)をプリエンプションできる中間優先度タスクは間接的に\(\tau_1\)をブロックするからです．

固定優先度スケジューリングと動的優先度スケジューリングの両方で，優先度逆転を回避するための手法が定義されています．（EDFでは，このような現象を「デッドライン逆転」と呼ぶことがあります．）

固定優先度スケジューリングで開発されたすべての方法は，共有資源にアクセスする時，クリティカルセクションに出入りするための与えられたプロトコルに従って，タスクの優先度を高くします．

同様に，EDFの下で開発された手法は，タスクの相対デッドラインに基づいてパラメータを変更します．

資源アクセスプロトコルの用語と想定

\(n\)個の周期的なタスクの集合\(\tau_1, \tau_2, ..., \tau_n\)は，\(m\)個の共有資源\(R_1, R_2, ..., R_m\)を介して実行します．

タスク\(\tau_i\)は，周期\(T_i\)と最悪実行時間\(C_i\)によって特徴づけられます．

資源\(R_k\)は，異なるセマフォ\(S_k\)によって保護されています．

したがって，資源\(R_k\)に関するすべての重要なセクションは\(wait(S_k)\)操作を行い，\(signal(S_k)\)操作で終了します．

プロトコルはタスクの優先度を変更するので，タスクは（例えばRate Monotonicスケジューリングにより割り当てられる）固定の通常優先度\(P_i\)とアクティブ優先度\(p_i (p_i \geq P_i)\)（動的に変更し初期値は\(P_i\)）によって特徴づけられます．

資源アクセスプロトコル固有の表記は以下になります．

• \(B_i\)：タスク\(\tau_i\)の最長ブロック時間
• \(z_{i,k}\)：セマフォ\(S_k\)で保護されるタスク\(\tau_i\)の一般的なクリティカルセクション
• \(Z_{i,k}\)：セマフォ\(S_k\)で保護されるタスク\(\tau_i\)の最長のクリティカルセクション
• \(\delta_{i,k}\)：\(Z_{i,k}\)の持続時間
• \(z_{i,h} \subset z_{i,k}\)：\(z_{i,h}\)が\(z_{i,k}\)のサブセットであること（完全に含まれていること）
• \(\sigma_i\)：\(\tau_i\)が使用するセマフォの集合
• \(\sigma_{i,j}\)：低優先度タスク\(\tau_j\)がアクセスする\(\tau_i\)をブロックできるセマフォの集合
• \(\gamma_{i,j}\)：低優先度タスク\(\tau_j\)がアクセスする\(\tau_i\)をブロックできる最長クリティカルセクションの集合
  $$\gamma_{i,j} = \{ Z_{j,k}\ |\ (P_j < P_i) \ \rm{and} \ (S_k \in \sigma_{i,j})\}$$
• \(\gamma_i\)：\(\tau_i\)をブロックできる最長クリティカルセクションの集合
  $$\gamma_i = \bigcup_{j: P_j < P_i} \gamma_{i,j}$$

さらに，資源アクセスプロトコルの性質は，以下の仮定の下で有効です．

• タスク\(\tau_1, \tau_2, ..., \tau_n\)は異なる優先度を持つと仮定し，通常優先度の降順でリストアップされ，\(\tau_1\)が最も高い通常優先度を持ちます．
• タスクは，I/O操作や明示的な（ロックされたセマフォを除く）同期プリミティブでは中断しません．
• どのタスクでも利用される重要なセクションが適切にネストされています．
  すなわち，ペア\(z_{i,h}\)と\(z_{i,k}\)において，\(z_{i,h} \subset z_{i,k}, z_{i,k} \subset z_{i,h}\)または\(z_{i,h} \cap z_{i,k} = \emptyset\)が成立します．
• クリティカルセクションはバイナリセマフォによって保護されており，クリティカルセクション内には一度に1つのタスクしか存在できないことを意味します．

まとめ

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

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

• 資源アクセスプロトコルの紹介
• 資源アクセスプロトコルにおける優先度逆転問題
• 資源アクセスプロトコルの用語と想定

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

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

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

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

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