SKEDSOFT

CONTROLLING ACCESSES TO MULTIPLE-UNIT RESOURCES
Both versions of the priority-ceiling protocol and preemption-ceiling protocol described in the previous sections assume that there is only one unit of each resource. We now describe an extension to these protocols so that they can deal with the general case where there may be more than one unit of each resource (type).

Priority (Preemption) Ceilings ofMultiple-Unit Resources
The first step in extending the priority-ceiling protocol is to modify the definition of the priority ceilings of resources. We let (Ri , k), for k ≤ vi , denote the priority ceiling of a resource Ri when k out of the νi (≥ 1) units of Ri are free. If one or more jobs in the system require more than k units of Ri , (Ri , k) is the highest priority of all these jobs. If no job requires more than k units of Ri , (Ri , k) is equal to Ω, the nonexisting lowest priority. In this notation, the priority ceiling (Rj ) of a resource Rj that has only 1 unit is (Rj , 0).

Let ki (t) denote the number of units of Ri that are free at time t . Because this number changes with time, the priority ceiling of Ri changes with time. The (current) priority ceiling of the system at time t is equal to the highest priority ceiling of all the resources at the time. Figure 8–21 gives an example. The resource requirement graph gives the numbers of units of the resources X, Y, and Z required by the five jobs that are indexed in decreasing order of their priorities. The table below the graph gives the priority ceilings of each resource for different numbers of free resource units. For example, there are 2 units of X. When 1 unit of X is used, only J3 is directly blocked. Therefore, (X, 1) is π3. J1 is also directly blocked when both units of X are in use. For this reason, (X, 0) is π1, the higher priority between π1 and π3. When both units of X are free, the ceiling of the resource is Ω. Similarly, since J2, J3, and J5 require 2, 3, and 1 unit of Y, which has 3 units, (Y, 0), (Y, 1), and (Y, 2) are equal to π2, π2, and π3, respectively. Suppose that at time t , 1 unit of each of X, Y, and Z is free. The priority ceilings of the resources are π3, π2, and Ω, respectively, and the priority ceiling of the system is π2.

The preemption ceilings of resources that have multiple units can be defined in a similar manner: The preemption ceiling (Ri , k) of the resource Ri when k units of Ri are free is the highest preemption level of all the jobs that require more than k units of Ri . Hence, if the jobs in Figure 8–21 were indexed in decreasing order according to their preemption levels and we replaced πi and (∗, k) in the table by ψi and (∗, k), respectively, we would get the preemption ceilings of the three resources. The preemption ceiling of the system at time t is equal to the highest preemption ceiling of all the resources at the time.