SKEDSOFT

Real Time Systems

BASIC PRIORITY-CEILING PROTOCOL: The priority-ceiling protocol [ShRL88, ShRL90] extends the priority-inheritance protocol to prevent deadlocks and to further reduce the blocking time. This protocol makes two key assumptions:
1. The assigned priorities of all jobs are fixed.
2. The resources required by all jobs are known a priori before the execution of any job begins.

To define the protocol, we need two additional terms. 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 ). For example, the priority ceiling (Black) of the resource Black in the example in Figure 8–8 is 2 because J2 is the highest priority job among the jobs requiring it. Similarly, (Shaded) is 1. Because of assumption 2, the priority ceilings of all resources are known a priori. We note that if the resource access control protocol includes the priority-inheritance rule, then a job can inherit a priority as high as x during its execution if it requires a resource with priority ceiling x.

At any time t , the current priority ceiling (or simply the ceiling) ˆ (t) of the system is equal to the highest priority ceiling of the resources that are in use at the time, if some resources are in use. If all the resources are free at the time, the current ceiling ˆ (t) is equal to Ω, a nonexisting priority level that is lower than the lowest priority of all jobs. As an example, we again look at the system in Figure 8–8. In the interval [0, 1) when both resources in the system are free, the current ceiling of the system is equal to Ω, lower than 5, the priority of the lowest priority job J5. In (1, 3], Black is held by J5; hence, the current ceiling of the system is 2. In (3, 13] when Shaded is also in use, the current ceiling of the system is 1, and so it is in (13, 14].

Definition ofthe Basic Priority-Ceiling Protocol: We now define the priority-ceiling protocol for the case when there is only 1 unit of every resource.

Rules of Basic Priority-Ceiling Protocol

1. Scheduling Rule:
(a) 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.
(b) 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:
(a) R is held by another job. J ’s request fails and J becomes blocked.
(b) R is free.
(i) If J ’s priority π(t) is higher than the current priority ceiling ˆ (t), R is allocated to J.

(ii) If J ’s priority π(t) is not higher than the ceiling ˆ (t) of the system, R is allocated to J only if J is the job holding the resource(s) whose priority ceiling is equal to ˆ (t); otherwise, J ’s request is denied, and J becomes blocked.
3. Priority-Inheritance Rule: When J becomes blocked, the job Jl which blocks 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, the priority of Jl returns to its priority πl (t') at the time t  when it was granted the resource(s).

We note that (ii) in rule 2 assumes that only one job holds all the resources with priority ceiling equal to ˆ (t). Similarly, rule 3 assumes that only one job is responsible for J ’s request being denied, because it holds either the requested resource or a resource with priority ceiling ˆ (t). We will return shortly to show that these assumptions are true.
Figure 8–10 shows the schedule of the system of jobs whose parameters are listed in Figure 8–8(a) when their accesses to resources are controlled by the priority-ceiling proto-col. As stated earlier, the priority ceilings of the resources Black and Shaded are 2 and 1, respectively.

 

 

 

 

 

 

 

  1. In the interval (0, 3], this schedule is the same as the schedule shown in Figure 8–8, which is produced under the basic priority-inheritance protocol. In particular, 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 2, the priority ceiling of Black.
  2. At time 3, J4 requests Shaded. Shaded is free; however, because the ceiling ˆ (3) (= 2) of the system is higher than the priority of J4, J4’s request is denied according to (ii) in part (b) of rule 2. J4 is blocked, and J5 inherits J4’s priority and executes at priority 4.
  3. 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. Consequently, J5 inherits the priority 2; it executes until J1 becomes ready and preempts it. During all this time, the ceiling of the system remains at 2.
  4. When J1 requests Shaded at time 8, its priority is higher than the ceiling of the system. Hence, its request is 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 (i.e., 2); it resumes.
  5. 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 [according to (i) in part (b) of rule 2], and starts to execute.
  6. 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 1, the priority ceiling of Shaded.
  7. At time 16, J4 requests Black, which is free. The priority of J4 is lower than ˆ (16), but J4 is the job holding the resource (i.e., Shaded) whose priority ceiling is equal to ˆ (16). Hence, according to (ii) of part (b) of rule 2, J4 is granted Black. It continues to execute. The rest of the schedule is self-explanatory.

Comparing the schedules in Figures 8–8 and 8–10, we see that when priority-ceiling protocol is used, J4 is blocked at time 3 according to (ii) of part (b) of rule 2. A consequence is that the higher priority jobs J1, J2, and J3 all complete earlier at the expense of the lower priority job J4. This is the desired effect of the protocol.