Content area
Real-time systems typically have two conflicting requirements: computations must provably satisfy application-specific timing constraints, and the system must efficiently utilize the underlying processing resources to meet constraints related to size, weight, power, and cost. Satisfying timing constraints while ensuring high resource utilization requires the formal analysis of such systems to be as tight as possible. Unfortunately, obtaining tight analysis for even simple real-time systems is computationally intractable, often leading to inefficient resource utilization. In today’s artificial-intelligence-powered real-time systems, this challenge is further exacerbated by complex workloads involving parallel real-time tasks, precedence constraints, and non-processing shared resources. Moreover, these workloads are often deployed on multiprocessor platforms augmented with hardware accelerators, introducing additional complexities.
The goal of this dissertation is to take a step toward tighter analysis of real-time systems exhibiting complex runtime behaviors due to precedence constraints, shared resources, and parallelism. The analyses presented here focus on two types of resource-management algorithms: scheduling algorithms and synchronization algorithms. The specific contributions of this dissertation are threefold:
First, this dissertation presents a polynomial-time tight response-time analysis for a practically common class of sequential tasks under global earliest-deadline-first (G-EDF) scheduling and its variants. It also presents an exact response-time analysis for such systems that can be performed in pseudo-polynomial time. Furthermore, the analysis is extended to systems with precedence constraints.
Second, this dissertation presents an optimal suspension-based locking protocol for mutual exclusion sharing under first-in-first-out (FIFO) scheduling. It also establishes new lower-bound results to show that existing asymptotically optimal suspension-based locking protocols for mutual exclusion under G-EDF and its variants are nearly optimal.
Finally, this dissertation presents response-time analysis for parallel tasks with co-scheduling requirements, known as gang tasks, both with and without precedence constraints. It also provides intractability results for scheduling gang tasks—even in systems with soft timing constraints—and demonstrates that G-EDF and FIFO are not optimal for such systems.