Resource-Efficient Scheduling of Multiprocessor Mixed-Criticality Real-Time Systems

Timing guarantee is critical to ensure the correctness of embedded software systems that interact with the physical environment. As modern embedded real-time systems evolves, they face three challenges: resource constraints, mixed-criticality, and multiprocessors. This dissertation focuses on resource-efficient scheduling techniques for mixed-criticality systems on multiprocessor platforms. While Mixed-Criticality (MC) scheduling has been extensively studied on uniprocessor platforms, the problem on multiprocessor platforms has been largely open. Multiprocessor algorithms are broadly classified into two categories: global and partitioned. Global scheduling approaches use a global run-queue and migrate tasks among processors for improved schedulability. Partitioned scheduling approaches use per processor run-queues and can reduce preemption/migration overheads in real implementation. Existing global scheduling schemes for MC systems have suffered from low schedulability. Our goal in the first work is to improve the schedulability of MC scheduling algorithms. Inspired by the fluid scheduling model in a regular (non-MC) domain, we have developed the MC-Fluid scheduling algorithm that executes a task with criticality-dependent rates. We have evaluated MC-Fluid in terms of the processor speedup factor: MC-Fluid is a multiprocessor MC scheduling algorithm with a speed factor of 4/3, which is known to be optimal. In other words, MC-Fluid can schedule any feasible mixed-criticality task system if each processor is sped up by a factor of 4/3. Although MC-Fluid is speedup-optimal, it is not directly implementable on multiprocessor platforms of real processors due to the fractional processor assumption where multiple task can be executed on one processor at the same time. In the second work, we have considered the characteristic of a real processor (executing only one task at a time) and have developed the MC-Discrete scheduling algorithm for regular (non-fluid) scheduling platforms. We have shown that MC-Discrete is also speedup-optimal. While our previous two works consider global scheduling approaches, our last work considers partitioned scheduling approaches, which are widely used in practice because of low implementation overheads. In addition to partitioned scheduling, the work considers the limitation of conventional MC scheduling algorithms that drops all low-criticality tasks when violating a certain threshold of actual execution times. In practice, the system designer wants to execute the tasks as much as possible. To address the issue, we have developed the MC-ADAPT scheduling framework under uniprocessor platforms to drop as few low-criticality tasks as possible. Extending the framework with partitioned multiprocessor platforms, we further reduce the dropping of low-criticality tasks by allowing migration of low-criticality tasks at the moment of a criticality switch. We have evaluated the quality of task dropping solution in terms of speedup factor. In existing work, the speedup factor has been used to evaluate MC scheduling algorithms in terms of schedulability under the worst-case scheduling scenario. In this work, we apply the speedup factor to evaluate MC scheduling algorithms in terms of the quality of their task dropping solution under various MC scheduling scenarios. We have derived that MC-ADAPT has a speedup factor of 1.618 for task dropping solution