Date of Award
5-14-2024
Degree Name
Doctor of Philosophy (PhD)
Degree Type
Dissertation
Abstract
In real-time computing systems, \textit{timely} execution is a requirement of \textit{correct} execution. Such systems are widely found in robotics and autonomous vehicle applications, mobile spectrometry of atmospheric aerosols, real-time hybrid simulation for natural hazards engineering, and in prompt localization of transients such as gamma-ray bursts for time-domain and multi-messenger astrophysics. \textit{Elastic scheduling} provides a framework to adjust computational rates and workloads in systems for which timeliness cannot otherwise be guaranteed. While originally proposed for periodic tasks executing on a single processor, elastic scheduling has since been extended to sequential and parallel execution on multiple processors and to earliest deadline first scheduling of constrained-deadline tasks. This dissertation expands the state of the art in elastic scheduling in three key directions. First, it proposes and analyzes new algorithms for elastic scheduling with provably better execution time complexity compared to the prior work, enabling better guarantees of timeliness associated with adapting to new execution states. Second, it presents new extensions of the elastic model to other common scheduling paradigms, including fixed-priority scheduling of constrained-deadline tasks and task systems for which execution semantics demand that periods take harmonic values. Third, it considers the impact of adaptation on system performance as a whole, and demonstrates how changes in task periods and workloads can be realized to optimize expected system outcomes within the constraints of schedulability. In doing so, this dissertation paves the way toward a richer set of adaptive scheduling and execution models in simulation, localization, and control applications.
Language
English (en)
Chair
Christopher Gill