Hardware Reference
In-Depth Information
P
J
J
J
1
1
5
8
P
J
J
4
J
J
2
2
6
9
P
J
J
3
3
7
t
01
2
3
456789
0
11
12
13
14
15
Figure 2.21
Schedule of task set
J
on three processors, with computation times reduced
by one unit of time.
J
J
1
(3)
(9)
9
J
(4)
8
J
(2)
2
J
(4)
7
J
(2)
3
J
(4)
6
J
J
(2)
(4)
4
5
(a)
P
J
J
J
1
1
8
9
P
J
J
J
2
2
4
5
P
J
J
J
3
3
7
6
t
0
1
2
345678
9
10
11
12
13
14
15
16
(b)
Figure 2.22
a.
Precedence graph of task set
J
obtained by removing the constraints on
tasks
J
7
and
J
8
.
b.
Schedule of task set
J
on three processors, with precedence constraints
weakened.
PRECEDENCE CONSTRAINTS WEAKENED
Scheduling anomalies can also arise by removing precedence constraints from the
directed acyclic graph depicted in Figure 2.18. For instance, removing the precedence
relations between job
J
4
and jobs
J
7
and
J
8
(see Figure 2.22a), we obtain the schedule
shown in Figure 2.22b, which is characterized by a global completion time of
t
c
=16
units of time.
Search WWH ::
Custom Search