An Efficient Utilization-Based Test for Scheduling Hard Real-Time Sporadic DAG Task Systems on Multiprocessors

The scheduling and schedulability analysis of real-time directed acyclic graph (DAG) task systems have received much recent attention. The DAG model can accurately represent intra-task parallelism and precedence constraints existing in many application domains. Existing techniques show that analyzing the DAG model is fundamentally more challenging compared to the ordinary sporadic task model, due to the complex intra-DAG precedence constraints which may cause rather pessimistic schedulability loss. However, such increased loss is counter-intuitive because the DAG structure shall better exploit the hardware parallelism provided by the multiprocessor platform. Our key observation is that the intra-DAG precedence constraints, if not carefully considered by the scheduling algorithm, may cause unpredictable execution behaviors of sub-tasks in a DAG and thus pessimistic analysis. In this paper, we present a set of novel scheduling and analysis techniques for better supporting hard real-time sporadic DAG tasks on multiprocessors, through smartly defining and analyzing the execution order of subtasks in each DAG. Combined with a new DAG-specific interval analysis framework, the proposed subtask ordering technique leads to a highly efficient utilization-based schedulability test. Importantly, the developed test becomes identical to the classical density test designed for the sporadic task model, if each DAG in the system has an out-degree of one (i.e., only containing a chain of subtasks). Experiments show the efficiency of the developed test, which improves schedulability upon existing utilization-based tests by over 60% on average and is often able to guarantee schedulability with little utilization loss.