Hardware Reference
In-Depth Information
9.2.5
THE RED ALGORITHM
RED (Robust Earliest Deadline) is a robust scheduling algorithm proposed by But-
tazzo and Stankovic [BS93, BS95] for dealing with firm aperiodic tasks in overloaded
environments. The algorithm synergistically combines many features including grace-
ful degradation in overloads, deadline tolerance, and resource reclaiming. It operates
in normal and overload conditions with excellent performance, and it is able to predict
not only deadline misses but also the size of the overload, its duration, and its overall
impact on the system.
In RED, each task
J
i
(
C
i
,D
i
,M
i
,V
i
) is characterized by four parameters: a worst-
case execution time (
C
i
), a relative deadline (
D
i
), a deadline tolerance (
M
i
), and
an importance value (
V
i
). The deadline tolerance is the amount of time by which a
task is permitted to be late; that is, the amount of time that a task may execute after
its deadline and still produce a valid result. This parameter can be useful in many
real applications, such as robotics and multimedia systems, where the deadline timing
semantics is more flexible than scheduling theory generally permits.
Deadline tolerances also provide a sort of compensation for the pessimistic evaluation
of the worst-case execution time. For example, without tolerance, a task could be
rejected, although the system could be scheduled within the tolerance levels.
In RED, the primary deadline plus the deadline tolerance provides a sort of secondary
deadline, used to run the acceptance test in overload conditions. Note that having a
tolerance greater than zero is different than having a longer deadline. In fact, tasks are
scheduled based on their primary deadline but accepted based on their secondary dead-
line. In this framework, a schedule is said to be
strictly feasible
if all tasks complete
before their primary deadline, whereas is said to be
tolerant
if there exists some task
that executes after its primary deadline but completes within its secondary deadline.
The guarantee test performed in RED is formulated in terms of residual laxity. The
residual laxity
L
i
of a task is defined as the interval between its estimated finishing
time
f
i
and its primary (absolute) deadline
d
i
. Each residual laxity can be efficiently
computed using the result of the following lemma.
Lemma 9.1
Given a set
J
=
of active aperiodic tasks ordered by
increasing primary (absolute) deadline, the residual laxity
L
i
of each task
J
i
at time
t
can be computed as
{
J
1
,J
2
,...,J
n
}
c
i
(
t
)
,
(9.10)
where
L
0
=0
,
d
0
=
t
(the current time), and
c
i
(
t
)
is the remaining worst-case
computation time of task
J
i
at time
t
.
L
i
=
L
iā
1
+(
d
i
ā
d
iā
1
)
ā
Search WWH ::
Custom Search