Many real-time systems rely on static scheduling algorithms. This
includes cyclic scheduling, rate monotonic scheduling and fixed
schedules created by off-line scheduling techniques such as dynamic
programming, heuristic search, and simulated annealing. However, for
many real-time systems, static scheduling algorithms are quite
restrictive and inflexible. For example, highly automated agile
manufacturing, command, control and communications, and distributed
real-time multimedia applications all operate over long lifetimes and in
highly non-deterministic environments. Dynamic real-time scheduling
algorithms are more appropriate for these systems and are used in such
systems. Many of these algorithms are based on earliest deadline first
(EDF) policies. There exists a wealth of literature on EDF-based
scheduling with many extensions to deal with sophisticated issues such
as precedence constraints, resource requirements, system overload,
multi-processors, and distributed systems.
Deadline Scheduling for Real-Time Systems: EDF and Related Algorithms
aims at collecting a significant body of knowledge on EDF scheduling for
real-time systems, but it does not try to be all-inclusive (the
literature is too extensive). The book primarily presents the algorithms
and associated analysis, but guidelines, rules, and implementation
considerations are also discussed, especially for the more complicated
situations where mathematical analysis is difficult.
In general, it is very difficult to codify and taxonomize scheduling
knowledge because there are many performance metrics, task
characteristics, and system configurations. Also, adding to the
complexity is the fact that a variety of algorithms have been designed
for different combinations of these considerations. In spite of the
recent advances there are still gaps in the solution space and there is
a need to integrate the available solutions. For example, a list of
issues to consider includes:
-
preemptive versus non-preemptive tasks,
-
uni-processors versus multi-processors,
-
using EDF at dispatch time versus EDF-based planning,
-
precedence constraints among tasks,
-
resource constraints,
-
periodic versus aperiodic versus sporadic tasks,
-
scheduling during overload,
-
fault tolerance requirements, and
-
providing guarantees and levels of guarantees (meeting quality of
service requirements).
Deadline Scheduling for Real-Time Systems: EDF and Related Algorithms
should be of interest to researchers, real-time system designers, and
instructors and students, either as a focussed course on deadline-based
scheduling for real-time systems, or, more likely, as part of a more
general course on real-time computing. The book serves as an invaluable
reference in this fast-moving field.
