Semi-federated scheduling of mixed-criticality system for sporadic DAG tasks

DAG task model is a general parallel task model that has been widely concerned and studied by researchers. The combination of mixed-criticality and DAG task model makes it difficult to analyze system behaviors. Under federated mixed-criticality scheduling algorithm, tasks are physically isolated with regard to computation resources, which leads to lower analysis complexity and better performance. However, federated mixed-criticality scheduling algorithm suffers resource waste as in federated scheduling, and almost half of processor resources can be wasted in extreme cases. In this paper, we address the problem and propose a novel semi-federated mixed-criticality algorithm (SFMC). SFMC combines semi-federated scheduling with mixed-criticality systems, whose original architecture is changed to a dual-hierarchical one. When analyzing the combined system, we first allocate finer-grained processor resources to each MC DAG task, then we prove the correctness of the SFMC algorithm in both normal and critical states. The proposed algorithm is evaluated on randomly generated independent DAG task sets based on OpenMP benchmarks. Experiment results present that our algorithm has better performance on schedulability than the federated mixed-criticality scheduling algorithm.