Introduction
In modern real-time systems, such as automotive or aerospace applications, "Mixed-Criticality" (MC) scheduling is essential. These systems must simultaneously manage high-criticality tasks (e.g., braking control) and low-criticality tasks (e.g., infotainment) on a shared multicore platform. While global scheduling offers efficiency and partitioned scheduling offers predictability, both face significant challenges regarding execution overhead—specifically context switches and task migrations. This paper introduces MC-Bfair, a cluster-based scheduling algorithm designed to minimize these "hidden" costs while maintaining high schedulability.
The Challenge: Balancing Efficiency and Overhead
Traditional scheduling models often ignore the time lost during context switches (stopping one task to start another) and migrations (moving a task between cores). In safety-critical environments, these overheads can lead to missed deadlines.
- Partitioned Scheduling avoids migration overhead by locking tasks to specific cores, but it often leaves processing power underutilized.
- Global Scheduling maximizes utilization by allowing tasks to roam across all cores, but it incurs massive overhead that can compromise system safety.
Proposed Methodology: MC-Bfair and Clustering
The authors propose a "middle ground" through a two-stage strategy that combines intelligent task partitioning with a novel scheduling algorithm.
1. Task Partitioning (DCDU-WF)
Tasks are assigned to clusters using the "Decreasing Criticality Decreasing Utilization with Worst-Fit" (DCDU-WF) approach. Tasks are sorted by importance and processing requirements, then distributed among clusters—groups of cores—to balance the load across the chip.
2. The MC-Bfair Algorithm
Within each cluster, tasks are scheduled using a "Boundary Fair" (Bfair) approach. Unlike standard algorithms that might trigger preemptions at any time, MC-Bfair primarily makes scheduling decisions at task period boundaries. This alignment naturally reduces the frequency of context switches.
3. Mode-Aware Overhead Accounting
The model explicitly incorporates time penalties for every context switch and migration. These penalties are mode-aware, meaning they are calculated differently depending on whether the system is in "Low-Criticality" mode (all tasks active) or "High-Criticality" mode (only safety-critical tasks active).
Key Results and Performance
The researchers evaluated MC-Bfair using over 300 synthetic task sets per data point, comparing it against existing methods like CB-FP and MC-EKG-VD-1.
- Superior Schedulability at High Utilization: At a target utilization ($U$) of 0.6, the proposed technique successfully scheduled 66.7% of task sets. In contrast, traditional global scheduling failed completely (0%) when overhead was accounted for, and the MC-EKG-VD-1 method managed only 50%.
- Extended Efficiency Range: The system maintained 100% schedulability up to $U=0.55$, outperforming partitioned and fixed-priority methods which began failing around $U=0.45$.
- Overhead Minimization: By reducing context switches and limiting migrations to within clusters, the algorithm reclaimed significant execution time for actual task processing.
Conclusion and Future Directions
The cluster-based approach provides a robust solution for mixed-criticality systems on multicore platforms by effectively managing the trade-off between utilization and overhead. While currently limited to binary criticality levels and homogeneous cores, future work aims to extend this model to multi-level criticality systems (like ISO 26262's ASIL A-D) and heterogeneous architectures like ARM's big.LITTLE. Additionally, incorporating fault tolerance remains a key area for future research to ensure reliability in the face of hardware failures.
Summary updated