優先度上限プロトコル
優先度上限プロトコル（ゆうせんどじょうげんプロトコル、Priority Ceiling Protocol）とは、クリティカルセクションの間違った入れ子によって生じる優先順位の逆転によるデッドロックを防ぐための共有資源の同期プロトコルである。このプロトコルでは、各資源には優先度上限が割り当てられており、それはその資源をロックしたタスクの持ちうる最高の優先度である[1]。
優先度上限があるとき、例えば排他を行うプロセスはミューテックスをロックした際に割り当てられた（高い）優先度で動作する。そうするとそのミューテックスを確保できていない他のタスクはその優先度上限より高い優先度を持たないので、ミューテックスをロックしたタスクが邪魔されずにスムーズに動作できるという利点がある。
Immediate Ceiling Priority Protocol (ICPP) の場合、あるタスクが資源をロックすると、優先度は一時的にその資源の優先度上限まで上げられるので、その資源をロックしようとする他のタスクがスケジュールされることがなくなる。これにより低優先度タスクが高優先度タスクに先んじて動作可能となる。
Original Ceiling Priority Protocol (OCPP) も最悪の場合の性能は同程度だが、ICPPに比較して粒度の細かい優先度継承機構を実装できる点が微妙に異なる。この場合、タスクの動的優先度が現在のシステム優先度より高いときだけ資源をロックすることができる（タスクの動的優先度とは自身の静的優先度の最大値であり、そのプロセスがブロックしている高優先度のプロセスの優先度を継承したものでもある。現在のシステム優先度とは、他のタスクがロックしている資源の持つ優先度上限の最大値である）。さもなくば、タスクはブロックされ、その優先度は問題の資源をその時点で保持しているタスクが継承し、それによって現在のシステム優先度が決まる。
ICPP はAdaでは "Ceiling Locking"、POSIXでは "Priority Protect Protocol"、RTSJでは "Priority Ceiling Emulation" と呼ばれている[2]。また、"Highest Locker's Priority Protocol" (HLP) とも呼ばれている[3]。
現に他のタスクがロック中の資源をロックしようとしているタスクは決してスケジュールされないので、優先度上限プロトコルはデッドロックを防ぐことができる。
ICPP と OCPP の比較[編集]
最悪の場合のこれら2つの手法の振る舞いは、スケジューリングの観点から見れば同じである。しかし、以下のような差異がある[4]。
- ICCP は OCPP よりも実装が容易であり、ブロック関係を気にする必要がない。
- ICPP は実行する以前にブロックするので、コンテキストスイッチ回数が少なくなる傾向がある。
- ICPP では資源を使用する度に優先度が変更されるので、優先度更新が頻繁になる。
- OCPP は実際のブロックが発生するときだけ優先度を変更する。
脚注[編集]
- ^ Lui Sha, Ragunathan Rajkumar, and John P. Lehoczky (September 1990). “Priority Inheritance Protocols: An Approach to Real-Time Synchronization”. IEEE Transactions on Computers 39 (9): 1175–1185. doi:10.1109/12.57058. ISSN 0018-9340.
- ^ Alan Burns, and Andy Wellings (March 2001). Real-Time Systems and Programming Languages — Ada 95, Real-Time Java and Real-Time POSIX (3rd ed.). Addison Wesley Longmain. ISBN 0-201-72988-1
- ^ Priority Ceiling Protocols
- ^ RTOS Scheduling - I: Rate-Monotonic Theory
外部リンク[編集]
- How to use priority inheritance, by Kyle Renwick and Bill Renwick (2004-05-18)
 | この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。 |