Schedulability analysis and low-criticality execution support for mixed-criticality real-time systems on uniprocessors

An increasing trend in safety-critical real-time systems is towards open computing environments, where applications with different degrees of importance are developed independently and integrated together on a single computing platform. In these systems, the correct behavior of some application (e.g., flight control) is more important (“critical”) to the overall safety of the system than that of another (e.g., in-flight cooling). Such a system that consolidates multiple functionalities of different importance or criticality is called a mixed-criticality system. Classical real-time scheduling theory can be used to guarantee the correctness of mixed-criticality systems, such that applications at different levels of criticality are verified with the corresponding degree of assurance. However, conservative resource reservations are often used to achieve this correctness at high assurance levels, and this results in severe under-utilization of system resources. To address this problem, real-time scheduling theory for mixed-criticality systems has been developed. The primary objective of this theory is to improve resource utilization, while still guaranteeing the safe execution of critical applications. Focusing on mixed-criticality scheduling theory, this dissertation addresses two important problems in the design of scheduling algorithms for mixed-criticality systems on uniprocessor platforms. First, we focus on the design of scheduling algorithms and analysis techniques for mixed-criticality systems that can successfully schedule a large proportion of such systems. Since mixed-criticality scheduling has been shown to be a NP-Hard problem, it is important to develop techniques that improve schedulability while still having efficient runtimes. To address this problem, we propose a demand bound function (DBF) based schedulability analysis technique for earliest deadline first (EDF) schedul- ing of mixed-criticality systems, and also develop a corresponding scheduling strategy. This analysis considers the different execution modes in a mixed-criticality system collectively, and is thus able to overcome some of the pessimistic assumptions in existing analysis. The proposed scheduling strategy is thus able to achieve much better schedulability, particularly for systems with more than two criticality levels, without any increase in the runtimes. Second, we also propose novel scheduling models and strategies to support the execution of less critical applications in mixed-criticality systems. Several of the studies in mixed-criticality make simplifying, but unrealistic, assumptions about the need to execute less critical applications. They assume that when critical applications demand additional system resources, it is safe to completely suspend the less critical applications in order to ensure a safe execution of the critical ones. Furthermore, many of these studies also assume that the critical applications are likely to demand these additional resources at the same time, and hence consider it reasonable to reduce support to all the less critical applications. These assumptions are not only impractical, but also lead to under-utilization of system resources. To contain the impact on less critical applications, we first propose a component-based scheduling model and extend the above DBF-based schedulability analysis technique for the same. In this model, a component boundary isolates the critical applications within the component from the less critical ones in other components, as long as the demand for additional resources is within defined limits. Thus, the model provides service differentiation among the less critical applications depending on the demand of individual critical applications at any point in time. To further support the execution of less critical applications, we also propose a dynamic task and EDF based scheduling model under which the budgets for individual critical applications are determined at runtime. Thus, by dynamically distributing the total available budget among critical applications, we are able to significantly postpone the time instant when the demand from critical applications exceeds defined limits. As a consequence, the less critical applications in the system are able to get full service for a prolonged duration.Doctor of Philosophy (SCE