6
Joint Scheduling of Tasks
and Messages in Distributed
Systems
This chapter and the next one discuss mechanisms to support real-time communica-
tions between remote tasks. This chapter deals with some techniques used in multiple
access local area networks and Chapter 7 deals with packet scheduling when the
communications are supported by packet-switching networks such as ATM or IP-
based networks.
6.1 Overview of Distributed Real-Time Systems
The complexity of control and supervision of physical processes, the high number of
data and events dealt with, the geographical dispersion of the processes and the need
for robustness of systems on one hand, and the advent, for several years, on the market
of industrial local area networks on the other, have all been factors which resulted in
reconsidering real-time applications (Stankovic, 1992). Thus, an information processing
system intended to control or supervise operations (for example, in a vehicle assembly
factory, in a rolling mill, or in an aircraft) is generally composed of several nodes,
which may be central processing units (computers or programmable automata), sensors,
actuators, or peripherals of visualization and dialogue with operators. The whole of
these nodes is interconnected by a network or by a set of interconnected networks
(industrial local area networks, fieldbuses, etc.) (Pimentel, 1990). These systems are
called distributed real-time systems (Kopetz, 1997; Stankovic, 1992).
Several aspects have to be distinguished when we speak about distributed systems.
First of all, it is necessary to differentiate the physical (or hardware) allocation from
the software allocation. The hardware allocation is obtained by using several cen-
tral processing units which are interconnected by a communication subsystem. The
taxonomy is more complex when it is about the software. Indeed, it is necessary to
distinguish:
• data allocation (i.e. the assignment of data to appropriate nodes);
• processing allocation (i.e. the assignment of tasks to appropriate nodes);
• control allocation (i.e. the assignment of control roles to nodes for starting tasks;

composing the distributed system (while possibly carrying out migrations of tasks).
Thus, a local scheduling aims to answer the question of ‘when to execute a task on
the local processor, so as to guarantee the constraints imposed on this task?’. A global
scheduling seeks to answer the question ‘which is the node best adapted to execute a
given task, so as to guarantee its constraints?’.
In distributed real-time applications, task allocation and scheduling are closely
related: it is necessary to allocate the tasks to the set of processors so that local
scheduling leads imperatively to the guarantee of the time constraints of the critical
tasks. Local scheduling uses algorithms like those presented in the preceding chapters
(i.e. rate monotonic, earliest deadline first, and so on). We are interested here in global
scheduling, i.e. with allocation and migration of tasks, and with support for real-time
communications.
The problem of allocating n tasks to p processors often consists in initially seeking
a solution which respects the initial constraints as much as possible, and then to choose
the best solution, if several solutions are found. The search for a task allocation must
take into account the initial constraints of the tasks, and the support environment, as
well as the criteria (such as maximum lateness, scheduling length, number of processors
used) to optimize.
6.3 REAL-TIME TRAFFIC 105
The tasks composing a distributed application can be allocated in a static or dynamic
way to the nodes. In the first case, one speaks about static allocation; in the second, of
dynamic allocation. In the first case, there cannot be any additional allocations of the
tasks during the execution of the application; the allocation of the tasks is thus fixed
at system initialization. In the second case, the scheduling algorithm chooses to place
each task on the node capable of guaranteeing its time constraints, at the release time
of the task.
Dynamic allocation algorithms make it possible to find a node where a new task
will be executed. If a task allocated to a node must be executed entirely on the node
which was chosen for it, one speaks about a distributed system ‘without migration’;
if a task can change node during its execution, one speaks about a distributed system

106 6 JOINT SCHEDULING OF TASKS AND MESSAGES IN DISTRIBUTED SYSTEMS
of the original transmission. This distortion is particularly damaging to multimedia
traffic. For example, the playback of audio or video data may have a jittery or
shaky quality.
In a way similar to tasks, one can distinguish three types of messages:
• Periodic (also called synchronous) messages are generated and consumed by peri-
odic tasks, and their characteristics are similar to the characteristics of their respec-
tive source tasks. Adopting the notation used for periodic tasks, a periodic message
M
i
is usually denoted by a 3-tuple (T
i
,L
i
,D
i
). This means that the instances of
message M
i
are generated periodically with a period equal to T
i
, the maximum
length of M
i
’s instances is L
i
bits, and each message instance must be delivered
to its destination within D
i
time units. D

s
. AT
s
is the average inter-arrival
time, where the average is taken over a time interval of length I
s
.
• Aperiodic messages are generally generated by aperiodic tasks and they are char-
acterized by their maximum length and end-to-end delay.
In addition to the previous parameters, which are similar to the ones associated with
tasks, other parameters inherent to communication networks, such as message loss rate,
may be specified in the case of real-time traffic.
6.3.2 End-to-end communication delay
Communication delay between two tasks placed on the same machine is often consid-
ered to be negligible. It is evaluated according to the machine instructions necessary
to access a data structure shared by the communicating tasks (shared variables, queue,
etc.). The communication delay between distant tasks (i.e. tasks placed on differ-
ent nodes) is much more complex and more difficult to evaluate with precision. The
methods of computation of the communication delay differ according to whether the
nodes on which the communicating tasks are placed are directly connected — as is
the case when the application uses a local area network with a bus, loop or star topol-
ogy — or indirectly connected — as is the case when the application uses a meshed
network. When the communicating nodes are directly connected, the communication
delay between distant tasks can be split into several intermediate delays, as shown in
Figure 6.1:
• A delay of crossing the upper layers within the node where the sending task is
located (d
1
). The upper layers include the application, presentation and transport
layers of the OSI model when they are implemented.

1
d
6
d
5
d
2
d
3
d
5
d
6
Figure 6.1 Components of end-to-end delay of communication between two tasks when tasks
are allocated to nodes directly connected by a local area network
• A queuing delay in the medium access control (MAC) sublayer of the sending node
(d
2
). This queuing delay is the most difficult to evaluate.
• A delay of physical transmission of the message on the medium (d
3
).
• A delay of propagation of a bit on the medium up to the receiving node (d
4
).
• A delay of reception and waiting time in the MAC sublayer of the receiving
node (d
5
).
• A delay of crossing the upper layers in the node where the receiving task is

is directly related to the medium access control of the network. The upper bound of
this delay is guaranteed by reserving the medium at the right time for messages. There
is no single solution for this problem. The technique of medium reservation depends
on the MAC protocol of the network used. We will reconsider this problem by taking
examples of networks (see Section 6.4.3).
When the communicating tasks are allocated to nodes that are not directly connected,
in a network such as ATM or the Internet, the end-to-end transfer delay is determined by
considering the various communication delays along the path going from the sending
node to the receiving node. The techniques of bandwidth reservation and scheduling of
real-time messages are much more complex in this case. The next chapter will focus
on these techniques in the case of packet-switching networks.
6.4 Message Scheduling
6.4.1 Problems of message scheduling
Distributed real-time applications impose time constraints on task execution, and these
constraints are directly reflected on the messages exchanged between the tasks when
they are placed on different nodes. The guarantee (or non-guarantee) of the time con-
straints of messages is directly reflected on those of tasks, because waiting for a
message is equivalent to waiting for the acquisition of a resource by a task; if the
message is not delivered in time, the time constraints of the task cannot be guaranteed.
In real-time applications, certain tasks can have hard time constraints and others
not. Similarly, the messages exchanged between these tasks can have hard time con-
straints or not. For example, a message indicating an alarm must be transmitted and
received with hard time constraints in order to be able to treat the cause of the alarm
before it leads to a failure, whereas a file transfer does not generally require hard time
constraints.
Communication in real-time systems has to be predictable, because unpredictable
delays in the delivery of messages can adversely affect the execution of tasks depen-
dent on these messages. If a message arrives at its destination after its deadline has
expired, its value to the end application may be greatly reduced. In some circumstances
messages are considered ‘perishable’, that is, are useless to the application if delayed

• Each node of task location connected to the network is regarded as a subscriber
(or client) and does not know the protocols used inside the switching network.
• To transmit its data, each subscriber node establishes a connection according to a
traffic contract specifying a certain quality of service (loss rate, maximum transfer
delay, etc.). Subscriber nodes can neither enter into competition with each other,
nor consult each other, to know which node can transmit data. A subscriber node
addresses its requests to the network switch (an ATM switch or an IP router, for
example) to which it is directly connected, and this switch (or router) takes care of
the message transfer according to the negotiated traffic contract.
• The time constraints are entirely handled by the network switches (or routers),
provided that each subscriber node negotiates a sufficient quality of service to take
into account the characteristics of messages it wishes to transmit. Consequently,
the resource reservation mechanisms used are implemented in the network switches
(or routers) and not in the subscriber nodes.
2. Multiple access local area networks (LAN)
• The nodes connected to the network control the access to the medium via a MAC
technique implemented on each node. Generally, a node obtains the right to access
the shared medium either by competition, or by consultation (by using a token, for
example) according to the type of MAC technique used by the LAN.
• Once a node has sent a frame on the medium, this frame is directly received by its
recipient (obviously excepting the case of collision with other frames or the use of
a network with interconnection equipment such as bridges).
• The nodes must be set up (in particular, by setting message or node priorities,
token holding times, and so on) to guarantee message time constraints. Conse-
quently, resource reservation mechanisms are implemented in the nodes supporting
the tasks.
110 6 JOINT SCHEDULING OF TASKS AND MESSAGES IN DISTRIBUTED SYSTEMS
Techniques to take into account time constraints are similar, whether they are integrated
above the MAC sublayer, in the case of LANs, or in the network switches, in the case of
packet-switching networks. They rely on the adaptation of task scheduling algorithms

With the emergence of distributed real-time systems, new needs for scheduling
appeared: it is necessary, at the same time, to guarantee the time constraints of the tasks
and those of the messages. As messages have similar constraints (mainly deadlines)
as tasks, the scheduling of real-time messages uses techniques similar to those used in
the scheduling of tasks.
Whereas tasks can, in general, accept preemption without corrupting the consis-
tency of the results that they elaborate, the transmission of a message does not admit
preemption. If the transmission of a message starts, all the bits of the message must be
6.4 MESSAGE SCHEDULING 111
transmitted, otherwise the transmission fails. Thus, some care must be taken to apply
task scheduling algorithms to messages:
• one has to consider only non-preemptive algorithms;
• one has to use preemptive algorithms with the proviso that transmission delays of
messages are lower than or equal to the basic time unit of allocation of the medium
to nodes;
• one has to use preemptive algorithms with the proviso that long messages are
segmented (by the sending node) in small packets and reassembled (by the receiving
node). The segmentation and reassembly functions must be carried out by a layer
above the MAC sublayer; traditionally, these functions concern the transport layer.
Some communication protocols provide powerful mechanisms to take into account time
constraints. This is the case, in particular, of FDDI and token bus protocols, which
make it possible to easily treat periodic messages. Other, more general, protocols like
CSMA/CD require additional mechanisms to deal with time constraints. Consequently,
scheduling, and therefore the adaptation of task scheduling algorithms to messages,
are closely related to the type of time constraints (in particular, whether messages are
periodic or aperiodic) and the type of protocol (in particular, whether the protocol
guarantees a bounded waiting time or not). The reader eager to look further into the
techniques of message scheduling can refer to the synthesis presented in Malcolm and
Zhao (1995). In the following section, we treat the scheduling of a set of messages,
and consider three basically different types of protocols (token bus, FIP and CAN).

bus, with priorities, is the following:
• at network initialization, the following parameters are set:
– a token holding time (THT), which indicates the amount of time each node
can transmit its frames each time it receives the token for transmitting its data
of priority 6 (this time is sometimes called synchronous allocation),
– three counters TRT
4
,TRT
2
and TRT
0
. Counter TRT
4
(token rotation time for
priority 4) limits the transmission time of frames with priority 4, according to
the effective time taken by the current token rotation time. Counters TRT
2
and
TRT
0
have the same significance as TRT
4
for priorities 2 and 0.
• Each node uses a counter (TRT) to measure the token rotation time. When any
node receives the token:
– It stores the current value of TRT in a variable (let us call it V ), resets TRT
and starts it.
– It transmits its data of priority 6, for an amount of time no longer than the
value of its THT.
– Then, the node can transmit data of lower priorities (respecting the order of