Hardware Reference
In-Depth Information
L
=−
f
a
d
a
σ
J
b
J
a
a
max
'
'
'
L
=
max (L , L )
J
a
J
b
σ
a
max
b
'
a
f
'
f
'
t
f
b
=
f
a
d
a
d
0
b
'
'
'
'
if
(
L
>
L
)
then
L
=
f
a
−<
d
a
f
a
−
d
a
a
b
a
max
'
in both cases:
L
<
L
a
max
a
max
'
'
'
=f
'
if
(
L
<
L
)
then
L
−<
d
b
f
a
−
d
a
a
b
a
max
Figure 3.1
Optimality of Jackson's algorithm.
3.2.1
EXAMPLES
EXAMPLE 1
Consider a set of five tasks, simultaneously activated at time
t
=0, whose parame-
ters (worst-case computation times and deadlines) are indicated in the table shown in
Figure 3.2. The schedule of the tasks produced by the EDD algorithm is also depicted
in Figure 3.2. The maximum lateness is equal to
1 and it is due to task
J
4
, which
completes a unit of time before its deadline. Since the maximum lateness is negative,
we can conclude that all tasks have been executed within their deadlines.
−
Note that the optimality of the EDD algorithm cannot guarantee the feasibility of the
schedule for any task set. It only guarantees that if a feasible schedule exists for a task
set, then EDD will find it.
EXAMPLE 2
Figure 3.3 illustrates an example in which the task set cannot be feasibly scheduled.
Still, however, EDD produces the optimal schedule that minimizes the maximum late-
ness. Note that since
J
4
misses its deadline, the maximum lateness is greater than zero
(
L
max
=
L
4
=2).
Search WWH ::
Custom Search