SKEDSOFT

Modified Rules: It is straightforward to modify the ceiling-priority protocol so it can deal with multiple-unit resources. In essence, the scheduling and allocation rules remains unchanged except for the new definition of priority ceiling of resources. However, since more than one job can hold (some units of) a resource, scheduling rule 1b needs to be rephrased for clarity. It should read as follows:

Scheduling Rule of Multiple-Unit Ceiling-Priority Protocol: Upon acquiring a resource R and leaving k ≥ 0 free units of R, a job executes at the higher of its priority and the priority ceiling (R, k) of R.
Similarly, the allocation rule of the priority-ceiling (or preemption-ceiling) protocol for multiple units of resources is a straightforward modification of the allocation rule of the basic priority-ceiling (preemption-ceiling) protocol.

Allocation Rule of Multiple-Unit Priority-(Preemption-) Ceiling Protocol
Whenever a job J requests k units of resource R at time t , one of the following two conditions occurs:
(a) Less than k units of R are free. J ’s request fails and J becomes directly blocked.
(b) k or more units of R are free.
(i) If J ’s priority π(t) [preemption level ψ(t)] is higher than the current priority ceiling ψ (t) [preemption ceiling ψ (t)] of the system at the time, k units of R are allocated to J until it releases them.
(ii) If J ’s priority π(t) [preemption level ψ(t)] is not higher than the system ceiling ψ (t) [ ψ (t)], k units of R are allocated to J only if J holds the resource(s) whose priority ceiling (preemption ceiling) is equal to ψ (t) [ ψ (t)]; otherwise, J ’s request is denied, and J becomes blocked.

You can see that this rule is essentially the same as the allocation rule of the basic version. The only change is in the wording to accommodate multiple-unit requests.

Priority-Inheritance Rule: In the case where there is only 1 unit of each resource, we have shown that when a job J is blocked, only one lower-priority job is responsible for this blocking and this lower-priority job inherits J ’s priority. This may no longer be true in a system containing multiple resource units. More than one lower-priority job may be responsible. The question is which one of these jobs should inherit J ’s priority.

To illustrate, let us examine a system where there are 3 units of resource R, and there are four jobs, each requiring 1 unit of R. Suppose that at the time when the highest priority job J1 requests a unit of R, all 3 units are held by the other three jobs. Now, all three lower-priority jobs block J1. In this case, it is reasonable to let J2 (i.e., the job with the highest priority among the three lower-priority jobs) inherit J1’s priority until it releases its units of R. Indeed, an important special case is when a job can request and hold at most 1 unit of every resource at a time. (An example is counting semaphores.) In this case, the following priority-inheritance rule proposed by Chen [Chen] works well, that is, each job is blocked at most once for the duration of one critical section

Priority-Inheritance Rule: When the requesting job J becomes blocked at t , the job with the highest priority among all the jobs holding the resource R that has the highest priority ceiling among all the resources inherits J ’s priority until it releases its unit of R.

In general, a job may request and hold arbitrary numbers of resources. The example in Figure 8–22 illustrates that a straightforward generalization of the priority-ceiling protocol and the above priority-inheritance rule ensures that each job is blocked at most once. The system in this example has five jobs indexed in decreasing order of their priorities. (In the description below, the priorities are 1, 2, 3, 4 and 5.) There are two resources Black and Shaded. The numbers of units are 5 and 1, respectively. The resource requirements of the jobs and priority ceilings of the resources are listed in Figure 8–22(a).

1. At time 0, J5 starts to execute. When it requests 1 unit of Black at time 0.5, the ceiling of the system is Ω; therefore, it is granted 1 unit of Black and continues to execute. The ceiling of the system stays at Ω because there still are sufficient units of Black to meet the demand of every job.
2. At time 1, J4 becomes ready. It preempts J5 and, later, requests and is granted 1 unit of Black. Now, J2 would be directly blocked if it requests Black, and the ceiling of Black, and consequently of the system, becomes 2, the priority of J2.
3. At time 2, J3 preempts J4, and at time 2.5, J2 preempts J3. J2 becomes blocked when it requests Shaded at time 3 because its priority is not higher than the ceiling of the system. J4 now inherits priority 2 and executes.

4. At time 3.5, J1 preempts J4. Since its priority is higher than the ceiling of the system, J1 is allocated both resources when it requests them.
5. At time 6, J1 completes, and J4 continues to execute until it releases its 1 unit of Black at time 6.5. The ceiling of the system returning to Ω, J2 is allocated Shaded. After Shaded is allocated, the ceiling of the system becomes 1.
6. At time 7, when J2 requests 4 units of Black, the units are available. The ceiling of the system is 1, but J2 holds the resource with this priority ceiling. Hence it is allocated 4 units of Black.
7. When J2 completes, J3 resumes. When J3 completes, J4 resumes, and it is followed by J5. The system becomes idle at time 10.

From this example, we can see that Chen’s priority-inheritance rule works for the general case as well. Specifically, we let R denote the resource whose priority ceiling is the highest among all resources in the system at time t. Let J' denote the job that has acquired the resource latest among all jobs holding R. If a requesting job J becomes blocked at t , J'  inherits the priority of J .