Real-Time Scheduling of Mixed-Critical Workloads upon Platforms with Uncertainties

In designing safety-critical real-time systems, there is an emerging trend in moving towards mixed-criticality (MC), where functionalities with different degrees of importance (i.e., criticality) are implemented upon a shared platform. Since 2007, there has been a large amount of research in MC scheduling, most of which considers the Vestal Model. In this model, all kinds of uncertainties in the system are characterized into the workloads by assuming multiple worst-case execution time (WCET) estimations for each execution (of a piece of code). However, uncertainties of estimations may arise from different aspects (instead of WCET only), especially upon more widely used commercial-off-the-shelf (COTS) hardware that typically provides good average-case performance rather than worst-case guarantees. This dissertation addresses two questions fundamental to the modeling and analyzing of such MC real-time systems: (i) Can Vestal model be used to describe all kinds of uncertainties at no significant analytical capacity loss? (ii) If not, can new mechanisms be developed with better performances over existing ones (in MC scheduling theory), under certain assumptions? To answer these questions, we first investigate the Vestal model carefully. We propose a new algorithm (named LE-EDF) which dominates state-of-the-art schedulers for MC job scheduling. We also improve the understanding of certain existing algorithms by proving a better (and even optimal) speedup bound. We have found that by introducing the probabilistic WCET workload model into MC scheduling, the uncertain behaviors can be better characterized comparing to Vestal model in the sense of schedulability ratio via experiments. We then present a new MCsystem model to describe the uncertainties arising from the platform’s performance. We show that under this model, where uncertainties of execution speed are separately captured, better schedulability results can be achieved compared to using the Vestal model instead. We propose a linear programming (LP) based algorithm for scheduling MC job set on uniprocessor platforms, and show its optimality (i.e., with zero analytical capacity loss), in the sense that it dominates any existing MC scheduler. Under the fluid (processor sharing) scheme, we further show that the optimality result can be retained even when the work is extended to multiprocessor scheduling and MC task scheduling. This thesis further addresses the two questions by studying cases where uncertainties arise from more than one aspect, by integrating both dimensions of uncertainties (i.e., WCET estimation and system performance) within a single integrated framework and designing scheduling algorithms with associated schedulability tests. The proposed LE-EDF algorithm is shown to be well applicable for MC job scheduling. While For MC task scheduling, we adapt an existing algorithm named EDF-VD, and show that it has the same worst-case analytical capacity loss; i.e., the framework generalization is available “for free” at least from the perspective of speedup factor. Under many cases, experimental studies upon randomly generated workloads are conducted to verify and quantify the theoretically proven domination relationships for both uniprocessor and multiprocessor scenarios.Doctor of Philosoph