Integrating Fault-Tolerance in Real-Time Scheduling of Mixed-Criticality Systems on Multiprocessors

Abstract

This thesis presents a novel real-time global fixed-priority scheduling algorithm that integrates mixed-criticality and fault-tolerance. An important aspect of mixedcriticality is to ensure that the temporal correctness of safety-critical tasks is not impacted by non-safety critical tasks they share a platform with. This thesis proposes that safety-critical tasks are given fault-tolerance to also ensure functional correctness. By integrating fault-tolerance the algorithm can provide guarantees for the temporal and functional correctness of safety critical tasks. Fault-tolerance is given through the execution of backup tasks where these tasks may be simple a re-execution of the primary or a diverse implementation. In addition, the backup tasks can be scheduled as either passive or active backups. The thesis includes an analysis to derive a schedulability test for the proposed algorithm and also presents policies to determine how many backups should be active for each task assuming a certain fault model. Simulated tests show that mixed-criticality and fault-tolerance can be costly in terms of schedulability, but that assigning active backups according to the policies proposed by the thesis can provide an increase in schedulability over having just passive backups.