Sharp thresholds for scheduling recurring tasks with distance constraints

Sathish Gopalakrishnan, Marco Caccamo, Lui Sha

Research output: Contribution to journalArticlepeer-review

16 Scopus citations

Abstract

The problem of identifying suitable conditions for the schedulability of (nonpreemptive) recurring tasks with deadlines is of great importance to real-time systems. In this paper, motivated by the problem of scheduling radar dwells, we show that scheduling problems of this nature show a sharp threshold behavior with respect to system utilization. Sharp thresholds are associated with phase transitions: When the utilization of a task set is less than a critical value, it can be scheduled almost surely and, when the utilization increases beyond the critical level, almost no task set can be scheduled. We make connections to work on random graphs to prove the sharp threshold behavior in the scheduling problem of interest. Using extensive experiments, we determine the threshold for the radar dwell scheduling problem and use it for performance optimization. The connections to random graph theory suggest new ways for understanding the average-case behavior of scheduling policies. These results emphasize the ease with which performance can be controlled in a variety of real-time systems.

Original languageEnglish
Pages (from-to)344-358
Number of pages15
JournalIEEE Transactions on Computers
Volume57
Issue number3
DOIs
StatePublished - Mar 2008
Externally publishedYes

Keywords

  • Phase transitions
  • QoS optimization
  • Radar systems
  • Real-time systems
  • Scheduling
  • Sharp thresholds

Fingerprint

Dive into the research topics of 'Sharp thresholds for scheduling recurring tasks with distance constraints'. Together they form a unique fingerprint.

Cite this