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