Duration Of Blocking
Duration of Blocking: We saw earlier that under the priority-ceiling protocol, a job may be directly blocked, avoidance blocked, and inheritance blocked by lower-priority jobs. A question is whether as a cost of its ability to prevent deadlock, this protocol can cause a job to be blocked for a longer duration than the priority-inheritance protocol. In the worst case, the answer is no. You recall that a job may be blocked for a multiple number of times under the basic priority-inheritance protocol when it conflicts with more than one job over more than one resource. In contrast, under the priority-ceiling protocol, every job is blocked at most once for the duration of a critical section, no matter how many jobs conflict with it. This is stated formally below [ShRL90].
THEOREM . When resource accesses of preemptive, priority-driven jobs on one processor are controlled by the priority-ceiling protocol, a job can be blocked for at most the duration of one critical section.
Informal Proof of Theorem . Rather than proving the theorem formally, we use an intuitive argument to convince you that the theorem is true. There are two parts to this argument: (1)When a job becomes blocked, it is blocked by only one job, and (2) a job which blocks another job cannot be blocked in turn by some other job. State (2) in another way, there can be no transitive blocking under the priority-ceiling protocol.
We use the scenario in Figure 8–13 to to convince you that (1) is true. There are three jobs, Jl , Jm and Jh. Their release times are indicated by the arrows below the graph, which plots the ceiling of the system as a function of time. The priority πl of Jl is lower than the priority πm of Jm, which is in turn lower than the priority πh of Jh. Suppose that at time t1, Jl requests and is granted a resource R. As a consequence, the ceiling of the system rises to ˆ (t1), which is the priority ceiling of R. Later, Jm preempts Jl and acquires some resources (say at and after t2) while it executes. Clearly this is possible only if its priority πm is higher than ˆ (t1). Suppose that at time t4, Jh becomes blocked. We note that it is not possible for Jh to be directly blocked by Jl . Otherwise, the ceiling of the system would be at least as high as πh when Jm requests resources, and Jm would not be able to acquire any resource. If all the resources allocated since t2 are held by Jm at time t4, we have shown that Jm is the only job blocking Jh . On the other hand, suppose that at some time t3 before t4, a resource R is allocated to some other job Jk . Then, Jm cannot be blocking Jh for the same reason that Jl cannot be blocking Jh.
This inductive argument allows us to conclude that Jh is either directly blocked or priority-ceiling blocked by only one job, and this job holds the resource that has the highest priority ceiling among all the resources in use when Jh becomes blocked. For simplicity, we have assumed in this scenario that all three jobs have their assigned priorities. It is easy to see that above argument remains valid even when the jobs have inherited priorities, as long as the priority of Jh is the highest and the priority of Jl is the lowest.
To show that (2) is true, let us suppose that the three jobs Jl , Jm and Jh are blocked transitively. Because the jobs are scheduled according to their priorities, it must be that Jl is preempted after having acquired some resource(s) and later at t , Jm is granted some other resource( s). This can happen only if Jm and all the jobs with higher priorities do not require any of the resources held by Jl at t . Until Jm completes, Jl cannot execute and acquire some other resources. Consequently, Jl cannot inherit a priority equal to or higher than πm(t) until Jm completes. If transitive blocking were to occur, Jm would inherit πh(t), and Jl would inherit a priority higher than πm(t) indirectly. This leads to a contradiction. Hence, the supposition that the three jobs are transitively blocked must be false.
Computation of Blocking Time. Theorem 8.2 makes it easy for us to compute an upper bound to the amount of time a job may be blocked due to resource conflicts. We call this upper bound the blocking time (due to resource conflicts) of the job. To illustrate how to do this computation, let us consider the system of jobs whose resource requirements are given by Figure 8–14. As always, the jobs are indexed in order of decreasing priorities. We see that J1 can be directed blocked by J4 for 1 unit of time. The blocking time b1(rc) of J1 is clearly one. Although J2 and J3 do not require the resource Black, they can be priority-inheritance blocked by J4 since J4 can inherit priority π1. Hence, the blocking times b2(rc) and b3(rc) are also one.
Figure 8–15(a) shows a slightly more complicated example. Even for this small system, it is error prone if we compute the blocking times of all jobs by inspection, as we did earlier. The tables in Figure 8–15(b) give us a systematic way. There is a row for each job that can be blocked. (In these tables, there is a row for every job except J6.) The tables list only the nonzero entries; all the other entries are zero. Since jobs are not blocked by higher-priority jobs, the entries at and below “*” in each column are zero. The leftmost part is the direct-blocking table. It lists for each job the duration for which it can be directly blocked by each of the lower-priority jobs. The entries in this table come directly from the resource requirement graph of the system. Indeed, for the purpose of calculating the blocking times of the jobs, this table gives a complete specification of the resource requirements of the jobs.
The middle part of Figure 8–15(b) is the priority-inheritance blocking table. It lists the maximum duration for which each job can be priority-inheritance blocked by each of the lower-priority jobs. For example, J6 can inherit priority π1 of J1 for 2 units of time when it directly blocks J1. Hence, it can block all the other jobs for 2 units for time. In the table, we show 2 units of inheritance blocking time of J2 and J3 by J6. However, because J6 can also inherit π3 for 4 units of time, it can block J4 and J5 for 4 units of time. This is the reason that the entries in the fourth and fifth rows of column 6 are 4. In general, a systematic way to get the entries in each column of this table from the entries in the corresponding column of the direct-blocking table is as follows. The entry at column k and row i of the inheritance blocking table is the maximum of all the entries in column k and rows 1, 2, . . . , i − 1 of the direct-blocking table.
