SKEDSOFT

Properties ofthe Priority-Inheritance Protocol: This example illustrates that when resource accesses are controlled by the priority-inheritance protocol, there are two types of blocking: direct blocking and priority-inheritance blocking (or simply inheritance blocking). J2 is directly blocked by J5 in (6, 11] and by J4 in (11, 12.5], and J1 is directly blocked by J4 in (8, 13]. In addition, J3 is blocked by J5 in (6, 7] because the latter inherits a higher priority in this interval. Later at time 8, when J4 inherits priority 1 from J1, J3 becomes blocked by J4 as a consequence. Similarly, the job J2 in Figure 8–7(b) suffers inheritance blocking by J3 in (5, 7]. This type of blocking suffered by jobs that are not involved in resource contention is the cost for controlling the durations of priority inversion suffered by jobs that are involved in resource contention.

The example in Figure 8–8 also illustrates the fact that jobs can transitively block each other. At time 9, J5 blocks J4, and J4 blocks J1. So, priority inheritance is transitive. In the time interval (9, 11), J5 inherits J4’s priority, which J4 inherited from J1. As a consequence, J5 indirectly inherits the J1’s priority.

The priority-inheritance protocol does not prevent deadlock. To see why, let us suppose that J5 in this example were to request the resource Shaded sometime after Shaded has been granted to J4 (e.g., at time 6.5). These two jobs would be deadlocked.

In addition, the priority-inheritance protocol does not reduce the blocking times suffered by jobs as small as possible. It is true that in the absence of a deadlock, a job can be blocked directly by any lower-priority job for at most once for the duration of one outermost critical section. However, in the worst case, a job that requires v resources and conflicts with k lowerpriority jobs can be blocked for min(v, k) times, each for the duration of an outermost critical section. Figure 8–9 shows the worst-case scenario when v is equal to k. Here the job J1 has the highest priority; it is blocked k times.