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.
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.
Other articles related to "priority ceiling protocol, ceiling, priority, protocol":
... The worst-case behaviour of the two ceiling schemes is identical from a scheduling view point ... leads to less context switches as blocking is prior to first execution ICPP requires more priority movements as this happens with all resource usage OCPP changes ...
... Examples of priority inheritance algorithms include (from simplest to most complex) http//rt.wiki.kernel.org/index.php/Main_Page contains an implementation of this algorithm which is a ... This method does not prevent deadlocks, but does prevent priority inversion ... The highest locker protocol which requires off-line analysis of all task conflicts to find a "ceiling priority" The priority ceiling protocol which is an enhancement of basic priority inheritance ...
Famous quotes containing the words priority and/or ceiling:
“Weekend planning is a prime time to apply the Deathbed Priority Test: On your deathbed, will you wish youd spent more prime weekend hours grocery shopping or walking in the woods with your kids?”
—Louise Lague (20th century)
“Spooky things happen in houses densely occupied by adolescent boys. When I checked out a four-inch dent in the living room ceiling one afternoon, even the kid still holding the baseball bat looked genuinely baffled about how he possibly could have done it.”
—Mary Kay Blakely (20th century)