ORCID
https://orcid.org/0009-0008-5093-5441
Date of Award
Winter 12-18-2024
Degree Name
Master of Science (MS)
Degree Type
Thesis
Abstract
This work addresses hard real-time systems, in which tasks must be scheduled so that they are guaranteed to meet deadlines. In particular, when tasks execute across multiple domains with high preemption costs, the combined cost of these preemptions can cause the system to become unschedulable. The number of preemptions must therefore be bounded to limit the overall task execution time, while ensuring that task blocking times are small enough to allow the system to be schedulable. Prior work introduces the Multi-Phase Secure model, which describes a more exact version of this scenario, and an algorithm to determine schedulability of sporadic earliest-deadline first (EDF) tasks under this model by finding a set of preemption points. Here we adapt and improve upon that algorithm to resolve multiple correctness and performance issues, resulting in an orders-of-magnitude improvement to its execution time. We then extend the MPS model to fixed-priority scheduling by adapting prior algorithms for fixed-priority, limited-preemption task sets. Next, we consider representing the MPS problem as a constraint program. We demonstrate that such a program can feasibly solve the MPS scheduling problem for both EDF and fixed-priority scheduling, and has improved performance and flexibility when applied to fixed-priority partitioned multiprocessor scheduling. Finally, we investigate the feasibility of implementing the MPS model in a Linux-based system, and make recommendations for future system implementers.
Language
English (en)
Chair
Christopher Gill
Committee Members
Christopher Gill Sanjoy Baruah Marion Sudvarg