High assurance real-time systems : scheduling, budgeting, and safety

In this dissertation we investigate resource allocation and task scheduling problems pertaining to real-time systems that mandate high levels of assurance. The required assurance guarantees are those of safety and quality of service, atop the basic guarantee required by any (classical) real-time system, namely, timely delivery of responses. We explore three major ideas within the landscape of high assurance real-time systems. First, we study the problem of scheduling Mixed-Criticality real-time tasks, with probabilistic guarantees, on a single processor. The major contribution is that we incorporate software failure rates into the scheduling problem, and we synthesize feasible scheduling policies under which the input task set will satisfy certain failure rate requirements. We model the task scheduling problem as a path-Constrained Markov Decision Process (CMDP). Second, realizing the exorbitant cost of developing safety-critical software, we develop cost-effective methods for achieving both safety integrity and timing predictability through the notion of run-time monitors, coupled with isochronous execution. This model gives rise to interesting multiversion task scheduling problems on multiple processors. We show the intractability of non-preemptive variants of the scheduling problems, and we derive optimal solutions to preemptive variants in polynomial-time. Finally, we consider a general resource budgeting problem where recurrent tasks should maintain certain quality of service levels over an indefinite operational horizon, and where both the task execution demands and the available budgets are noisy and fluctuate randomly. We derive large deviation bounds that are sufficient conditions that would allow the system designer to properly dimension system resources and allocate tasks sufficient budgets to sustain the desired quality of service levels. We then apply the bounds to a case study involving safety-critical systems that employ run-time monitors and isochronous execution, and we show how to synthesize minimum monitor worst-case execution times sufficient to achieve the desired quality of service and meet hard deadlines.Applied Science, Faculty ofElectrical and Computer Engineering, Department ofGraduat