Hardware Reference
In-Depth Information
Proof.
f
i
. Since tasks are ordered by
increasing deadlines,
J
1
is executing at time
t
, and its estimated finishing time is given
by the current time plus its remaining execution time (
f
1
=
t
+
c
1
). As a consequence,
L
1
is given by
By definition, a residual laxity is
L
i
=
d
i
−
c
1
.
Any other task
J
i
, with
i>
1, will start as soon as
J
i−
1
completes and will finish
c
i
units of time after its start (
f
i
=
f
i−
1
+
c
i
). Hence, we have
L
1
=
d
1
−
f
1
=
d
1
−
t
−
L
i
=
d
i
−
f
i
=
d
i
−
f
i−
1
−
c
i
=
d
i
−
(
d
i−
1
−
L
i−
1
)
−
c
i
=
=
L
i−
1
+(
d
i
−
d
i−
1
)
−
c
i
,
and the lemma follows.
Note that if the current task set
J
is schedulable and a new task
J
a
arrives at time
t
,
the feasibility test for the new task set
J
=
J
requires to compute only the
residual laxity of task
J
a
and that one of those tasks
J
i
such that
d
i
>d
a
. This is
because the execution of
J
a
does not influence those tasks having deadline less than
or equal to
d
a
, which are scheduled before
J
a
. It follows that, the acceptance test has
O
(
n
) complexity in the worst case.
∪{
J
a
}
To simplify the description of the RED guarantee test, we define the
Exceeding time
E
i
as the time that task
J
i
executes after its secondary deadline:
1
E
i
=max(0
,
−
(
L
i
+
M
i
))
.
(9.11)
We also define the
Maximum Exceeding Time
E
max
as the maximum among all
E
i
's
in the tasks set; that is,
E
max
=max
i
(
E
i
). Clearly, a schedule will be strictly feasible
if and only if
L
i
≥
0 for all tasks in the set, whereas it will be tolerant if and only if
there exists some
L
i
<
0,but
E
max
=0.
By this approach we can identify which tasks will miss their deadlines and compute
the amount of processing time required above the capacity of the system - the max-
imum exceeding time. This global view allows planning an action to recover from
the overload condition. Many recovering strategies can be used to solve this problem.
The simplest one is to reject the least-value task that can remove the overload situ-
ation. In general, we assume that, whenever an overload is detected, some rejection
policy will search for a subset
J
∗
of least-value tasks that will be rejected to maximize
the cumulative value of the remaining subset. The RED acceptance test is shown in
Figure 9.12.
1
If
M
i
=0
, the
Exceeding Time
is also called the
Tardiness
.
Search WWH ::
Custom Search