優先順位の逆転

優先順位逆転の例。
3つのタスク J1, J2, J3 の優先順位は、J1 が最高で J3 が最低。
1. J3 がセマフォ S1 を占有する。その後、より優先順位の高い J1 の実行が始まり、J3 は一時停止する（実行可能状態）。
2. J1 が S1 の解放待ちのためブロック状態となり一次停止する。直ちに J3 の処理が再開されて S1 が解放され、定められた時間内に J1 の処理に戻るのであれば、このブロックは問題にはならない。しかし、図では J3 より優先順位の高いタスク J2 の実行がまず先に開始されている。
3. J2 の実行後、J3 の実行が再開され、S1 が解放される。J1 はこの時点でようやく S1 を占有し、実行を継続できるようになる。
つまり、セマフォ S1 と全く関係の無いタスク J2 が S1 の解放を妨げてしまい、結果としてより優先順位の高い J1 の実行をも妨げている。

計算機科学における優先順位の逆転（ゆうせんじゅんいのぎゃくてん、Priority Inversion）とは、スケジューリングにおいて優先順位の高いタスクが必要としているリソースを優先順位の低いタスクが占有しているときに発生する状態である。

解説

低い優先順位のタスクがそのリソースを解放するまで高い優先順位のタスクが実行をブロックされるため、実質的に二つのタスクの優先順位が逆転する。他の中程度の優先順位のタスクがその途中で動作するなら、そのタスクは高優先順位のタスクと低優先順位のタスクの両方に優先して動作していることになる。

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

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

対策

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

  1. クリティカルセクションを保護するために全ての割り込みを不可とする。
  2. 優先度上限プロトコル
  3. 優先度継承

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

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

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

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

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

注

  1. ^ たいていの場合は運が良い側かもしれないが、それでもそれは「運が良かっただけ」である。

関連項目

外部リンク

いずれも英文