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.<ref> {{#invoke:citation/CS1|citation |CitationClass=web }}</ref>
ICPP versus OCPPEdit
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.<ref name="informatik">{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>
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.<ref name="informatik"/>
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".<ref name="informatik"/>
- ICPP is easier to implement than OCPP, as blocking relationships need not be monitored<ref name="informatik"/>
- ICPP leads to fewer context switches as blocking is prior to first execution<ref name="informatik"/>
- ICPP requires more priority movements as this happens with all resource usage<ref name="informatik"/>
- OCPP changes priority only if an actual block has occurred<ref name="informatik"/>
ICPP is called "Ceiling Locking" in Ada, "Priority Protect Protocol" in POSIX and "Priority Ceiling Emulation" in RTSJ.<ref name="burns2001">Template:Cite book</ref> It is also known as "Highest Locker's Priority Protocol" (HLP).<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>
See alsoEdit
ReferencesEdit
<references/>