real-time computing Real-time computing (RTC) is the computer science term for hardware and software systems subject to a "real-time constraint", for example from event to system response. Real-time programs must guarantee response within specified time constrai ...

, the priority ceiling protocol is a synchronization protocol for

shared resource In computing, a shared resource, or network share, is a computer resource made available from one host to other hosts on a computer network. It is a device or piece of information on a computer that can be remotely accessed from another compu ...

s to avoid unbounded

priority inversion In computer science, priority inversion is a scenario in scheduling in which a high priority task is indirectly superseded by a lower priority task effectively inverting the assigned priorities of the tasks. This violates the priority model that h ...

and mutual

deadlock In concurrent computing, deadlock is any situation in which no member of some group of entities can proceed because each waits for another member, including itself, to take action, such as sending a message or, more commonly, releasing a lo ...

due to wrong nesting of

critical section In concurrent programming, concurrent accesses to shared resources can lead to unexpected or erroneous behavior, so parts of the program where the shared resource is accessed need to be protected in ways that avoid the concurrent access. One way to ...

s. 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 A schedule or a timetable, as a basic time-management tool, consists of a list of times at which possible tasks, events, or actions are intended to take place, or of a sequence of events in the chronological order in which such things are i ...

that supports

dynamic priority scheduling Dynamic priority scheduling is a type of scheduling algorithm in which the priorities are calculated during the execution of the system. The goal of dynamic priority scheduling is to adapt to dynamically changing progress and to form an optimal con ...

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. 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 priority ceiling of the resource, 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. 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". * ICPP is easier to implement than OCPP, as blocking relationships need not be monitored * ICPP leads to fewer context switches as blocking is prior to first execution * ICPP requires more priority movements as this happens with all resource usage * OCPP changes priority only if an actual block has occurred ICPP is called "Ceiling Locking" in

Ada Ada may refer to: Places Africa * Ada Foah, a town in Ghana * Ada (Ghana parliament constituency) * Ada, Osun, a town in Nigeria Asia * Ada, Urmia, a village in West Azerbaijan Province, Iran * Ada, Karaman, a village in Karaman Province, ...

, "Priority Protect Protocol" in

POSIX The Portable Operating System Interface (POSIX) is a family of standards specified by the IEEE Computer Society for maintaining compatibility between operating systems. POSIX defines both the system- and user-level application programming interf ...

and "Priority Ceiling Emulation" in

RTSJ Real time Java is a catch-all term for a combination of technologies that enables programmers to write programs that meet the demands of real-time systems in the Java programming language. Java's sophisticated memory management, native support ...

. It is also known as "Highest Locker's Priority Protocol" (HLP).http://user.it.uu.se/~yi/courses/rts/dvp-rts-08/notes/synchronization-resource-sharing.pdf

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 ''IEEE Transactions on Computers'' is a monthly peer-reviewed scientific journal covering all aspects of computer design. It was established in 1952 and is published by the IEEE Computer Society. The editor-in-chief is Ahmed Louri, David and Mari ...

, volume = 39 , issue = 9 , pages = 1175–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 Real-time computing Concurrency control

ICPP versus OCPP

See also

References