優先度上限プロトコル

リアルタイムコンピューティングにおいて、優先度上限プロトコルは、クリティカルセクションの誤ったネストによる無制限の優先度逆転や相互デッドロックを回避するための共有リソースの同期プロトコルです。このプロトコルでは、各リソースに優先度上限が割り当てられます。優先度上限は、リソースをロックする可能性のあるタスクの最高優先度に等しい優先度です。このプロトコルは、特定の状況でタスクの優先度を一時的に上げることで機能するため、動的優先度スケジューリングをサポートするスケジューラが必要です。^[1]

このプロトコルには、 オリジナル上限優先度プロトコル（OCPP）と即時上限優先度プロトコル（ICPP）の2つのバリエーションがあります。2つの上限スキームの最悪のケースの動作は、スケジュールの観点からは同じです。どちらのバリエーションも、タスクの優先度を一時的に上げることによって機能します。^[2]

OCPP では、タスク X の優先度は、より優先度の高いタスク Y が X がロックしたリソースを取得しようとすると上がります。その後、タスクの優先度は、自身でブロックされていた最高の優先度に上がり、タスク X がクリティカル セクションを迅速に終了してリソースのロックを解除できるようにします。タスクは、その動的優先度が他のタスクによってロックされているすべてのリソースの優先度上限よりも高い場合にのみ、リソースをロックできます。そうでない場合、タスクはブロックされ、リソースを待機します。^[2]

ICPP では、タスクがリソースをロックすると、そのタスクの優先度が即座に上がります。タスクの優先度はリソースの優先度上限に設定されるため、リソースをロックする可能性のあるタスクはスケジュールされません。これにより、「タスクは、その動的優先度が他のタスクによってロックされているすべてのリソースの優先度上限よりも高い場合にのみ、リソースをロックできる」という OCPP プロパティが保証されます。^[2]

• ICPPはOCPPよりも実装が容易であり、ブロッキング関係を監視する必要がないため^[2]
• ICPPでは最初の実行前にブロッキングが行われるため、コンテキストスイッチが少なくなります^[2]
• ICPPはすべてのリソースの使用で発生するため、より優先的な移動が必要となる^[2]
• OCPPは実際にブロックが発生した場合にのみ優先度を変更する^[2]

ICPPは、 Adaでは「Ceiling Locking」 、 POSIXでは「Priority Protect Protocol」 、 RTSJでは「Priority Ceiling Emulation」と呼ばれています。^[3] また、「Highest Locker's Priority Protocol」（HLP）としても知られています。^[4]

• 優先権継承

• Lui Sha、Ragunathan Rajkumar、John P. Lehoczky (1990年9 月)。「優先度継承プロトコル: リアルタイム同期へのアプローチ」( PDF)。IEEE Transactions on Computers。39 ( 9): 1175–1185。doi :10.1109/12.57058。