SKEDSOFT

Definitions of Protocols and Duration of Blocking
A preemption-ceiling protocol makes decisions on whether to grant a free resource to any job based on the preemption level of the job in a manner similar to the priority-ceiling protocol. This protocol also assumes that the resource requirements of all the jobs are known a priori. After assigning preemption levels to all the jobs, we determine the preemption ceiling of each resource. Specifically, when there is only 1 unit of each resource, which we assume is the case here, the preemption ceiling (R) of a resource R is the highest preemption level of all the jobs that require the resource. For the example in Figure 8–19, the preemption ceiling of Black is 1, while the preemption ceiling of Shaded is 2.

The (preemption) ceiling of the system ˆ (t) at any time t is the highest preemption ceiling of all the resources that are in use at t .When the context is clear and there is no chance of confusion, we will simply refer to ˆ (t) as the ceiling of the system. We again use to Ω denote a preemption level that is lower than the lowest preemption level among all jobs since there is no possibility of confusion. When all the resources are free, we say that the ceiling of the system is Ω.

Like the priority-ceiling protocol, the preemption-ceiling protocol also has a basic version and a stack-based version. The former assumes that each job has its own stack and the latter allows the jobs to share a common stack. Basic versions of priority-ceiling and preemption-ceiling protocols differ mainly in their allocation rules. For this reason, only the allocation rule of the basic preemption-ceiling protocol is given below. You can see that the principle of this rule for both protocols is the same, the only difference being the parameters (i.e., priority or preemption levels and ceilings) used by the rule. Rules of Basic Preemption-Ceiling Protocol

1 and 3. The scheduling rule (i.e., rule 1) and priority inheritance rule (i.e., rule 3) are the same as the corresponding rules of the priority-ceiling protocol.
2. Allocation Rule: Whenever a job J requests resource R at time t , one of the following two conditions occurs:
(a) R is held by another job. J ’s request fails, and J becomes blocked.
(b) R is free.
(i) If J ’s preemption level ψ(t) is higher than the current preemption ceiling ˆ (t) of the system, R is allocated to J .
(ii) If J ’s preemption level ψ(t) is not higher than the ceiling ˆ (t) of the system, R is allocated to J only if J is the job holding the resource(s) whose preemption ceiling is equal to ψ (t); otherwise, J ’s request is denied, and J becomes blocked.

The stack-based preemption-ceiling protocol is called the Stack-Based Protocol (SBP) by Baker [Bake91]. It is defined by the following rules. Rules 0, 1, and 2 are essentially the same as the corresponding rules of the stack-based priority-ceiling protocol; again, the difference is that priority levels/ceilings are replaced by preemption levels/ceilings. In addition, the stack-based preemption-ceiling protocol has an inheritance rule. We will show the need for this rule shortly.

Rules of Basic Stack-Based, Preemption-Ceiling Protocol
0. Update of the Current Ceiling: Whenever all the resources are free, the preemption ceiling of the system is Ω. The preemption ceiling ˆ (t) is updated each time a resource is allocated or freed.
1. Scheduling Rule: After a job is released, it is blocked from starting execution until its preemption level is higher than the current ceiling ψ(t) of the system and the preemption level of the executing job. At any time t , jobs that are not blocked are scheduled on the processor in a priority-driven, preemptive manner according to their assigned priorities.
2. Allocation Rule: Whenever a job J requests for a resource R, it is allocated the resource.
3. Priority-Inheritance Rule: When some job is blocked from starting, the blocking job inherits the highest priority of all the blocked jobs.

Obviously, when the preemption levels of jobs are identical to their priorities, these versions of the preemption-level protocol are the same as the corresponding versions of the priority-ceiling protocol. For this reason, if the jobs in Figure 8–8 are scheduled according to the preemption-ceiling protocol, the resultant schedules are the same as those shown in Figures 8-10 and 8-17.

To see the necessity of the priority-inheritance rule of the stack-based preemptionceiling protocol when preemption levels are assigned on the basis of jobs’s relative deadlines, let us examine Figure 8–20. This figure gives an EDF schedule of jobs in Figure 8–19. (The deadline of each job is indicated by the second vertical bar on its time line. Specifically, the deadlines of J1 and J2 are at 18 and 18.5, respectively.) The preemption levels of the jobs are 2, 1, 3, 5 and 4, respectively, which are chosen based on the relative deadlines of the jobs.3 The preemption ceiling of Black is 2, while the preemption ceiling of Shaded is 3. Hence, the preemption ceiling of the system is given by the dotted line in the graph. Because of the priority-inheritance rule, J4 inherits the priority of J1 when it blocks J1 from starting execution at time 5. Consequently, J4 can continue to execute and completes its critical section. Without this rule, J1 would be blocked because of rule 1, but J2, whose preemption level is 1, could start execution at time 7. Consequently, it would complete before J4 completes its critical section. In other words, without the inheritance rule, J1 would be blocked first by J4 and then by J2. This uncontrolled priority inversion is prevented by the inheritance rule.

It is not surprising that both versions of the preemption-ceiling protocol prevent deadlock and transitive blocking and ensure that every job is blocked for at most the duration of one critical section. Like priority ceilings, preemption ceilings of resources impose an order on all the resources. The preemption ceiling ˆ (t) of the system tells us the subset of all jobs which we can safely grant available resources at time t . This subset contains all the jobs whose preemption levels are higher than the ceiling ˆ (t) of the system. Such a job J can be granted any resource R that is available at t because it does not require any resource that is in use at the time. Moreover, none of the jobs that are holding any resources at t can later preempt J .