Hardware Reference
In-Depth Information
P
1
J
J
1
9
P
J
J
J
J
2
2
4
5
7
P
J
J
J
3
3
6
8
t
0
1
2
3
45678
9
10
11
12
13
14
15
Optimal schedule of task set
J
on a three-processor machine.
Figure 2.19
P
J
J
1
1
8
P
J
J
J
2
2
5
9
P
J
J
3
3
6
P
J
J
4
4
7
t
0
12
3
4
5
6
7
8
9
10
11
12
3 4 5
Figure 2.20
Schedule of task set
J
on a four-processor machine.
Now we will show that adding an extra processor, reducing tasks' execution times, or
weakening precedence constraints will increase the global completion time of the task
set.
NUMBER OF PROCESSORS INCREASED
If we execute the task set
J
on a more powerful machine consisting of four processors,
we obtain the schedule illustrated in Figure 2.20, which is characterized by a global
completion time of
t
c
=15units of time.
COMPUTATION TIMES REDUCED
One could think that the global completion time of the task set
J
could be improved by
reducing tasks' computation times of each task. However, we can surprisingly see that,
reducing the computation time of each task by one unit of time, the schedule length
will increase with respect to the optimal schedule
σ
∗
, and the global completion time
will be
t
c
=13, as shown in Figure 2.21.
Search WWH ::
Custom Search