Date of Award
Spring 5-15-2023
Degree Name
Doctor of Philosophy (PhD)
Degree Type
Dissertation
Abstract
We apply the framework of parameterized algorithms to the FP (fixed-priority) and EDF (earliest- deadline-first) scheduling of recurrent (periodic and sporadic) task systems in a preemptive uniprocessor environment, which are fundamental models in real-time scheduling theory. We identify parameters for these models that allow the models to be analyzed efficiently; reciprocally, we pick out parameters for the models that should not lead to efficient analysis, in the absence of major algorithmic breakthroughs.Fixed-point iteration algorithms like RTA (response time analysis) and QPA (quick processor-demand analysis) are arguably the most popular ways of solving some of the fundamental problems mentioned above. We show that RTA and QPA are suboptimal cutting-plane algorithms for specific IP formulations of these problems, and we propose optimal cutting-plane algorithms for these IP formulations. These new algorithms have better convergence rates than RTA and QPA for every input instance, where the convergence rate is measured as the inverse of the number of iterations required for convergence.In the remainder of the thesis, we consider more sophisticated hardware models (processors with memory caches) and workload models (hybrid workloads that contain aperiodic tasks in addition to regular tasks), and we seek algorithmic results for these models.
Language
English (en)
Chair
Sanjoy Baruah Kunal Agrawal
Committee Members
Jeremy Buhler, Pontus Ekberg, Christopher Gill,