Overhead Based Cluster Scheduling of Mixed Criticality Systems on Multicore Platform

Amjad Ali, Asad Masood Khattak, Shahid Iqbal, Omar Alfandi, Bashir Hayat, Muhammad Hameed Siddiqi, Adil KhanIEEE Access 2023 · DOI

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.

Example of a task cluster in low-criticality mode, illustrating the grouping of tasks and cores.

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

BibTeX
@article{ali2023overhead,
  author = {Amjad Ali and Asad Masood Khattak and Shahid Iqbal and Omar Alfandi and Bashir Hayat and Muhammad Hameed Siddiqi and Adil Khan},
  title = {{Overhead Based Cluster Scheduling of Mixed Criticality Systems on Multicore Platform}},
  journal = {IEEE Access},
  year = {2023},
  doi = {10.1109/access.2023.3330973},
}
Figure