Feasibility Tests for Recurrent Real-Time Tasks in the Sporadic DAG Model

Abstract

A model has been proposed in [Baruah et al., in Proceedings of the IEEE Real-Time Systems Symposium 2012] for representing recurrent precedence-constrained tasks to be executed on multiprocessor platforms, where each recurrent task is modeled by a directed acyclic graph (DAG), a period, and a relative deadline. Each vertex of the DAG represents a sequential job, while the edges of the DAG represent precedence constraints between these jobs. All the jobs of the DAG are released simultaneously and have to be completed within some specified relative deadline. The task may release jobs in this manner an unbounded number of times, with successive releases occurring at least the specified period apart. The feasibility problem is to determine whether such a recurrent task can be scheduled to always meet all deadlines on a specified number of dedicated processors. The case of a single task has been considered in [Baruah et al., 2012]. The main contribution of this paper is to consider the case of multiple tasks. We show that EDF has a speedup bound of 2-1/m, where m is the number of processors. Moreover, we present polynomial and pseudopolynomial schedulability tests, of differing effectiveness, for determining whether a set of sporadic DAG tasks can be scheduled by EDF to meet all deadlines on a specified number of processors.

Cited by in corpus (8)

• Edge Generation Scheduling for DAG Tasks Using Deep Reinforcement Learning
• Semi-Federated Scheduling of Parallel Real-Time Tasks on Multiprocessors
• New Analysis Techniques for Supporting Hard Real-Time Sporadic DAG Task Systems on Multiprocessors
• k2U: A General Framework from k-Point Effective Schedulability Analysis to Utilization-Based Tests
• Schedulability Bounds for Parallel Real-Time Tasks under Global Rate-Monotonic Scheduling
• Response Time Bounds for Typed DAG Parallel Tasks on Heterogeneous Multi-cores
• Analysis of Global Fixed-Priority Scheduling for Generalized Sporadic DAG Tasks
• Timing Analysis for DAG-based and GFP Scheduled Tasks