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.

Committee Chair

Christopher Gill

Committee Members

Christopher Gill Sanjoy Baruah Marion Sudvarg

Degree

Master of Science (MS)

Author's Department

Computer Science & Engineering

Author's School

McKelvey School of Engineering

Document Type

Thesis

Date of Award

Winter 12-18-2024

Language

English (en)

Author's ORCID

https://orcid.org/0009-0008-5093-5441

Download

Share

COinS