4
Scheduling Schemes
for Handling Overload
4.1 Scheduling Techniques in Overload
Conditions
This chapter presents several techniques to solve the problem of scheduling real-time
tasks in overload conditions. In such situations, the computation time of the task set
exceeds the time available on the processor and then deadlines can be missed. Even
when applications and the real-time systems have been properly designed, lateness can
occur for different reasons, such as missing a task activation signal due to a fault of
a device, or the extension of the computation time of some tasks due to concurrent
use of shared resources. Simultaneous arrivals of aperiodic tasks in response to some
exceptions raised by the system can overload the processor too. If the system is not
designed to handle overloads, the effects can be catastrophic and some paramount
tasks of the application can miss their deadlines. Basic algorithms such as EDF and
RM exhibit poor performance during overload situations and it is not possible to control
the set of late tasks. Moreover, with these two algorithms, one missed deadline can
cause other tasks to miss their deadlines: this phenomenon is called the domino effect.
Several techniques deal with overload to provide deadline missing tolerance. The
first algorithms deal with periodic task sets and allow the system to handle variable
computation times which cannot always be bounded. The other algorithms deal with
hybrid task sets where tasks are characterized with an importance value. All these
policies handle task models which allow recovery from deadline missing so that the
results of a late task can be used.
4.2 Handling Real-Time Tasks with Varying
Timing Parameters
A real-time system typically manages many tasks and relies on its scheduler to decide
when and which task has to be executed. The scheduler, in turn, relies on knowledge
about each task’s computational time, dependency relationships and deadline supplied
by the designer to make the scheduling decisions. This works quite well as long as the
execution time of each task is fixed (as in Chapters 2 and 3). Such a rigid framework is

tion time, period or deadline;
• on-line adaptive model, which calculates the largest possible timing parameters for
a task at any time;
• fault-tolerant mechanism based on minimum software, for a given task, which
ensures compliance with specified timing requirements in all circumstances.
4.2.1 Specific models for variable execution
task applications
In the context of specific models for tasks with variable execution times, two approaches
have been proposed: statistical rate monotonic scheduling (Atlas and Bestavros, 1998)
and the multiframe model for real-time tasks (Mok and Chen, 1997).
The first model, called statistical rate monotonic scheduling, is a generalization of the
classical rate monotonic results (see Chapter 2). This approach handles periodic tasks
with highly variable execution times. For each task, a quality of service is defined as
the probability that in an arbitrary long execution history, a randomly selected instance
of this task will meet its deadline. The statistical rate monotonic scheduling consists
of two parts: a job admission and a scheduler. The job admission controller manages
the quality of service delivered to the various tasks through admit/reject and priority
assignment decisions. In particular, it wastes no resource on task instances that will
miss their deadlines, due to overload conditions, resulting from excessive variability
in execution times. The scheduler is a simple, preemptive and fixed-priority scheduler.
This statistical rate monotonic model fits quite well with multimedia applications.
4.2 HANDLING REAL-TIME TASKS WITH VARYING TIMING PARAMETERS 81
t
1
t
2
t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

2
can simulate a program with two different paths which are
executed alternatively. Figure 4.1 illustrates the execution sequence obtained with this
multiframe model and a RM algorithm priority assignment.
4.2.2 On-line adaptive model
In the context of the on-line adaptive model, two approaches have been proposed: the
elastic task model (Buttazzo et al., 1998) and the scheduling adaptive task model (Wang
and Lin, 1994). In the elastic task model, the periods of task are treated as springs, with
given elastic parameters: minimum length, maximum length and a rigidity coefficient.
Under this framework, periodic tasks can intentionally change their execution rate
to provide different quality of service, and the other tasks can automatically adapt
their period to keep the system underloaded. This model can also handle overload
conditions. It is extremely useful for handling applications such as multimedia in which
the execution rates of some computational activities have to be dynamically tuned as
a function of the current system state, i.e. oversampling, etc. Consider, for example, a
set of three tasks with the following four parameters (r
i
,C
i
,D
i
,T
i
): τ
1
(0, 10, 20, 20),
τ
2
(0, 10, 40, 40) and τ
3

i,j
s
i,j
r
i,j
d
i,j −1
e
i,j −1
s
i,j −1
r
i,j −1
r
i,j −1
r
i,j +1
d
i,j
e
i,j
s
i,j
r
i,j
d
i,j −1
e
i
,

The scheduling adaptive model considers that the deadline of an adaptive task is set to
one period interval after the completion of the previous task instance and the release
time can be set anywhere before the deadline. The time domain must be divided
into frames of equal length. The main goal of this model is to obtain constant time
spacing between adjacent task instances. The execution jitter is deeply reduced with
this model while it can vary from zero to twice the period with a scheduling of classical
periodic tasks. Figure 4.2 shows a comparison between a classical task model and an
adaptive task model. The fundamental difference between the two models is in selecting
the release times, which can be set anywhere before the deadline depending on the
individual requirements of the task. So the deadline is defined as one period from the
previous task instance completion.
4.2.3 Fault-tolerant mechanism
The basic idea of the fault-tolerant mechanism, based on an imprecise computation
model, relies on making available results that are of poorer, but acceptable, quality
on a timely basis when results of the desired quality cannot be produced in time.
In this context, two approaches have been proposed: the deadline mechanism model
(Campbell et al., 1979; Chetto and Chetto, 1991) and the imprecise computation model
(Chung et al., 1990). These models are detailed in the next two subsections.
Deadline mechanism model
The deadline mechanism model requires each task τ
i
to have a primary program τ
p
i
and
an alternate one τ
a
i
. The primary algorithm provides a good quality of service which is
in some sense more desirable, but in an unknown length of time. The alternate program

1
(0, 2, 16, 16) and τ
2
(0, 6, 32, 32), and a task τ
3
with primary and alternate
programs. The alternate code τ
a
i
is defined by the classical fixed parameters (0, 2, 8, 8).
The primary program τ
p
i
has various computational durations at each instance; assume
that, for the first four instances, the execution times of task τ
p
i
are successively (4,
4, 6, 6). The scheduling is based on an RM algorithm for the three task τ
1
, τ
2
and
the alternate code τ
a
i
. The primary programs τ
p
i
are scheduled with the lowest priority