Editing Priority ceiling protocol

In [[real-time computing]], the '''priority ceiling protocol''' is a synchronization protocol for [[resource (computer science)|shared resource]]s to avoid unbounded [[priority inversion]] and mutual [[Deadlock (computer science)|deadlock]] due to wrong nesting of [[critical section]]s. In this protocol each resource is assigned a priority ceiling, which is a [[:wikt:priority|priority]] equal to the highest priority of any [[task (computers)|task]] which may lock the resource. The protocol works by temporarily raising the priorities of tasks in certain situations, thus it requires a [[Scheduling (computing)|scheduler]] that supports [[dynamic priority scheduling]].<ref>
{{cite web
 | last = Renwick
 | first = Kyle
 | authorlink =
 | last2 = Renwick
 | first2 = Bill
 | title = How to use priority inheritance
 | publisher = embedded.com
 | date = May 18, 2004
 | url = http://www.embedded.com/design/configurable-systems/4024970/How-to-use-priority-inheritance
 | accessdate = November 11, 2014}}</ref>

== 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.<ref name="informatik">{{Cite web| url=http://rtsys.informatik.uni-kiel.de/teaching/ws08-09/v-emb-rt/lectures/lecture13-handout4.pdf | title=Embedded Real-Time Systems—Lecture 13 | accessdate=2014-11-13 | url-status=dead | archiveurl=https://web.archive.org/web/20141113091626/http://rtsys.informatik.uni-kiel.de/teaching/ws08-09/v-emb-rt/lectures/lecture13-handout4.pdf | archivedate=2014-11-13}}</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 (programming language)|Ada]], "Priority Protect Protocol" in [[POSIX]] and "Priority Ceiling Emulation" in [[Real-time specification for Java|RTSJ]].<ref name="burns2001">{{cite book
|title = Real-Time Systems and Programming Languages &mdash; Ada&nbsp;95, Real-Time Java and Real-Time POSIX
|date=March 2001
|edition = 3rd
|publisher = Addison Wesley Longmain
|isbn = 0-201-72988-1
|author1=Alan Burns
|author2=Andy Wellings
|authorlink1=Alan Burns (professor)
|authorlink2=Andy Wellings
}}</ref>
It is also known as "Highest Locker's Priority Protocol" (HLP).<ref>{{Cite web| title=Priority Ceiling Protocols | url=http://user.it.uu.se/~yi/courses/rts/dvp-rts-08/notes/synchronization-resource-sharing.pdf | archive-url=https://web.archive.org/web/20130418081832/http://user.it.uu.se:80/~yi/courses/rts/dvp-rts-08/notes/synchronization-resource-sharing.pdf | archive-date=2013-04-18}}</ref>

==See also==
*[[Priority inheritance]]

== References ==
* {{cite journal |author1=Lui Sha |author2=Ragunathan Rajkumar |author2-link=Ragunathan Rajkumar |author3=John P. Lehoczky |author3-link=John Lehoczky |name-list-style=amp |date=September 1990 |title=Priority Inheritance Protocols: An Approach to Real-Time Synchronization |journal=[[IEEE Transactions on Computers]] |volume=39 |issue=9 |pages=1175&ndash;1185 |url=http://www.csie.ntu.edu.tw/~r95093/papers/Priority%20Inheritance%20Protocols%20An%20Approach%20to%20Real-Time%20Synchronization.pdf |doi=10.1109/12.57058 |access-date=2014-11-13 |archive-date=2016-07-29 |archive-url=https://web.archive.org/web/20160729211417/http://www.csie.ntu.edu.tw/~r95093/papers/Priority%20Inheritance%20Protocols%20An%20Approach%20to%20Real-Time%20Synchronization.pdf |url-status=dead }}
<references/>

[[Category:Real-time computing]]
[[Category:Concurrency control]]