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

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 priority ceiling of the resource, 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 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

References

  1. Renwick, Kyle; Renwick, Bill (May 18, 2004). "How to use priority inheritance". embedded.com. Retrieved November 11, 2014.
  2. 1 2 3 4 5 6 7 http://rtsys.informatik.uni-kiel.de/teaching/ws08-09/v-emb-rt/lectures/lecture13-handout4.pdf
  3. 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.
  4. http://user.it.uu.se/~yi/courses/rts/dvp-rts-08/notes/synchronization-resource-sharing.pdf
This article is issued from Wikipedia - version of the 6/5/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.