Fixed-priority Scheduling And Priority-ceiling Protocol

Fixed-Priority Scheduling and Priority-Ceiling Protocol
The priority-ceiling protocol is an excellent algorithm for controlling the accesses to resources of periodic tasks when the tasks are scheduled on a fixed-priority basis. It is reasonable to assume that the resources required by every job of every task and the maximum execution times of their critical sections are known a priori, just like the other task parameters. All the jobs in each periodic task have the same priority. Hence, the priority ceiling of each resource is the highest priority of all the tasks that require the resource. This makes it possible for us to analyze and determine the potential of resource contentions among tasks statically. The effect of resource contentions on the schedulability of the tasks can be taken care of by including the blocking time bi (rc) in the schedulability test of the system.

For example, suppose that the jobs in Figure 8–14 belong to four periodic tasks. The tasks are T1 = (ε, 2, 0.8; [Black; 0.8]), T2 = (ε, 2.2, 0.4), T3 = (ε, 5, 0.2; [Shaded; 0.2]), and T4 = (10, 1.0; [Black; 1.0]), where ε is a small positive number. For all i , Ji in Figure 8–14 is a job in Ti . Figure 8–16 shows the initial segment of the schedule of the tasks according to the rate-monotonic algorithm and priority-ceiling protocol.We see that T2 misses it is deadline at time 2.2 ε. A schedulability test can predict this miss. The time-demand function of T2 is equal to 2.2 (i.e., 0.8 0.4 1.0) in (0, 2.0 ε] when the blocking time b2(rc) = 1.0 of T2 is included and becomes 3.0 at 2.0 ε (i.e., the beginning of the second period of T1). Obviously, the time supply by T2’s first deadline at 2.2 ε cannot meet this demand. Similarly, if the jobs Ji, for i = 1, 2, . . . , 6, in Figure 8–15 are jobs in periodic tasks Ti , respectively, we can take the effect of resource conflicts into account in our determination of whether the tasks are schedulable by including the blocking time bi (rc) computed above in the schedulability test.

To summarize this section, we recall that two factors contribute to the time-demand function of each task in addition to the execution times of its jobs and execution times of equal and higher-priority jobs. They are blocking time and context-switching time. When the system is scheduled on a fixed-priority basis and uses the priority-ceiling protocol, we can compute the blocking time bi (rc) of each task Ti due to its resource conflicts with other tasks in the way described above. After we have thus obtained bi (rc), we include this blocking factor with the other types of blocking times (e.g., due to nonpreemptivity of lower-priority

jobs and self-suspension) which the task may suffer to obtain the total blocking time bi of the task.

In Section 6.8, we showed that each job in a system of fixed-priority tasks suffers at most two context switches when the tasks are independent. When the tasks contend for resources under the control of the basic priority-ceiling protocol, each job can be blocked at most once. In particular, a job that requires some resources may be blocked and lose the processor when it requests some resource and, as a consequence, suffers two additional context switches. In contrast, a job which does not require any resource suffers only two context switches: one when it starts and one when it ends. (You recall that the context-switch time when a job is preempted is attributed to the preempting job.) Hence, to account for the context switch overhead in schedulability test, we add

1. two CS to the execution time of each task that does not require any resource and
2. four CS to the execution time of each task that requires one or more resource,

where CS is the maximum time to complete a context switch