The priority ceiling protocol extends the priority inheritance protocol to prevent deadlocks and to further reduce the blocking time. This protocols makes following assumptions.

  • The assigned priorities of all jobs are fixed.
  • The resources required by all jobs are known a priori before the execution of any job begins.

The protocol makes use of a parameter called priority ceiling of every resource. The priority ceiling of any resource Ri is the highest priority of all the jobs that require Ri and is denoted by Π (Ri). At any time t, the current priority ceiling Π (t) of the system is equal to the highest priority ceiling of the resources that are in use at that time, if some resources are in use. If all the resources are free at the time, the current ceiling Π (t) is Ω, a non-existing priority level that is lower than the lowest priority of all jobs.

Rules of Priority Ceiling Protocol:

1. Scheduling rule:

  1. At its release time t, the current priority π (t) of every job J is equal to its assigned priority. The job remains at this priority except under the condition stated in rule 3.
  2. Every ready job J is scheduled preemptively and in a priority driven manner at its current priority π (t).

2. Allocation rule:

Whenever a job J requests a resource R at time t, one of the following two conditions occurs:

  1. R is held by another job J‟s request fails and J becomes blocked.
  2. R is free then
    1. If J’s priority π (t) is higher than current priority ceiling, R is allocated to J.
    2. If J’s priority π (t) is not higher than the current priority ceiling of the system, R is allocated to J only if J is the job holding the resource whose priority ceiling is equal to current priority ceiling otherwise J’s request is denied and J becomes blocked.

3. Priority Inheritance Rule:

When J becomes blocked the job Jl which blocked J inherits the current priority π (t) of J. Jl executes at its inherited priority until the time when it releases every resource whose priority ceiling is equal to or higher than π (t). At that time, priority of Jl returns to its priority πl  (t’) at time t’ when it was granted the resource.

For example:

Consider a system with following parameters:

                         

  • The priority ceiling of the black resource is two since J2 is the highest priority job among the jobs requiring it.
  • The priority ceiling of the shaded resource is one.
  • In the priority inheritance protocol figure [0,1) current ceiling of the system is Ω lower than 5.
  • In (1, 3] interval black is held by J5 so the current ceiling of the system is 2.
  • In (3, 13] interval when shaded is also in use the current ceiling of the system is 1.

The access to resources are controlled by the priority ceiling protocol. Here the priority ceiling of the resources Black and Shaded are two and one respectively.

                                     

  • In the interval (0,3], this schedule is the same as the schedule which is produced under the basic priority inheritance protocol, the ceiling of the system at time 1 is Ω, when J5 requests black it is allocated the resource according to (i) in part (b) of rule 2 after black is allocated the ceiling of the system is raised to two the priority ceiling of black
  • At time 3, J4 requests shaded, shaded is free. However, because the ceiling pi(3) is equal to two of the system is higher than the priority of J4 ,J4’s request is denied according to ii in part of (b) of rule two J4 is blocked and J5 inherits J4‟s priority and executes at priority 4
  • At time 4, J3 preempts J5 and at time 5 J2 preempts J3 at time 6, J2 requests black and becomes directly blocked by J5. So J5 inherits the priority 2. It executes until J1 becomes ready and preempts During all this time , the ceiling of the system remains at two
  • When J1 request shaded at time 8, its priority is higher than the ceiling of the system. So its request if granted according to i in part (b) of rule 2 allowing it to enter its critical section and complete by the time 10 at time 10, J3 and J5 are ready. The latter has a higher priority 2 ; It resumes
  • At 11, when J5 releases black, its priority returns to 5 and the ceiling of the system drops to Ω. J2 becomes unblocked is allocated black and starts to execute
  • At time 14 ,after J2 and J3 complete J4 has the processor and is granted the resource shaded because its priority is higher than Ω, the ceiling of the system at the time. It starts to execute. The ceiling of the system is raised to one. The priority ceiling of shaded.
  • At time 16, J4 requests black, which is free, the priority of J4 is lower than current priority ceiling Π(16), but J4 is the job holding the shaded resource whose priority ceiling is equal to Π(16) hence J4 is granted black . It continues to execute