Sharp thresholds for scheduling recurring tasks with distance constraints

Sathish Gopalakrishnan, Marco Caccamo, Lui Sha

Research output: Contribution to journalArticlepeer-review


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 (US)
Pages (from-to)344-358
Number of pages15
JournalIEEE Transactions on Computers
Issue number3
StatePublished - Mar 2008


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

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


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

Cite this