その日いちばん急ぎの会議を控えたチームリーダーが、会議室の鍵を待っています。ところが鍵を持つ新入社員は、ほかの先輩たちの細かい用事に次々と呼ばれ、なかなか会議室を空けられません。いちばん大事な仕事がいちばん後回しになるこの奇妙な状況は、コンピューターの中でもまったく同じように起こり、「優先度逆転(Priority Inversion)」と呼ばれます。
優先度逆転とは、簡単に言えば「優先度の高いタスクが、優先度の低いタスクが握っている共有資源を待つうちに、事実上さらに低い順位へ押し下げられてしまう現象」を意味します。複数のタスクが決められた優先度に従ってプロセッサーを分け合うリアルタイムシステムで古くから知られる問題で、1997年に火星探査機マーズ・パスファインダー(Mars Pathfinder)が火星で再起動を繰り返す事故を起こしたことで広く知られるようになりました。
本稿では、優先度逆転が起こる過程、三つのタスクで見る仕組み、火星で実際に起きたパスファインダー事件、そしてそれを防ぐ方法と教訓までを順に見ていきます。
高い優先度が低い優先度を待つとき
1. 優先度逆転はどのように起こるのか

優先度スケジューリングでは、実行準備のできたタスクのうち最も優先度の高いものが、常に先にプロセッサーを使います。この単純なルールが揺らぐのは、複数のタスクが同じ資源を共有するときです。
(1)共有資源とロック
複数のタスクが同じメモリーや装置を同時に書き換えると、データが壊れてしまいます。そこでオペレーティングシステムはミューテックス(Mutex)のようなロックを置き、一度に一つのタスクだけが資源を使えるようにします。先にロックを取ったタスクは、優先度に関係なく、仕事を終えてロックを解放するまで資源を独占します。
(2)高優先度タスクの待機
低優先度タスクがロックを握っているときに高優先度タスクが同じ資源を求めると、高優先度タスクはロックが解放されるまで止まらなければなりません。低優先度タスクが短いクリティカルセクションを終えればすぐに解放されるため、この程度の待ちはあらかじめ計算できる「有界な逆転」です。
(3)中優先度タスクの割り込み
本当の問題は、その間にロックと関係のない中優先度タスクが目を覚ましたときに起こります。中優先度タスクは低優先度タスクより優先度が高いのでプロセッサーを奪い、低優先度タスクはロックを握ったまま止まります。結局、高優先度タスクは自分より優先度の低い中優先度タスクが終わるまで待つことになり、中優先度タスクが多ければ待ち時間は際限なく延びていきます。
2. 三つのタスクで見る仕組み

優先度逆転は、ふつう高・中・低の三つのタスクで説明します。優先度だけを見れば高優先度タスクが最初に終わるはずですが、ロックが一つ絡むだけで実際の実行順序がひっくり返ります。

- 優先度スケジューリング(Priority Scheduling):タスクごとに優先度を付け、実行準備のできたタスクのうち最も優先度の高いものから処理する方式です。高優先度タスクが目を覚ますと、低優先度タスクを止めてプロセッサーを引き継ぎます。
- ミューテックス(Mutex):相互排除(Mutual Exclusion)を縮めた言葉で、一度に一つのタスクだけが共有資源を使えるようにするロックです。
- クリティカルセクション(Critical Section):ロックを握ったまま共有資源を扱うコードの区間です。短いほど、ほかのタスクが待つ時間も短くなります。
- 有界な逆転と無界な逆転(Bounded and Unbounded Inversion):高優先度タスクが低優先度タスクのクリティカルセクションの分だけ待つなら有界な逆転、中優先度タスクまで割り込んで待ち時間の上限が決められなくなれば無界な逆転といいます。
リアルタイムシステムで恐ろしいのは無界な逆転です。決められた時間内に必ず終わらなければならないタスクが、いつ終わるのか分からなくなるからです。見た目にはすべてのタスクがルールどおり優先度を守っているのに、全体の結果は優先度がひっくり返ったように現れる点が、この問題を見つけにくくしています。
3. 火星で起きたパスファインダー事件

優先度逆転を世界に最も広く知らせた出来事は、火星で起こりました。1997年7月4日に火星に降り立ったアメリカ航空宇宙局(NASA)のマーズ・パスファインダーは、着陸の数日後からシステム全体が突然再起動する問題に見舞われました。
(1)繰り返す再起動
パスファインダーのコンピューターは、ウインドリバー(Wind River Systems)のリアルタイムOS、VxWorksで動いていました。問題は、探査機が気象データを集め始めたころから現れました。再起動が起こるとその日に予定していた作業が翌日に持ち越されるため、地球の運用チームは急いで原因を突き止める必要がありました。
(2)地球で再現した原因
ジェット推進研究所(JPL)のチームは、地球の試験装置で記録機能をオンにしたまま同じ状況を走らせ、18時間足らずで再起動をもう一度起こすことに成功しました。原因は教科書どおりの優先度逆転でした。低優先度の気象データタスクがロックを握っている間に中優先度タスクが実行され、そのロックを待っていた高優先度の情報バス管理タスクが決められた周期内に終われなかったのです。これを見つけた上位の管理タスクが深刻なエラーと判断し、再起動を起こしたのでした。
(3)グローバル変数一つで直した遠隔修正
問題のロックは、性能上の理由から優先度継承機能がオフになった既定の設定で作られていました。チームはこの機能をオンにするためにグローバル変数一つの値を変える修正を火星の探査機へ送り、問題を解決しました。この件は同じ年の12月にリアルタイムシステムの学会で紹介されて広く知られ、飛行ソフトウェアの責任者グレン・リーブス(Glenn Reeves)も自ら経緯を説明しました。
4. 優先度逆転を防ぐ方法

ロックを使う限り優先度逆転を完全になくすことは難しいものの、待ち時間が際限なく延びることは防げます。代表的な解決策は、1990年にLui Sha、Ragunathan Rajkumar、John Lehoczkyが発表した優先度継承プロトコル(Priority Inheritance Protocols)の論文にまとめられています。
(1)優先度継承
高優先度タスクがロックを待ち始めたら、ロックを握る低優先度タスクの優先度を一時的に高優先度タスクと同じにまで上げます。すると中優先度タスクは割り込めず、低優先度タスクはクリティカルセクションをすばやく終え、ロックを解放するとすぐ元の優先度に戻ります。パスファインダーを救ったのがまさにこの方法です。
(2)優先度上限プロトコル
ロックごとに、そのロックを使う可能性のあるタスクのうち最も高い優先度を「上限」として決めておく方式です。同じ論文で提案されたこの方法は、最大の待ち時間をあらかじめ計算できるようにし、ロック同士が互いにかみ合って止まってしまうデッドロックも防ぎます。
(3)設計から得られる教訓
ロックを握る区間を短くし、優先度の大きく異なるタスクが同じ資源を共有しないように設計することも大切です。今日では多くのリアルタイムOSやLinuxも、優先度継承に対応したロックを提供しています。パスファインダーの事例は、既定の設定を一つ確かめることや、問題を再現できる記録機能を残しておくことがどれほど重要かも示しています。
「急ぎの仕事をふさいでいる遅い仕事を少し後押しして、先に終わらせる」という単純な考え、それが優先度逆転を理解する第一歩です。