BASIC CONCEPTS - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 43

J J

(3) (9)

1 9

J

(4)

8

J (2)

2

J (4)

7

J

(2)

3

J (4)

6

J J (2) (4)

4 5

∀

priority(J )
i

> priority(J ) i < j

j

Figure 2.18 Precedence graph of the task set J ; numbers in parentheses indicate compu-

tation times.

Designers should be aware of such insidious anomalies to take the proper countermea-
sures to avoid them. The most important anomalies are expressed by the following
theorem [Gra76, SSDNB95]:

Theorem 2.1 (Graham, 1976) If a task set is optimally scheduled on a multiproces-
sor with some priority assignment, a fixed number of processors, fixed execution times,
and precedence constraints, then increasing the number of processors, reducing ex-
ecution times, or weakening the precedence constraints can increase the schedule
length.

This result implies that, if tasks have deadlines, then adding resources (for example,
an extra processor) or relaxing constraints (less precedence among tasks or fewer exe-
cution times requirements) can make things worse. A few examples can best illustrate
why this theorem is true.

Let us consider a task set consisting of nine jobs J = , sorted by

decreasing priorities, so that J i priority is greater than J j priority if and only if i<j .
Moreover, jobs are subject to precedence constraints that are described through the
graph shown in Figure 2.18. Computation times are indicated in parentheses.

{ J 1 ,J 2 ,...,J 9 }

If this task set is executed on a parallel machine with three processors, where the
highest priority task is assigned to the first available processor, the resulting schedule
σ ∗ is illustrated in Figure 2.19, where the global completion time is t c =12units of
time.