A survey on real-time DAG scheduling, revisiting the Global-Partitioned Infinity War

Modern cyber-physical embedded systems are characterized by a range of intricate functionalities that are subject to tight timing constraints. Unfortunately, traditional sequential task models and uniprocessors solutions are not suitable for this context: a more expressive model becomes necessary. In such cases, the Directed Acyclic Graph (DAG) is a proper model to express the complexity and the parallelism of the tasks of these kinds of systems. In recent years, several methods with different settings have been proposed to solve the schedulability problem for applications featuring DAG tasks. This paper presents a survey of the state-of-the-art of the DAG task model, focusing on scheduling tests that are more effective, easy to implement, and adopt, while providing a detailed comparison of global and partitioned scheduling solutions. Besides discussing the approaches and presenting them under a common convention, this work is the first to present a comprehensive experimental analysis of several state-of-the-art tests, thanks to the development of a C++ library that implements all the methods, which is made available at url will be inserted for camera-ready.

Automated summary

Modern cyber-physical embedded systems require a more expressive model to handle intricate functionalities and tight timing constraints. Directed Acyclic Graph (DAG) is a suitable model for expressing the complexity and parallelism of tasks in these systems. This paper presents a survey of state-of-the-art DAG task models and scheduling solutions, including a comprehensive experimental analysis of various tests using a C++ library.