Work-in-Progress: New Analysis Techniques for Supporting Hard Real-Time Sporadic DAG Task Systems on Multiprocessors

We consider the problem of globally scheduling hard real-time sporadic DAG task systems on multiprocessors. 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 counterintuitive because the DAG structure shall better exploit the parallelism provided by the multiprocessor platform. In this work, 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. Interestingly, when each DAG task only contains a single subtask, the proposed utilization-based schedulability test becomes identical to the density test.