Priority ceiling protocol

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[citation needed]. In this protocol each resource is assigned a priority ceiling[citation needed], which is a priority equal to the highest priority of any task which may lock the resource[citation needed].

For example, with priority ceilings, the shared mutex process (that runs the operating system code) has a characteristic (high) priority of its own[citation needed], which is assigned to the task locking the mutex. This works well[citation needed], provided the other high priority task(s) that tries to access the mutex does not have a priority higher than the ceiling priority[citation needed].

In the Immediate Ceiling Priority Protocol (ICPP)[citation needed] when a task locks the resource its priority is temporarily raised to the priority ceiling of the resource[citation needed], 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[citation needed].

The Original Ceiling Priority Protocol (OCPP)[citation needed] has the same worst-case performance[citation needed], but is subtly different in the implementation which can provide finer grained priority inheritance control mechanism than ICPP[citation needed]. 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[citation needed]. The system current priority is the ceiling[citation needed] 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[citation needed].

A task will not get scheduled if any resource it may lock actually has been locked by another task, and therefore the priority ceiling protocol prevents deadlocks[citation needed].

ICPP is called "Ceiling Locking" in Ada, "Priority Protect Protocol" in POSIX and "Priority Ceiling Emulation" in RTSJ. [1] It is also known as "Highest Locker's Priority Protocol" (HLP). [2]

ICPP versus OCPP[edit]

The worst-case behaviour of the two ceiling schemes is identical from a scheduling view point. However, there are some differences:[3]

  • ICPP is easier to implement than OCPP, as blocking relationships need not be monitored[citation needed]
  • ICPP leads to fewer context switches as blocking is prior to first execution[citation needed]
  • ICPP requires more priority movements as this happens with all resource usage[citation needed]
  • OCPP changes priority only if an actual block has occurred[citation needed]

See also[edit]

References[edit]

  1. ^ 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. 
  2. ^ http://user.it.uu.se/~yi/courses/rts/dvp-rts-08/notes/synchronization-resource-sharing.pdf
  3. ^ http://rtsys.informatik.uni-kiel.de/teaching/ss05/v-rt2/lectures/lecture13-handout4.pdf

External links[edit]