Mixed-Criticality Federated Scheduling for Relaxed-Deadline DAG Tasks

A mixed-criticality (MC) system is a computational platform shared by tasks with two or more safety-critical levels. An important research topic related to MC systems is designing scheduling algorithms that can satisfy the computation requirements of tasks with different criticality levels. Numerous studies have focused on this topic, but only a few have considered parallel tasks. To address the research gap, we propose a dual-criticality scheduling algorithm based on federated scheduling for parallel tasks with Directed Acyclic Graph (DAG) structures. We particularly focus on the task set in which each task has a deadline longer than its release period. To the best of our knowledge, our work is the first that does not assume the constrained-or implicit-deadline in the MC DAG task model. In addition to simulation experiments, we demonstrate that our algorithm has a capacity augmentation bound of 4, providing a quantitative worst-case performance guarantee for our algorithm.