険しい「北一山脈」の奥深くに、その名を聞くだけで身の毛がよだつ垂直の岩壁があり、「砕骨崖」と呼ばれていました。安全を確保するため、山脈管理事務所は岩壁にただ一本の安全ロープを打ち込んでいます。この壁を登るルールは非常に厳格です。どのクライマーも、自分の確保器（一般的な ATC など）をこのロープにクリップしなければ登ることができず、しかもロープは同時に一人分の体重しか支えられません。
つまり、誰かがロープにクリップしている間は、他の全員が崖の下で待たなければならないのです。ある朝早く、動作が遅く重装備を背負った初心者クライマー（李くん）が崖の下にやって来ました。彼は自分の ATC 確保器をロープにクリップし、きわめてゆっくりとした登攀を始めます。まだ半分ほど登ったところで、崖の下に突然「山岳特殊救助隊」が駆け込んできました。山頂で深刻な雪崩が発生し、彼らは命を救うという最高の使命を帯び、山脈全体に対する「絶対的な最優先通行権」を持っていました。しかし、規則は規則です。李くんがすでにロープ上にいるため、救助隊はどれほど急いでいても、崖の下で李くんが登り終えるのを焦りながら待つほかありませんでした。もどかしいけれど、これは至極まっとうなことです。
ところが、致命的な危機が現れました。このとき、一団の「商業観光ツアー客」が、そばのなだらかな横断分岐路からやって来たのです。この分岐路にはロープは不要ですが、空中で李くんの登攀ルートと頻繁に交差します。山脈の副次的な通行権規定によれば、商業観光ツアーの通行権は、単独の初心者クライマーよりも上位です。こうして、不条理な光景が繰り広げられました。観光ツアーが交差点にさしかかるたびに、李くんは動作を止め、岩壁にぴたりと張りつき、談笑するこの観光客の一団に道を譲らなければならなかったのです。ツアー客は人数が多く、次から次へとやって来ます。李くんはこうして空中に閉じ込められ、一歩も動けなくなりました。李くんが前進できない以上、ロープにクリップした ATC 確保器を外すこともできません。ロープが占有され続けるため、「絶対的な最優先通行権」を持つ崖下の救助隊は、そのまま下でがっちりと足止めを食らってしまったのです。
これは恐ろしいパラドックスでした。中程度の優先度しか持たない観光客の一団が、実質的に最高優先度の救助活動を阻んでしまったのです！山全体のルールシステムが完全に崩壊しました。
まさにこの生死の分かれ目で、救助隊長はこのシステムの欠陥を見抜きました。彼は空中の李くんに向かって叫びます。「聞け！私はいま特殊救助隊長として、お前を臨時に救助隊の一員として召集する！この隊章を受け取れ！」この宣言は絶大な効果を発揮しました。李くんは突如「絶対的な最優先通行権」を手にしたのです。観光ツアーは、李くんが特殊隊を代表していると見るや、たちまち怯えて分岐路へ引き返し、道を空けました。もう妨げるものはなく、李くんは残りの壁を素早く登りきり、ATC を外しました。ロープが空くやいなや、救助隊はただちに確保器をクリップし、平地を行くように山頂へ駆け上がり、悲劇を未然に防いだのです。
種明かし：優先度逆転 (Priority Inversion) と 優先度継承 (Priority Inheritance)
この物語が語っているのは、コンピュータサイエンス、とりわけリアルタイムOS (RTOS, Real-Time Operating System) の分野におけるきわめて古典的な大学院レベルの概念、優先度逆転 (Priority Inversion) です。組み込みシステム（FreeRTOS、Zephyr、あるいは Linux カーネルのスケジューラなど）に触れたことがあれば、システム内では重要度の異なる複数のタスク (Task) が同時に走っていることをご存じでしょう。複数のタスクが同じリソース（ハードウェアデバイスやメモリ領域など）を共有する必要があるとき、私たちは同時に一つのタスクだけがそれを使えるように「ミューテックス (Mutex)」を用いなければなりません。
物語の状況は、1997年に米国 NASA の「マーズ・パスファインダー (Mars Pathfinder)」がミッション失敗寸前まで追い込まれた実在のバグを完璧に再現しています。低優先度タスク（李くん）がミューテックス（ロープ）を取得したところに、高優先度タスク（救助隊）もそのロックを必要とし、高優先度タスクはやむなくスリープして待機します。ところがそこへ、そのロックを必要としない中優先度タスク（観光ツアー）が目を覚まします。中優先度タスクはスケジューリング上、低優先度タスクより上位であるため、CPU リソースを横取り (Preempt) してしまいます。結果として低優先度タスクは実行できず、永遠にミューテックスを解放できません。そのため高優先度タスクは永久に固まってしまうのです。これが有名な「優先度逆転」です。
そして救助隊長が叫んだあの一手こそ、この問題を解決する標準的な手法、優先度継承プロトコル (Priority Inheritance Protocol, PIP) です。オペレーティングシステムは、高優先度タスクが低優先度タスクの持つロックによって足止めされていることを検知すると、「低優先度タスクの優先度を、一時的に高優先度タスクと同じ水準まで引き上げ」ます。こうすれば中優先度タスクはもう割り込めなくなり、低優先度タスクは可能な限り速やかに実行を終えてロックを解放し、システムは正常に戻るのです。
物語のメタファー対応表
| 物語の要素 | RTOS / OS の概念 | 説明 |
|---|---|---|
| 唯一の安全ロープ | ミューテックス / 共有リソース (Mutex / Shared Resource) | 同時に一つのスレッドだけがアクセスを許されるシステムリソース。 |
| ATC 確保器をロープにクリップする | ロックの取得 (Acquire Lock) | タスクがミューテックスの占有に成功し、クリティカルセクションに入る。 |
| 初心者クライマー李くん | 低優先度タスク (Low Priority Task, $L$) | 共有リソースを使用中だが、実行権限自体は低いタスク。 |
| 特殊救助隊 | 高優先度タスク (High Priority Task, $H$) | システム内で最も緊急なのに、ロックを $L$ に奪われて阻塞 (Blocked) させられるタスク。 |
| 商業観光ツアー | 中優先度タスク (Medium Priority Task, $M$) | ミューテックスは不要だが、優先度が $L$ より高く $H$ より低いタスク。 |
| 観光ツアーが李くんに道を譲らせる | タスクの横取り (Preemption) | $M$ が $L$ より優先度が高いため、$L$ の CPU 実行権を奪う。 |
| 救助隊長が隊章を投げる | 優先度継承 (Priority Inheritance) | システムが $L$ の優先度を一時的に $H$ の水準まで引き上げ、$M$ による CPU の横取りを防ぎ、$L$ が一刻も早くロックを解放できるようにする。 |