New Analysis Techniques for Supporting 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 parallelim 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 parallelism provided by the multiprocessor platform. Our observation is that the intra-DAG precedence constraints, if not carefully considered by the scheduling algorithm, may cause very unpredictable execution behaviors of subtasks in a DAG and further cause 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. Evaluation demonstrates that our developed utilization-based schedulability test is highly efficient, which dramatically improves schedulability of existing utilization-based tests by over 60% on average. Interestingly, when each DAG in the system is an ordinary sporadic task, our test becomes identical to the classical density test designed for the sporadic task model.