SKEDSOFT

Real Time Systems

The rightmost table in Figure 8–15(b) is the avoidance (priority-ceiling) blocking table. It lists the maximum duration for which each job can be avoidance blocked by each lowerpriority job. Again, let us focus on column 6. When J6 holds resource X (whose priority ceiling is the highest in the system), it avoidance blocks all the jobs which require any resource. Similarly, when it holds Z, it avoidance blocks J4. Therefore, except for the entry in row 5, all entries in column 6 of the avoidance blocking table are the same as the corresponding entries in column 6 of the inheritance blocking table. J5 does not require any resource and is never directly or avoidance blocked. In general, when the priorities of all the jobs are distinct, the entries in the avoidance blocking table are equal to corresponding entries in the priority-inheritance blocking table, except for jobs which do not require any resources. Jobs which do not require any resource are never avoidance blocked, just as they are never directly blocked.

The blocking time bi (rc) of each job Ji is equal to the maximum value of all the entries in the ith row of the three tables. From Figure 8–15(b), we have bi (rc) is equal to 6, 6, 5, 4, 4, and 0 for i = 1, 2, . . . , 6, respectively

For this example, every entry in the avoidance blocking table is either equal to or smaller than the corresponding entries in the direct blocking or inheritance blocking tables. Since we are taking the maximum value of the entries of each row, there is no need for us to compute the avoidance blocking table. Indeed, we do not need this table whenever the priorities of all the jobs are distinct. When the priorities of jobs are not distinct, a job may be avoidance blocked by a job of equal priority. The avoidance blocking table gives this information. For example, suppose that in addition to the jobs in Figure 8–15(a), there is a job J 1 whose priority is also π1, and this job requires a resource V for 9 units of time. Then the blocking time of J1 is 10, the amount of time J1 holds the resource X and priority-ceiling blocks J1. Similarly, the blocking time of J1 is 9, the duration for which it is priority-ceiling blocked by J1. In this case, we need the avoidance blocking table to give us these blocking times.

In Problem 8.14, you are asked to provide a pseudocode description of an algorithm that computes the blocking time bi (rc) of all the jobs from the resource requirement graph of the system. For the sake of efficiency, you may want to first identify for each job Ji the subset of all the jobs that may block the job. This subset is called the blocking set of Ji . (In our simple example, J5 is not included in the blocking set of any other job, since it cannot block any job. The blocking set of Ji includes all the lower-priority jobs other than J5.)