Priority ceiling protocol
Encyclopedia
In real-time computing
, the priority ceiling protocol is a synchronization protocol for shared resource
s 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.
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 deadlock
s.
ICPP is called "Priority Protect Protocol" in POSIX
and "Priority Ceiling Emulation" in RTSJ.
Real-time computing
In computer science, real-time computing , or reactive computing, is the study of hardware and software systems that are subject to a "real-time constraint"— e.g. operational deadlines from event to system response. Real-time programs must guarantee response within strict time constraints...
, the priority ceiling protocol is a synchronization protocol for shared resource
Resource (computer science)
A resource, or system resource, is any physical or virtual component of limited availability within a computer system. Every device connected to a computer system is a resource. Every internal system component is a resource...
s to avoid unbounded priority inversion
Priority inversion
In computer science, priority inversion is a problematic scenario in scheduling when a higher priority task is indirectly preempted by a lower priority task effectively "inverting" the relative priorities of the two tasks....
and mutual deadlock due to wrong nesting of critical sections. In this protocol each resource is assigned a priority ceiling, which is a priority
Priority
Priority may refer to:* Priority date, a concept of establishing waiting times in the immigration process by United States Department of State* Priority level, the priority of emergency communications...
equal to the highest priority of any task
Task (computers)
A task is an execution path through address space. In other words, a set of program instructions that are loaded in memory. The address registers have been loaded with the initial address of the program. At the next clock cycle, the CPU will start execution, in accord with the program. The sense is...
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
Priority inheritance
In real-time computing, priority inheritance is a method for eliminating priority inversion problems. Using this programming method, a process scheduling algorithm will increase the priority of a process to the maximum priority of any process waiting for any resource on which the process has a...
control mechanism than ICPP.
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 deadlock
Deadlock
A deadlock is a situation where in two or more competing actions are each waiting for the other to finish, and thus neither ever does. It is often seen in a paradox like the "chicken or the egg"...
s.
ICPP is called "Priority Protect Protocol" in POSIX
POSIX
POSIX , an acronym for "Portable Operating System Interface", is a family of standards specified by the IEEE for maintaining compatibility between operating systems...
and "Priority Ceiling Emulation" in RTSJ.
External links
- How to use priority inheritance, by Kyle Renwick and Bill Renwick (2004-05-18)