Priority ceiling protocol
In real-time computing, the priority ceiling protocol is a synchronization protocol for shared resources to avoid unbounded priority inversion and mutual deadlock due to wrong nesting of critical sections. In this protocol each resource is assigned a priority ceiling, which is a priority equal to the highest priority of any task which may lock the resource.
For example, with priority ceilings, the shared mutex process (that runs the operating system code) has a characteristic (high) priority of its own, which is assigned to the task locking the mutex. This works well, provided the other high priority task(s) that tries to access the mutex does not have a priority higher than the ceiling priority.
In the Immediate Ceiling Priority Protocol (ICPP) when a task locks the resource its priority is temporarily raised to the priority ceiling of the resource, thus no task that may lock the resource is able to get scheduled. This allows a low priority task to defer execution of higher-priority tasks.
The Original Ceiling Priority Protocol (OCPP) has the same worst-case performance, but is subtly different in the implementation which can provide finer grained priority inheritance control mechanism than ICPP. Under this approach, a task can lock a resource only if its dynamic priority is higher than the current system priority. (The dynamic priority of a task is the maximum of its own static priority and any it inherits due to it blocking higher-priority processes. The system current priority is the ceiling of the resource having the highest ceiling among those locked by other tasks currently.) Otherwise the task is blocked, and its priority is inherited by the task currently holding the resource that gives the current system priority.
ICPP versus OCPP
The worst-case behaviour of the two ceiling schemes is identical from a scheduling view point. However, there are some differences:
- ICPP is easier to implement than OCPP, as blocking relationships need not be monitored
- ICPP leads to fewer context switches as blocking is prior to first execution
- ICPP requires more priority movements as this happens with all resource usage
- OCPP changes priority only if an actual block has occurred
- Alan Burns, 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.
- How to use priority inheritance, by Kyle Renwick and Bill Renwick (2004-05-18)