Hardware Reference
In-Depth Information
Algorithm: RED Acceptance Test
Input:
A task set
J
with
{
C
i
,D
i
,V
i
,M
i
}
,
∀
J
i
∈J
Output:
A schedulable task set
//
Assumes deadlines are ordered by decreasing values
begin
(1)
E
=0;
//
Maximum Exceeding Time
(2)
L
0
=0;
(3)
d
0
=
current time
();
(4)
J
=
J
∪{
J
new
}
;
(5)
in the task set
J
>
;
k
=
<
position of
J
new
(6)
for
(each task
J
i
such that
i
≥
k
)
do
(7)
L
i
=
L
i−
1
+(
d
i
−
d
i−
1
)
−
c
i
;
(8)
if
(
L
i
+
M
i
<
−
E
)
then
//
compute
E
max
(9)
E
=
−
(
L
i
+
M
i
);
(10)
end
(11)
end
(12)
if
(
E>
0)
then
(13)
<
select a set
J
∗
of least-value tasks to be rejected
>
;
(14)
<
reject all task in
J
∗
>
;
(15)
end
(16)
end
(17)
Figure 9.12
The RED acceptance test.
A simple rejection strategy consists in removing the task with the smallest value that
resolves the overload. To quickly identify the task to be rejected, we can keep track of
the
First Exceeding Task
, denoted as
J
FET
, which is the task with the earliest primary
deadline that misses its secondary deadline. The FET index can be easily determined
within the
for
loop in which residual each laxity is computed. Note that in order to
resolve the overload, the task to be rejected must have a residual computation time
greater than or equal to the maximum exceeding time and a primary deadline less than
d
FET
. Hence, the rejection strategy can be expressed as follows:
Reject the task
J
r
with the least value, such that
(
r
≤
FET) and (
c
r
(
t
)
≥
E
max
)
Search WWH ::
Custom Search