Hardware Reference
In-Depth Information
SOLUTIONS FOR CHAPTER 3
3.1
To check whether the EDD algorithm produces a feasible schedule, tasks must
be ordered with increasing deadlines, as shown in Table 13.1:
J
1
J
2
J
3
J
4
C
i
2
4
3
5
D
i
5
9
10
16
Table 13.1
Task set ordered by deadline.
Then applying Equation (3.1) we have
f
1
C
1
=2
=
f
2
f
1
+
C
2
=6
=
f
3
f
2
+
C
3
=9
=
f
4
f
3
+
C
4
=14
=
Since each finishing time is less than the corresponding deadline, the task set
is schedulable by EDD.
3.2
The algorithm for finding the maximum lateness of a task set scheduled by the
EDD algorithm is shown in Figure 13.1.
3.3
The scheduling tree constructed by the Bratley's algorithm for the following
set of non-preemptive tasks is illustrated in Figure 13.2.
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
Table 13.2
Task set parameters for the Bratley's algorithm.
3.4
The schedule found by the Spring algorithm on the scheduling tree developed
in the previous exercise with the heuristic function
H
=
a
+
C
+
D
is
{
J
2
,
J
4
,
J
3
,
J
1
}
, which is unfeasible, since
J
3
and
J
4
miss their deadlines. Noted that
the feasible solution is found with
H
=
a
+
d
.
Search WWH ::
Custom Search