SKEDSOFT

Deadlock Avoidance by Priority-Ceiling Protocol: The set of priority ceilings of resources impose a linear order on all the resources. It may not surprise you that deadlock can never occur under the priority-ceiling protocol.

In order to gain a deeper insight into how the protocol works to prevent deadlock, we pause to look at a more complicated example. In the example in Figure 8–12, there are three jobs: J1, J2, and J3 with priorities 1, 2, and 3, respectively. Their release times are 3.5, 1, and 0 and their critical sections are [Dotted; 1.5], [Black; 2 [Shaded; 0.7]], and [Shaded; 4.2 [Black; 2.3]], respectively. In this schedule, the intervals during which the jobs are in their critical sections are shown as the dotted box (the critical section associated with resource Dotted),

shaded boxes (critical sections associated with resource Shaded), and black boxes (critical sections associated with resource Black).
1. When J3 requests Shaded at time 0.5, no resource is allocated at the time. J3’s request is granted. When job J2 becomes ready at time 1, it preempts J3.
2. At time 2.5, J2 requests Black. Because Shaded is already allocated to J3 and has priority ceiling 2, the current ceiling of the system is 2. J2’s priority is 2. According to (ii) of part (b) of rule 2, J2 is denied Black, even though the resource is free. Since J2 is blocked, J3 inherits the priority 2 (rule 3), resumes, and starts to execute.
3. When J3 requests Black at time 3, it is holding the resource whose priority ceiling is the current ceiling of the system. According to (ii) of part (b) of rule 2, J3 is granted the resource Black, and it continues to execute.
4. J3 is preempted again at time 3.5 when J1 becomes ready. When J1 requests Dotted at time 4.5, the resource is free and the priority of J1 is higher than the ceiling of the system. (i) of part (b) of rule 2 applies, and Dotted is allocated to J1, allowing the job to enter into its critical section and proceed to complete at 7.3. The description of the segment after this time is left to you.

We now use this example to explain intuitively why priority-ceiling protocol prevents deadlock. To see the rationale behind (ii) of part (b) of rule 2, which leads to the denial of J2’s request for Black, we note that at the time Black is free but Shaded is already allocated to J3. The fact that the priority ceiling of Shaded is 2 indicates that some job with priority 2 requires this resource and this job may very well be J2, as is indeed the case in this example. If J2 were allowed to have Black, it might later request Shaded and would be blocked by J3. J3 would execute and might later request Black. Denying J2’s access to Black is one way to prevent this deadlock. On the other hand, suppose that the priority ceiling of Shaded were lower than the priority of J2. This fact would indicate that J2 does not require Shaded. Moreover, no job with priority equal to or higher than J2 requires this resource. Consequently, it would not be possible for the job holding Shaded to later inherit a higher priority than J2, preempt J2, and request Black. This is the rationale of (i) of part (b) of rule 2. Indeed, this is the reason that J1 was granted Dotted.

Let us now state in general terms what was said above. At any time t , the priority π(t) of a job J being higher than the current ceiling ˆ (t) of the system means that (1) job J will not require any of the resources in use at t and (2) jobs with priorities equal to or higher than J will not require any of these resource. In other words, the priority ceiling ˆ (t) of the system tells us the subset of all jobs to which we can safely grant free resources at time t ; this subset contains all the jobs that have higher priorities than ˆ (t). Because of (1), J will not request any resource that is in use at the time. Because of (2), no job holding any resource at the time can inherit a higher priority than J , later preempt J , and request resources allocated to J after t . For these reasons, (i) of part (b) of rule 2 will not lead to any deadlock.

(ii) in part (b) of rule 2 states an exception to the rule that J ’s request for any resource is denied if its priority is not higher than the ceiling of the system. The exception applies when J is the job holding the resource(s) whose priority ceiling(s) is equal to ˆ (t); under this condition, J is granted the resource it requests at t . (This exception is necessary in order to ensure that a job can make progress as it acquires resources. Otherwise, the job would block itself!) J ’s priority π(t) must be equal to ˆ (t) when it is granted its requested resource under this condition. Moreover, because of (i) and (ii) in part (b) of rule 2, no other job is holding resources with priority ceiling equal to ˆ (t). Consequently, (ii) in part (b) of rule 2 cannot lead to any deadlock.