A Soft-Real-Time Optimal Scheduler for DAG Tasks with Node-Level Self Dependencies

Modern real-time workloads are often expressed as processing graphs that have complex dataflow dependencies. No scheduling algorithm with a holistic analysis of graph-based tasks is known that can provide bounded response times without utilization loss, thus ensuring soft-real-time optimality, when a node instance depends on some of its prior instances and multiple invocations of the same graph can be active simultaneously. This paper presents a scheduling policy for such a graph-based task and provides a response-time analysis that guarantees bounded response times without utilization loss. Experimental evaluations show that our scheduler yields significantly tighter response-time bounds than existing soft-real-time optimal schedulers.