Hardware Reference
In-Depth Information
preemptive
non-preemptive
sync. activation
async. activation
async. activation
Tree search
EDD
(Jackson '55)
EDF
(Horn '74)
(Bratley '71)
independent
2
O(n logn)
O(n )
O(n n!)
Optimal
Optimal
Optimal
*
EDF
Spring
(Stankovic &
LDF
(Lawler '73)
(Chetto et al. '90)
Ramamritham '87)
precedence
O(n )
2
O(n )
2
O(n )
2
constraints
Optimal
Optimal
Heuristic
Figure 3.17
Scheduling algorithms for aperiodic tasks.
Exercises
3.1
Check whether the Earliest Due Date (EDD) algorithm produces a feasible
schedule for the following task set (all tasks are synchronous and start at time
t
=0):
J
1
J
2
J
3
J
4
C
i
4
5
2
3
D
i
9
16
5
10
3.2
Write an algorithm for finding the maximum lateness of a task set scheduled
by the EDD algorithm.
3.3
Draw the full scheduling tree for the following set of non-preemptive tasks and
mark the branches that are pruned by the Bratley's algorithm.
J
1
J
2
J
3
J
4
a
i
0
4
2
6
C
i
6
2
4
2
D
i
18
8
9
10
3.4
On the scheduling tree developed in the previous exercise find the path pro-
duced by the Spring algorithm using the following heuristic function:
H
=
a
+
C
+
D
. Then find a heuristic function that produces a feasible schedule.
Search WWH ::
Custom Search