BASIC CONCEPTS - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 47

Notice that the scheduling anomaly illustrated by the previous example is particu-
larly insidious for hard real-time systems, because tasks are guaranteed based on their
worst-case behavior, but they may complete before their worst-case computation time.
A simple solution that avoids the anomaly is to keep the processor idle if tasks com-
plete earlier, but this can be very inefficient. There are algorithms, such as the one
proposed by Shen [SRS93], that tries to reclaim such an idle time, while addressing
the anomalies so that they will not occur.
If tasks share mutually exclusive resources, scheduling anomalies can also occur in
a uniprocessor system when changing the processor speed [But06]. In particular, the
anomaly can be expressed as follows:
A real-time application that is feasible on a given processor can become
infeasible when running on a faster processor.
Figure 2.24 illustrates a simple example where two tasks, τ 1 and τ 2 , share a common
resource (critical sections are represented by light grey areas). Task τ 1 has a higher
priority, arrives at time t =2and has a relative deadline D 1 =7. Task τ 2 , having
lower priority, arrives at time t =0and has a relative deadline D 2 =23. Suppose that,
when the tasks are executed at a certain speed S 1 , τ 1 has a computation time C 1 =6,
(where 2 units of time are spent in the critical section), whereas τ 2 has a computation
time C 2 =18(where 12 units of time are spent in the critical section). As shown in
Figure 2.24a, if τ 1 arrives just before τ 2 enters its critical section, it is able to complete
before its deadline, without experiencing any blocking. However, if the same task set
is executed at a double speed S 2 =2 S 1 , τ 1 misses its deadline, as clearly illustrated in
Figure 2.24b. This happens because, when τ 1 arrives, τ 2 already granted its resource,
causing an extra blocking in the execution of τ 1 , due to mutual exclusion.
Although the average response time of the task set is reduced on the faster processor
(from 14 to 9.5 units of time), note that the response time of task τ 1 increases when
doubling the speed, because of the extra blocking on the shared resource.
ANOMALIES UNDER NON-PREEMPTIVE SCHEDULING
Similar situations can occur in non-preemptive scheduling. Figure 2.25 illustrates an
anomalous behavior occurring in a set of three real-time tasks, τ 1 , τ 2 and τ 3 , running
in a non-preemptive fashion. Tasks are assigned a fixed priority proportional to their
relative deadline, thus τ 1 is the task with the highest priority and τ 3 is the task with
the lowest priority. As shown in Figure 2.25a, when tasks are executed at speed S 1 ,
τ 1 has a computation time C 1 =2and completes at time t =6. However, if the same