Hardware Reference
In-Depth Information
3.3.2
EXAMPLE
An example of schedule produced by the EDF algorithm on a set of five tasks is shown
in Figure 3.6. At time
t
=0, tasks
J
1
and
J
2
arrive and, since
d
1
<d
2
, the processor
is assigned to
J
1
, which completes at time
t
=1. At time
t
=2, when
J
2
is executing,
task
J
3
arrives and preempts
J
2
, being
d
3
<d
2
. Note that, at time
t
=3, the arrival
of
J
4
does not interrupt the execution of
J
3
, because
d
3
<d
4
.As
J
3
is completed, the
processor is assigned to
J
2
, which resumes and executes until completion. Then
J
4
starts at
t
=5, but, at time
t
=6, it is preempted by
J
5
, which has an earlier deadline.
Task
J
4
resumes at time
t
=8, when
J
5
is completed. Notice that all tasks meet their
deadlines and the maximum lateness is
L
max
=
L
2
=0.
J
J
2
J
3
J
4
J
5
1
a
i
0
0
2
3
6
C
12
2
2
2
i
d
2
5
4
10
9
i
J
1
t
J
2
t
J
3
t
J
4
t
J
5
t
0
1
2
3
4
5
6
7
8
9
10
Figure 3.6
Example of EDF schedule.
3.3.3
GUARANTEE
When tasks have dynamic activations and the arrival times are not known a priori, the
guarantee test has to be done dynamically, whenever a new task enters the system.
Let
J
be the current set of active tasks, which have been previously guaranteed, and
Search WWH ::
Custom Search