優先順位の逆転

出典: フリー百科事典『ウィキペディア（Wikipedia）』

優先順位逆転の例。優先順位の低いタスクJ3 がセマフォS1を占有しているため、優先順位の高いタスクJ1 の実行がブロックされ、2～3の区間においてJ1より優先順位の低いタスクJ2, J3が先に動作している。

優先順位の逆転（Priority Inversion）とは、スケジューリングにおいて優先順位の低いタスクが優先順位の高いタスクが必要としているリソースを共有しているときに発生する状態である。低い優先順位のタスクがそのリソースを解放するまで高い優先順位のタスクが実行をブロックされるため、実質的に二つのタスクの優先順位が逆転する。他の中程度の優先順位のタスクがその途中で動作するなら、そのタスクは高優先順位のタスクと低優先順位のタスクの両方に優先して動作していることになる。

多くの場合、優先順位の逆転は直接的な被害を引き起こさない。優先順位の高いタスクの遅延に気づく前に低優先順位のタスクがリソースを解放することになる。しかし、同時に優先順位の逆転が深刻な問題の原因となる状況も多々ある。もし高優先順位のタスクがリソーススタベーションの原因となっているのにブロックされているなら、システム全体の誤動作を引き起こすかもしれないし、事前に定義された矯正手段（例えば、ウォッチドッグタイマによるシステム全体のリセット）の引き金となる可能性もある。火星探査船「マーズ・パスファインダー」で発生した問題は、リアルタイムシステムでの優先順位の逆転が引き起こした典型的な例である（「外部リンク」参照）。

優先順位の逆転はシステムの見た目の性能も低下させる。低優先順位のタスクは迅速に処理しなくてもよいから低優先順位に設定されている（例えば、それはバッチ処理かもしれないし、他の非対話型処理かもしれない）。同様に、高優先順位のタスクは時間的制限が問題となるから高優先順位に設定される。対話的にユーザーにデータを提供している場合もあるし、何らかのリアルタイムな応答を保証した処理をしているかもしれない。優先順位の逆転は低優先順位のタスクが高優先順位のタスクをブロックしてしまうので、システムの応答性能の低下を招き、保証された応答性能の違反となる可能性もある。

この問題は1970年代から知られているが、この状況を予測する確実な方法はない。様々な解決策は存在している。最も一般的な解決策は次のようなものである。

割り込みを不可にして優先順位の逆転を防ぐことができる場合、preemptible と interrupts disabled の二つの優先順位しかない。それ以外の優先順位がない場合、逆転は不可能となる。ひとつしかロックデータ（割り込み可能ビット）がないので、ロックの順番間違いも起きないし、デッドロックも発生しない。クリティカルセクションは常に最後まで実行されるので、ハングアップも発生しない。これは全割り込みを不可にした場合のみ有効であることに注意されたい。特定のハードウェア割り込みのみ不可にしたとしても、優先順位の逆転は防げない。

簡単なバリエーションとして、「単一の共有フラグロック」を複数CPUシステムで使用することがある。これは、共有メモリ上にひとつのフラグを用意して、全CPUについてプロセッサ間のクリティカルセクションをビジーウェイトでロックするものである。プロセッサ間通信は多くの複数CPUシステムでコストが高く低速である。従って、そのようなシステムではリソースの共有を極力しないよう設計している。結果として、素朴な方法であっても多くの実用システムでこれがうまく動作しているのである。

このような単純な手法は単純な組み込みシステムで広く使われている。組み込みシステムは信頼性、単純さ、リソースをなるべく使わないといった点が特徴である。これらの手法はクリティカルセクションが（例えば100μ秒以内などの）一定時間以内に終わるよう精密にプログラミングすることを要求する。汎用のコンピュータのソフトウェア技術者にとって、それは全く現実的な条件ではない。

このような手法は優先度上限プロトコル(Priority Ceiling Protocol)と似ている。優先度上限プロトコルでは、共有されたミューテックスプロセス（オペレーティングシステムのコードを実行する）が固有の（高い）優先度を持っている。そしてミューテックスをロックする処理はそのプロセスが行う。ミューテックスにアクセスしようとする他のタスクが上限優先度より高い優先度を持っていない限り、この方式はうまく機能する。

優先度継承(Priority Inheritance)では、低優先度タスクが高優先度タスクの優先度を継承する。それによって中程度の優先度のタスクが低優先度タスクに先立って動作することを防ぐ。これにはオペレーティングシステムの特殊な設計を要する。