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. The protocol works by temporarily raising the priorities of tasks in certain situations, thus it requires a scheduler that supports dynamic priority scheduling.[1]
ICPP versus OCPP
[edit]There are two variants of the protocol: Original Ceiling Priority Protocol (OCPP) and Immediate Ceiling Priority Protocol (ICPP). The worst-case behaviour of the two ceiling schemes is identical from a scheduling view point. Both variants work by temporarily raising the priorities of tasks.[2]
In OCPP, a task X's priority is raised when a higher-priority task Y tries to acquire a resource that X has locked. The task's priority is then raised to the highest priority had been blocked by itself, ensuring that task X quickly finishes its critical section, unlocking the resource. A task is only allowed to lock a resource if its dynamic priority is higher than the priority ceilings of all resources locked by other tasks. Otherwise the task becomes blocked, waiting for the resource.[2]
In ICPP, a task's priority is immediately raised when it locks a resource. The task's priority is set to the priority ceiling of the resource, thus no task that may lock the resource is able to get scheduled. This ensures the OCPP property that "A task can only lock a resource if its dynamic priority is higher than the priority ceilings of all resources locked by other tasks".[2]
- ICPP is easier to implement than OCPP, as blocking relationships need not be monitored[2]
- ICPP leads to fewer context switches as blocking is prior to first execution[2]
- ICPP requires more priority movements as this happens with all resource usage[2]
- OCPP changes priority only if an actual block has occurred[2]
ICPP is called "Ceiling Locking" in Ada, "Priority Protect Protocol" in POSIX and "Priority Ceiling Emulation" in RTSJ.[3] It is also known as "Highest Locker's Priority Protocol" (HLP).[4]
See also
[edit]References
[edit]- Lui Sha; Ragunathan Rajkumar & John P. Lehoczky (September 1990). "Priority Inheritance Protocols: An Approach to Real-Time Synchronization" (PDF). IEEE Transactions on Computers. 39 (9): 1175–1185. doi:10.1109/12.57058.
- ^ Renwick, Kyle; Renwick, Bill (May 18, 2004). "How to use priority inheritance". embedded.com. Retrieved November 11, 2014.
- ^ a b c d e f g "Archived copy" (PDF). Archived from the original (PDF) on 2014-11-13. Retrieved 2014-11-13.
{{cite web}}: CS1 maint: archived copy as title (link) - ^ 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.
- ^ http://user.it.uu.se/~yi/courses/rts/dvp-rts-08/notes/synchronization-resource-sharing.pdf [bare URL PDF]