Definition Of Ceiling-priority Protocol

Definition ofCeiling-Priority Protocol
As we will see shortly, the worst-case performance of the stack-based and the basic priorityceiling protocols are the same. The former is considerably simpler and has a lower context switching overhead. This is a good reason for using the stack-based version if jobs never self-suspend even when the jobs have their own stacks. Indeed, the stack-based version is the protocol supported by the Real-Time Systems Annex of Ada95 [Cohe96]. In Section 8.3, we mentioned that it is called the ceiling-priority protocol. The following rules defines it more formally.

Rules Defining the Ceiling-Priority Protocol
1. Scheduling Rule:
(a) Every job executes at its assigned priority when it does not hold any resource. Jobs of the same priority are scheduled on the FIFO basis.
(b) The priority of each job holding any resource is equal to the highest of the priority ceilings of all resources held by the job.
2. Allocation Rule: Whenever a job requests a resource, it is allocated the resource.

We note that when jobs never self-suspend, the stack-based priority-ceiling and ceilingpriority protocols are the same. By saying these protocols are the same we mean that they will produce the same schedule for all jobs. (If you are not convinced, you may want to apply this set of rules on the example given by Figure 8–8(a). The schedule you will produce should be same as one in Figure 8–17.) The two sets of rules give two implementations of the same protocol.

Sometimes, jobs of equal priority are scheduled on the round-robin basis. We must modify the definition of the ceiling-priority protocol to make it work for these jobs. This modification is left as an exercise to you in Problem 8.5.

Blocking Time and Context-Switching Overhead: Because of the following theorem [Bake91], we can use the same method to find the blocking time bi (rc) of every job Ji for both versions of the priority-ceiling protocol.

THEOREM 8.3. The longest blocking time suffered by every job is the same for the stack-based and basic priority-ceiling protocols.

To see why this theorem is true, we observe first that a higher-priority job Jh can be blocked only by the currently executing job Jl under the stack-based priority-ceiling protocol. The reason is that if a job Jl can start to execute at t , its priority is higher than the ceiling of the system at t . This means that none of the resources in use at t are required by Jl or any higher-priority job. Furthermore, similar arguments allow us to conclude that under the stack-based protocol, no job is ever blocked due to resource conflict more than once.

Now let us suppose that under the stack-based priority-ceiling protocol, a job Jh is blocked by the currently executing job Jl . This can happen only if Jh is released after Jl has acquired a resource X whose priority ceiling is equal to or higher than the priority πh of Jh and at the time when Jh is released, Jl still holds X. The occurrence of this sequence of events is not dependent on the protocol used; the sequence can also occur under the basic priorityceiling protocol. Moreover, under this circumstance, Jh is also blocked by Jl under the basic priority-ceiling protocol. In the worst case, Jh is blocked for as long as the job Jl holds such a resource. Theorem 8.3 follows from the fact that we can repeat this argument for every lower-priority job which can block Jh .

While the (worst-case) blocking time of individual jobs and periodic tasks are the same for both versions of the priority-ceiling protocol, the context-switch overhead is smaller under the stack-based version. Because no job is ever blocked once its execution starts, no job ever suffers more than two context switches. In particular, to take into account the contextswitching overhead in the schedulability analysis of a system of periodic tasks scheduled according to a fixed-priority algorithm and stack-based priority-ceiling protocol, we add 2CS to the execution time of every task.