Real-Time Systems: Scheduling
--- University of Virginia, Charlottesville
Jack Stankovic
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
Scheduling Co-processor).
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
and published.
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 Work
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.
Selected Publications
-
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
Symposium,
December 1999.
-
C. Lu, J. Stankovic, T. Abdelzaher, G. Tao, S. Son, and M. Marley,
Performance Specifications
and Metrics for Adaptive Real-Time Systems, Real-Time Systems
Symposium,
December 2000.