優先度継承

計算機科学における優先度継承（ゆうせんどけいしょう、Priority Inheritance）とは、優先順位の逆転を防ぐ手法の一つである。この手法を用いると、プロセスが獲得済みのリソースが解放されるのを待っている他のプロセス群の最高優先度を現にリソースを獲得しているプロセスに与える。

優先度継承の例。図中の2～3 の間で一時的にジョブJ3の優先度が上げられている。

解説

優先度継承プロトコルの基本的な考え方は、Jというジョブがより高優先度のジョブ群をブロックしているとき、Jが本来の優先度ではなくそれらジョブ群の最高優先度でクリティカルセクションを実行するというものである。クリティカルセクションの実行を終えると、ジョブ J は本来の優先度に戻る。

例えば、J1、J2、J3 というジョブがあり、優先度は J1 が最高、J3 が最低とする。J3 が共有リソースを獲得しているために J1 がブロックされているとする。優先度継承プロトコルは J3 が J1 の優先度でクリティカルセクションを実行することを要求する。結果として、J2 も J3 に先んじて動作することができずブロックされる。つまり、本来優先度の高い J2 が J3 の実行を待たなければならなくなる（J3 が J1 の優先度で動作中であるため）。J3 がクリティカルセクションの実行を終えると、優先度が元に戻され、ブロックされていた J1 が起床する。J1 は最高優先度なので即座に実行権を J3 から奪い、完了まで処理を行う。その後、J2 と J3 がスケジュールされ、完了まで動作する。

本来の優先度継承プロトコルには以下の二つの問題がある。

1. デッドロックを防げない状況がありうる。
2. ブロック化の連鎖が形成される可能性があり、そのブロック期間は有限だがかなり長期化する可能性がある。

外部リンク

• Embedded Systems Material at IIT Bombay（英語）