Hardware Reference
In-Depth Information
τ
1
τ
2
2
J
k
0
2
4
6
8
10
12
14
16
18
20
Schedule produced by EDF with
d
k
=14
Figure 6.10
.
d
k
f
k
step
0
14
12
1
12
9
2
9
8
3
8
6
4
6
5
5
5
5
Table 6.2
Deadlines and finishing times computed by the algorithm.
In this case, it can easily be verified that the aperiodic task actually terminates at
t
=12. This happens because the periodic tasks do not leave any idle time to the
aperiodic task, which is thus compelled to execute at the end. Table 6.2 shows the
subsequent deadlines evaluated at each step of the algorithm. In this example, six
steps are necessary to find the shortest deadline for the aperiodic request.
The schedule produced by EDF using the shortest deadline
d
k
=
d
k
=5is shown in
Figure 6.11. Notice that at
t
=19the first idle time is reached, showing that the whole
task set is schedulable.
6.7.2
OPTIMALITY
As far as the average case execution time of tasks is equal to the worst-case one, our
deadline assignment method achieves optimality, yielding the minimum response time
for each aperiodic task. Under this assumption, the following theorem holds.
Search WWH ::
Custom Search