5
Multiprocessor Scheduling
5.1 Introduction
In this chapter, we limit the study to multiprocessor systems with centralized control
that are called ‘strongly coupled systems’. The main characteristics of such systems are
the existence of a common base of time (for global scheduling of events and tasks) and
a common memory (for implementing the vector of communication between tasks).
Consequently, one has a global view of the state of the system accessible at every
moment. In addition to the common memory, which contains the whole of the code
and the data shared by the different tasks, the processors can have local memory (stack,
cache memory, and so on). These systems present strong analogies with the centralized
systems (uniprocessor) while primarily being different by their capacity to implement
parallel execution of tasks. In a multiprocessor environment, a scheduling algorithm
is valid if all task deadlines are met. This definition, identical to the one used in the
uniprocessor context, is extended with the two following conditions:
• a processor can execute only one task at any time;
• a task is treated only by one processor at any time.
The framework of the study presented here is limited to the most common architec-
ture, which is made up of identical processors (identical speed of processing) with
an on-line preemptive scheduling. In this book, we do not treat off-line scheduling
algorithms, which are often very complex, and not suitable for real-time systems. It
is, however, important to note that off-line algorithms are the only algorithms which
make it possible to obtain an optimal schedule (by the resolution of optimization prob-
lems of linear systems) and to handle some configurations unsolved by an on-line
scheduling algorithm.
5.2 First Results and Comparison
with Uniprocessor Scheduling
The first significant result is a theorem stating the absence of optimality of on-line
scheduling algorithms (Sahni, 1979):
Theorem 5.1:
An on-line algorithm which builds a feasible schedule for any set of tasks with

m

j =1
U
j
=
n

i=1
u
i
=
n

i=1
C
i
P
i
≤ m(5.1)
where u
i
is the processor utilization factor of task
τ
i
.
A third result is related to the schedule length, which is identical to that in the unipro-
cessor environment:
Theorem 5.2:
There is a feasible schedule for a set of periodic and independent tasks if and

0
= 0,C = 3,D =
3,T = 10), τ
3
(r
0
= 1,C = 2,D = 3,T = 10), τ
4
(r
0
= 2,C = 3,D = 3,T = 10)} to
execute on two processors, Proc
1
and Proc
2
. The EDF schedule does not respect the
deadline of task τ
4
, whereas there are feasible schedules as shown in Figure 5.1b.
(a) Infeasible schedule according to the EDF algorithm

τ
1
τ
3
τ
4
τ
1
τ

t

4 6 5 7
(b) Feasible schedule
Missed deadline
Figure 5.1 Example showing that the EDF algorithm is not optimal in the multiprocessor
environment
5.3 MULTIPROCESSOR SCHEDULING ANOMALIES 95
5.3 Multiprocessor Scheduling Anomalies
It is very important to stress that some applications, which are executed in a multipro-
cessor environment, are prone to anomalies at the time of apparently positive changes
of parameters. Thus, it was proven that (Graham, 1976):
Theorem 5.3:
If a task set is optimally scheduled on a multiprocessor with some priority assign-
ment, a fixed number of processors, fixed execution times, and precedence con-
straints, then increasing the number of processors, reducing computation times, or
weakening the precedence constraints can increase the schedule length.
This results implies that if tasks have deadlines, then adding resources (for instance,
adding processors) or relaxing constraints can make things worse. The following
example can best illustrate why Graham’s theorem is true.
Let us consider a set of six tasks that accept preemption but not migration (i.e.
the tasks cannot migrate from one processor to another during execution). These tasks
have to be executed on two identical processors using a fixed-priority based schedul-
ing algorithm (external priorities of tasks are fixed as indicated by Table 5.1). The
Table 5.1. Set of six tasks to highlight anomalies
of multiprocessor scheduling
Tas k r
i
C
i

2
= 2

C
2
= 6

5010
t
15 20 25
5010
t
15 20 25
τ
1
τ
5
τ
2
τ
4
τ
3
τ
1
τ
3
τ
2
τ

15 20 25
5010
t
15 20 25
C
2
= 3
C
2
= 5
5010
t
15 20 25
5010
t
15 20 25
τ
1
τ
5
τ
2
τ
4
τ
3
τ
1
τ
3

2
taken inside the fixed interval
computation time of task τ
2
is in the interval [2, 6]. The current analysis in the unipro-
cessor environment consists of testing the schedulability of a task set for the bounds
of the task computation time interval. The results presented in Figure 5.2 show a fea-
sible schedule for each one of the bounds of the computation time interval C
2
with,
however, a phenomenon of priority inversion between tasks τ
4
and τ
5
for the weakest
computation time of task τ
2
.
The schedules, built for two other values of C
2
taken in the fixed interval, show the
anomalies of multiprocessor scheduling (Figure 5.3): an infeasible schedule for C
2
= 3
(missed deadlines for tasks τ
4
and τ
6
), and a feasible schedule for C
2

The priority assignment is done according to the following rule (Andersson et al.,
2001):
• if u
i
>m/(3m − 2) then τ
i
has the highest priority and ties are broken arbitrarily
but in a consistent manner (always the same for the successive instances);
• if u
i
≤ m/(3m − 2) then τ
i
has the RM priority (the smaller the period, the higher
the priority).
With this priority assignment algorithm, we have a sufficient schedulability condition
(Andersson et al., 2001):
Sufficient condition:
A set of periodic and independent tasks with periods equal to deadlines such that
T
i
≥ T
i+1
for i ∈ [1,n− 1] is schedulable on m identical processors if:
U ≤
m
2
3m − 2
(5.2)
Consider an example of a set of five tasks to be scheduled on a platform of three
identical unit-speed processors (m = 3). The temporal parameters of these tasks are:

3
and τ
4
• u
i
≤
m
3m − 2
= 0.4286 for the other tasks τ
1
, τ
2
and τ
5
Hence, tasks τ
3
and τ
4
will be assigned the highest priorities and the remaining three
tasks will be assigned according to RM priorities. The possible priority assignments are
therefore as follows in a decreasing priority order: τ
3
, τ
4
, τ
1
, τ
2
, τ
5