優先度上限プロトコル

ウィキペディア

優先度上限プロトコル

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2012/07/17 06:26 UTC 版)

優先度上限プロトコル（ゆうせんどじょうげんプロトコル、Priority Ceiling Protocol）とは、クリティカルセクションの間違った入れ子によって生じる優先順位の逆転によるデッドロックを防ぐための共有資源の同期プロトコルである。このプロトコルでは、各資源には優先度上限が割り当てられており、それはその資源をロックしたタスクの持ちうる最高の優先度である。

優先度上限があるとき、例えば排他を行うプロセスはミューテックスをロックした際に割り当てられた（高い）優先度で動作する。そうするとそのミューテックスを確保できていない他のタスクはその優先度上限より高い優先度を持たないので、ミューテックスをロックしたタスクが邪魔されずにスムーズに動作できるという利点がある。

Immediate Ceiling Priority Protocol (ICPP) の場合、あるタスクが資源をロックすると、優先度は一時的にその資源の優先度上限まで上げられるので、その資源をロックしようとする他のタスクがスケジュールされることがなくなる。これにより低優先度タスクが高優先度タスクに先んじて動作可能となる。

Original Ceiling Priority Protocol (OCPP) も最悪の場合の性能は同程度だが、ICPPに比較して粒度の細かい優先度継承機構を実装できる点が微妙に異なる。この場合、タスクの動的優先度が現在のシステム優先度より高いときだけ資源をロックすることができる（タスクの動的優先度とは自身の静的優先度の最大値であり、そのプロセスがブロックしている高優先度のプロセスの優先度を継承したものでもある。現在のシステム優先度とは、他のタスクがロックしている資源の持つ優先度上限の最大値である）。さもなくば、タスクはブロックされ、その優先度は問題の資源をその時点で保持しているタスクが継承し、それによって現在のシステム優先度が決まる。

ICPP はAdaでは "Ceiling Locking"、POSIXでは "Priority Protect Protocol"、RTSJでは "Priority Ceiling Emulation" と呼ばれている。また、"Highest Locker's Priority Protocol" (HLP) とも呼ばれている。

現に他のタスクがロック中の資源をロックしようとしているタスクは決してスケジュールされないので、優先度上限プロトコルはデッドロックを防ぐことができる。

ICPP と OCPP の比較

最悪の場合のこれら2つの手法の振る舞いは、スケジューリングの観点から見れば同じである。しかし、以下のような差異がある。

• ICCP は OCPP よりも実装が容易であり、ブロック関係を気にする必要がない。
• ICPP は実行する以前にブロックするので、コンテキストスイッチ回数が少なくなる傾向がある。
• ICPP では資源を使用する度に優先度が変更されるので、優先度更新が頻繁になる。
• OCPP は実際のブロックが発生するときだけ優先度を変更する。

外部リンク

• How to use priority inheritance, by Kyle Renwick and Bill Renwick (2004-05-18)