Hardware Reference
In-Depth Information
8.2
NON-PREEMPTIVE SCHEDULING
The most effective way to reduce preemption cost is to disable preemptions com-
pletely. In this condition, however, each task
τ
i
can experience a blocking time
B
i
equal to the longest computation time among the tasks with lower priority. That is,
B
i
=max
j
:
P
j
<P
i
{
C
j
−
1
}
(8.1)
where the maximum of an empty set is assumed to be zero. Note that one unit of
time must be subtracted from
C
j
to consider that to block
τ
i
, the blocking task must
start at least one unit before the critical instant. Such a blocking term introduces an
additional delay before task execution, which could jeopardize schedulability. High
priority tasks are those that are most affected by such a blocking delay, since the
maximum in Equation (8.1) is computed over a larger set of tasks. Figure 8.4 illustrates
the schedule generated by Deadline Monotonic on the task set of Table 8.1 when
preemptions are disabled. With respect to the schedule shown in Figure 8.3, note that
τ
3
is now able to complete before its deadline, but the task set is still not schedulable,
since now
τ
1
misses its deadline.
deadline miss
1
τ
1
3
τ
2
6
τ
3
0
2
4
6
8
10
12
14
16
18
20
Figure 8.4
Schedule produced by non-preemptive Deadline Monotonic on the task set of
Table 8.1.
Unfortunately, under non-preemptive scheduling, the least upper bounds of both RM
and EDF drop to zero! This means that there are task sets with arbitrary low utilization
that cannot be scheduled by RM and EDF when preemptions are disabled. For exam-
ple, the task set illustrated in Figure 8.5(a) is not feasible under non-preemptive Rate
Monotonic scheduling (as well as under non-preemptive EDF), since
C
2
>T
1
, but its
utilization can be set arbitrarily low by reducing
C
1
and increasing
T
2
. The same task
set is clearly feasible when preemption is enabled, as shown in Figure 8.5(b).
Search WWH ::
Custom Search