Hardware Reference
In-Depth Information
Algorithm: EDF guarantee(
J
,
J
new
)
{
J
=
J∪{
J
new
}
;
/* ordered by deadline */
t = current time();
f
0
=0;
for
(each
J
i
∈J
)
{
f
i
=
f
i−
1
+
c
i
(
t
);
if
(
f
i
>d
i
) return(UNFEASIBLE);
return(FEASIBLE);
}
Figure 3.7
EDF guarantee algorithm.
J
J
2
1
a
0
1
i
C
4
2
i
d
7
5
i
J
1
t
Optimal
schedule
J
2
t
0
1
2
3
4
5
6
7
8
(a)
J
1
t
EDF
schedule
J
2
t
0
1
2
3
4
5
6
7
8
(b)
Figure 3.8
EDF is not optimal in a non-preemptive model. In fact, although there exists
a feasible schedule (a), the schedule produced by EDF (b) is infeasible.
Search WWH ::
Custom Search