Typically, a real-time system consists of a controlling system (i.e., a computer) and a controlled system (i.e., the environment). Real-time systems are those systems where correctness depends on two aspects: i) the logical result of computation and, ii) the time in which results are produced. It is essential to guarantee meeting timing constraints for this kind of systems to operate correctly. Missing deadlines in many cases -- in so-called hard real-time systems -- is associated with economic loss or loss of human lives and must be avoided under all circumstances. On the other hand, there is a trend towards consolidating software functions onto fewer processors in different domains such as automotive systems and avionics with the aim of reducing costs and complexity. Hence, applications with different levels of criticality that used to run in isolation now start sharing processors. As a result, there is a need for techniques that allow designing such mixed-criticality (MC) systems -- i.e., real-time systems combining different levels of criticality -- and, at the same time, complying with certification requirements in the different domains. In this research, we study the problem of scheduling MC tasks under EDF (Earliest Deadline First) and propose new approaches to improve scheduling techniques. In particular, we consider that a mix of low-criticality (LO) and high-criticality (HI) tasks are scheduled on one processor. While LO tasks can be modeled by minimum inter-arrival time, deadline, and worst-case execution time (WCET), HI tasks are characterized by two WCET parameters: an optimistic and a conservative one. Basically, the system operates in two modes: LO and HI mode. In LO mode, HI tasks run for no longer than their optimistic execution budgets and are scheduled together with the LO tasks. The system switches to HI mode when one or more HI tasks run for more than their conservative execution budgets. In this case, LO tasks are immediately discarded so as to be able of accommodating the increase in HI execution demand. We propose an exact test for mixed-criticality EDF, which increases efficiency and reliability when compared with the existing approaches from the literature. On this basis, we further derive approximated tests with less complexity and, hence, a reduced running time that makes them more suitable for online checks.:Contents 1. Introduction 1 1.1. Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2. Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3. Structure of this Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Concepts, Models and Assumptions 7 2.1. Real-Time Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1.1. Tasks Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2. Scheduling Policies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.1. Feasibility versus Schedulability . . . . . . . . . . . . . . . . . . . . . . 9 2.2.2. Schedulability Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3. Mixed-Criticality Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.4. Basic Nomenclature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.5. The Earliest Deadline First Algorithm . . . . . . . . . . . . . . . . . . . . . . 13 2.5.1. EDF-VD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.5.2. Mixed-Criticality EDF . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.5.3. Demand Bound Function . . . . . . . . . . . . . . . . . . . . . . . . . 16 3. Related Work 17 3.1. Uniprocessor Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.1.1. Uniprocessor Scheduling Based on EDF . . . . . . . . . . . . . . . . . 18 3.2. Multiprocessor Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.2.1. Multiprocessor Scheduling Based on EDF . . . . . . . . . . . . . . . . 20 4. Introducing Utilization Caps 23 4.1. Introducing Utilization Caps . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.1.1. Fixed utilization caps . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.1.2. Optimized utilization caps . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.2. Findings of this Chapter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5. Bounding Execution Demand under Mixed-Criticality EDF 29 5.1. Bounding Execution Demand . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.2. Analytical Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 5.2.1. The GREEDY Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 35 5.2.2. The ECDF Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.3. Finding Valid xi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 5.4. Findings of this Chapter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 6. Approximating Execution Demand Bounds 41 6.1. Applying Approximation Techniques . . . . . . . . . . . . . . . . . . . . . . . 41 6.2. Devi’s Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 6.2.1. Per-task deadline scaling . . . . . . . . . . . . . . . . . . . . . . . . . . 42 6.2.2. Uniform deadline scaling . . . . . . . . . . . . . . . . . . . . . . . . . . 44 6.2.3. Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 6.3. Findings of this Chapter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 7. Evaluation and Results 49 7.1. Mixed-Criticality EDF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 7.2. Obtaining Test Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 7.2.1. The Case Di = Ti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 7.2.2. The Case Di ≤ Ti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 7.3. Weighted schedulability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 7.4. Algorithms in this Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . 51 7.4.1. The EDF-VD and DEDF-VD Algorithms . . . . . . . . . . . . . . . . 51 7.4.2. The GREEDY algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 52 7.4.3. The ECDF algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 7.5. Evaluation of Utilization Caps . . . . . . . . . . . . . . . . . . . . . . . . . . 53 7.5.1. 10 tasks per task set . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 7.5.2. 20 tasks per task set . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 7.5.3. 50 tasks per task set . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 7.5.4. Comparison of runtime . . . . . . . . . . . . . . . . . . . . . . . . . . 59 7.6. Evaluation of Execution Demand Bounds . . . . . . . . . . . . . . . . . . . . 61 7.6.1. Comparison for sets of 10 tasks . . . . . . . . . . . . . . . . . . . . . . 61 7.6.2. Comparison for sets of 20 tasks . . . . . . . . . . . . . . . . . . . . . . 64 7.7. Evaluation of Approximation Techniques . . . . . . . . . . . . . . . . . . . . . 67 7.7.1. Schedulability curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 7.7.2. Weighted schedulability . . . . . . . . . . . . . . . . . . . . . . . . . . 69 7.7.3. Comparison of runtime . . . . . . . . . . . . . . . . . . . . . . . . . . 72 7.8. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 8. Conclusion and Future Work 77 8.1. Outlook/Future Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 Bibliography 83 A. Introduction 91 A.1. Multiple Levels of Criticality . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 A.1.1. Ordered mode switches . . . . . . . . . . . . . . . . . . . . . . . . . . 91 A.1.2. Unordered mode switches . . . . . . . . . . . . . . . . . . . . . . . . . 93 B. Evaluation and Results 95 B.1. Uniform Distribution for Task Periods . . . . . . . . . . . . . . . . . . . . . . 95