Sharp Thresholds for Scheduling Recurring Tasks with Distance Constraints

TitleSharp Thresholds for Scheduling Recurring Tasks with Distance Constraints
Publication TypeJournal Article
Year of Publication2008
AuthorsGopalakrishnan, S., M. Caccamo, and L. Sha
JournalComputers, IEEE Transactions on
Pagination344 -358
Date Publishedmar.
Keywordsdistance constraints, graph theory, performance optimization, phase transitions, radar, radar dwell scheduling problem, random graph theory, recurring task scheduling, sharp thresholds, system utilization

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.


a place of mind, The University of British Columbia

Electrical and Computer Engineering
2332 Main Mall
Vancouver, BC Canada V6T 1Z4
Tel +1.604.822.2872
Fax +1.604.822.5949

Emergency Procedures | Accessibility | Contact UBC | © Copyright 2021 The University of British Columbia