Real-Time Systems: Scheduling
--- University of Virginia, Charlottesville
Spring Scheduling Algorithm
The Spring scheduling algorithm is a dynamic, on-line solution that that
constructs guaranteed schedules based on deadlines, resources, precedence
contraints, values, etc. Many papers have been published on variations
of this algorithm. These scheduling algorithms
can be utilized off-line or on-line.
One sophisticated version of this
algorithm has been implemented in software as part of the Spring system
and in VLSI hardware (Spring
Other Scheduling Results
Related research in scheduling has produced results in the areas of allocating
complex periodic tasks, well-timed scheduling, and robust earliest deadline
scheduling. A new book on earliest dealine scheduling has been written
J. Stankovic, M. Spuri, K. Ramamritham, and G. Buttazzo, Deadline Scheduling
For Real-Time Systems: EDF and Related
Algorithms, Kluwer Academic Publishers, Boston, 1998.
Current scheduling work includes integration with high level AI planners,
scheduling multimedia sessions, and scheduling task sets with fault tolerance
requirements. Specific target applications such as steel mills (Mitsubishi),
flexible manufacturing, and chemical vapor deposition of gallium nitride
have also initiated modifications to the basic Spring scheduler. We have
also built, CAISARTS, a real-time scheduling expert assistant. This tool
provides conceptual, algorithmic (including analysis), and implementation
advice to real-time systems designers.
We are also working on the concept of a feedback control scheduling
paradigm that considers closed loop scheduling versus the common open loop
scheduling found in today's real-time systems. Our research goal is to
develop a theory and practice
of feedback control real-time scheduling.
J. Stankovic, C. Lu, S. Son, and G. Tao, The
Case for Feedback Control Real-Time Scheduling, EuroMicro Conference
on Real-Time Systems, June 1999.
C. Lu, J. Stankovic, G. Tao, and S. Son,
Design and Evaluation of a
Feedback Control EDF Algorithm, Real-Time Systems
C. Lu, J. Stankovic, T. Abdelzaher, G. Tao, S. Son, and M. Marley,
and Metrics for Adaptive Real-Time Systems, Real-Time Systems