優先度逆転と優先度継承プロトコル

優先度逆転とは「順位が引っくり返る」こと

リアルタイムシステムの大原則は「実行可能なタスクのうち最高優先度のものが常にCPUを握る」ことです。/os/realtime-scheduling/の SCHED_FIFO がまさにこの不変条件を体現します。優先度逆転（priority inversion） は、この不変条件がロックを介して破られ、最高優先度のタスクが格下のタスクに事実上追い越される現象を指します。

逆転には2種類あります。有界（bounded）逆転は、高優先度 H が低優先度 L の保持するロックを待つこと自体で、これはロックを使う以上避けられません。問題は非有界（unbounded）逆転で、待ち時間に理論上の上限が無くなる方です。本記事が扱うのはこの非有界逆転と、その封じ込め手法です。

非有界逆転はどう生まれるか

3つの優先度を持つタスク H（高）, M（中）, L（低）と、H と L が共有するロック S を考えます。M は S を一切使わないことがポイントです。

時刻1: L が起き、S を獲得してクリティカルセクションに入る
時刻2: H が起床。Lをプリエンプトして走り出す
時刻3: H が S を要求 → L が保持中なのでブロックして眠る
時刻4: ここで L が S を放せば H はすぐ再開できる…はずだが
時刻5: ロックを使わない M が起床。L をプリエンプトする
       （M > L なので正当なスケジューリング判断）
時刻6: M が走り続ける限り L は走れない
       → L は S を放せない → H も起きられない

ここで起きている逆転の本質は、H が間接的に M に負けていることです。H は M より高優先度なのに、M が走り終えるまで前進できません。しかも M は1つとは限りません。S を使わない中優先度タスクが次々起きれば、H の待ち時間はそれら中優先度タスクの実行時間の総和まで膨らみます。L のクリティカルセクションは短くても、待ち時間の上限はL とは無関係な要因で決まってしまう——これが「非有界」と呼ばれる理由です。

優先度継承プロトコル（PIP）

最も広く使われる対策が 優先度継承プロトコル（PIP, Priority Inheritance Protocol） です。規則はこうです。

高優先度 H が、低優先度 L の保持するロック S でブロックしたとき:
  → L の実効優先度を一時的に H まで引き上げる（継承）
L が S を解放したとき:
  → L の実効優先度を、引き上げ前の値（または
    なお待たせている他タスクの最高優先度）に戻す

引き上げられた L は M よりも高い実効優先度を持つため、もはや M にプリエンプトされません。L は速やかにクリティカルセクションを抜けて S を解放し、H が即座に再開します。これにより H のブロック時間は**「L が S を握っている区間の長さ」だけ**に有界化されます。M の数や長さはもう効きません。

PIP の継承は**推移的（transitive）**です。H が L1 を待ち、L1 が L2 の持つ別ロックを待っている場合、H の優先度は L1 を経由して L2 まで伝播します。これがないと L2 が中優先度に止められ、連鎖の根元で逆転が再発します。

PIP の弱点──チェーンブロックとデッドロック

PIP は実装が比較的軽く既存コードへ後付けしやすい反面、2つの弱点があります。

第一に**連鎖ブロック（chained blocking）**です。1つのタスクが n 個のロックを順に取りに行く設計だと、最悪で n 個のクリティカルセクション分だけ待たされ得ます。最悪ブロック時間の解析が、関与するロックとタスクの組み合わせで複雑化します。

第二に PIP はデッドロックを防がない点です。継承は優先度を上げるだけで、ロック獲得順序には介入しません。2タスクが2ロックを逆順に取れば、/os/deadlock/の循環待ちはそのまま成立します。

優先度上限プロトコル（PCP）

これらを構造的に解くのが 優先度上限プロトコル（PCP, Priority Ceiling Protocol） です。各ロックに上限優先度（priority ceiling）——そのロックを使い得る全タスクの中で最高の優先度——を静的に割り当てます。コア規則は次の通りです。

あるタスク T がロックを取得しようとするとき:
  「現在いずれかのタスクが保持中のロックの上限」の
  最高値（システム上限）を見て、
  T の優先度がそれを上回っていなければ取得を許さない
  （= T はブロックされる）
ロック保持中のタスクは、その上限まで実効優先度が上がる

この「自分が要求するロックだけでなく、他者が保持中のロックの上限まで見る」という一手間が効きます。結果として PCP は次の強い性質を持ちます。

• デッドロック防止：上限ルールが循環待ちの成立を構造的に排除する。
• ブロックは高々1回：どのタスクも、実行中に自分より低優先度のタスクのクリティカルセクションに止められるのは最大で1回だけ。連鎖ブロックが消える。

実用上は実装を簡略化した ICPP（Immediate Ceiling Priority Protocol／即時上限） がよく使われ、PTHREAD_PRIO_PROTECT がこれに当たります。ロックを取った瞬間に無条件で上限まで優先度を上げる方式で、判定が単純なうえ単一プロセッサでは標準PCPと同じブロック上界を達成します。

PCP系は強力ですが、上限を正しく与えるには「どのタスクがどのロックを使うか」を設計時に把握する必要があり、動的にロック構成が変わるシステムには向きません。PIP が後付けしやすく現場で多用されるのはこのためです。

Mars Pathfinder の事例

1997年に火星へ着陸した探査機 Mars Pathfinder は、運用中に原因不明のリセットを繰り返しました。原因はまさに非有界の優先度逆転でした。VxWorks上で、共有情報バスを守るミューテックスを、高優先度のバス管理タスクと低優先度の気象データ収集タスクが共有していました。

気象タスク(低) がバスのミューテックスを保持
  → バス管理タスク(高) が同ミューテックスでブロック
  → その間に中優先度の通信タスクが長時間走り、
    気象タスク(低)をプリエンプトし続ける
  → バス管理タスク(高)が規定時間内に動けない
  → ウォッチドッグが「ハングした」と判断しシステムをリセット

復旧は遠隔から行われました。VxWorks のミューテックスは優先度継承をオプションで有効化できる作りで、当該ミューテックス生成時のフラグが継承を無効にしていたのです。地上から該当パラメータを継承ありに書き換えるパッチを送り込み、逆転が解消してリセットは止まりました。

まとめ

• 優先度逆転は、高優先度が低優先度のロックで待つ間に無関係な中優先度が割り込み、順位が事実上引っくり返る現象。待ち時間の上限が中優先度の挙動で決まる非有界逆転が致命的。
• **優先度継承（PIP）**はロック保持者を待ち手の優先度へ動的に引き上げ、待ち時間をクリティカルセクション長で有界化。推移的に伝播するが、連鎖ブロックとデッドロックは残る。
• **優先度上限（PCP/ICPP）**は各ロックに上限を静的に与え、デッドロックを構造的に防ぎブロックを高々1回に抑える。事前のロック構成把握が前提。
• Mars Pathfinderは古典的な非有界逆転の実例で、継承の有効化により復旧した。継承機能の存在ではなく有効化が鍵だった。
• ロックの基礎は/os/concurrency-control/、カーネル側の同期実装は/os/kernel-locking-primitives/も参照。