SKEDSOFT

Differences between the Priority-Inheritance and Priority-Ceiling Protocols
A fundamental difference between the priority-inheritance and priority-ceiling protocols is that the former is greedy while the latter is not. You recall that the allocation rule (i.e., rule 2) of the priority-inheritance protocol lets the requesting job have a resource whenever the resource is free. In contrast, according to the allocation rule of the priority-ceiling protocol, a job may be denied its requested resource even when the resource is free at the time. (This is what happens to J4 at time 3 in the above example.) We will return shortly to discuss the consequence of this action.

The priority-inheritance rules of these two protocols are essentially the same. In principle, both rules say that whenever a lower priority job Jl blocks the job J whose request is just denied, the priority of Jl is raised to J ’s priority π(t). The difference arises because of

the nongreedy nature of the priority-ceiling protocol. It is possible for J to be blocked by a lower-priority job which does not hold the requested resource according to the priority-ceiling protocol, while this is impossible according to the priority-inheritance protocol.

The wait-for graphs in Figure 8–11 illustrate the three ways in which a job J can be blocked by a lower-priority job when resource accesses are controlled by the priority-ceiling protocol. Of course, J can be directly blocked by a lower-priority job Jl , as shown by the waitfor graph [Figure 8–11(a)]. As a consequence of the priority-inheritance rule, a job J can also be blocked by a lower-priority job Jl which has inherited the priority of a higher-priority job Jh . The wait-for graph in Figure 8–11(b) shows this situation. (For simplicity, we show only the inheritance due to direct blocking.) As stated in Section 8.4, this is priority-inheritance blocking.

The allocation rule may cause a job J to suffer priority-ceiling blocking, which is represented by the graph in Figure 8–11(c). The requesting job J is blocked by a lower-priority job Jl when J requests a resource R that is free at the time. The reason is that Jl holds another resource X whose priority ceiling is equal to or higher than J ’s priority π(t). Rule 3 says that a lower-priority job directly blocking or priority-ceiling blocking the requesting job J inherits J ’s priority π(t).

Priority-ceiling blocking is sometimes referred to as avoidance blocking. The reason for this term is that the blocking caused by the priority-ceiling rule is the cost for avoidance of deadlocks among jobs. Hereafter, we will use the terms avoidance blocking and priorityceiling blocking interchangeably.