A generalized parallel task model for recurrent real-time processes

Sanjoy Baruah, Vincenzo Bonifaci, Alberto Marchetti-Spaccamela, Leen Stougie, Andreas Wiese

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

144 Scopus citations


A model is considered for representing recurrent precedence-constrained tasks that are to execute on multiprocessor platforms. A recurrent task is specified as a directed a cyclic 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 need to complete execution within the specified relative deadline of their release. The task may release jobs in this manner an unbounded number of times, with successive releases occurring at least the specified period apart. The scheduling problem is to determine whether such a recurrent task can be scheduled to always meet all deadlines upon a specified number of processors that are dedicated for the use of this task. This problem is shown to be computationally intractable, but amenable to efficient approximate solutions. EDF is shown to be a good approximate scheduling algorithm. Polynomial and pseudo-polynomial schedulability tests, of differing effectiveness, are presented for determining whether a given task can be scheduled by EDF to always meet all deadlines on a specified number of processors.

Original languageEnglish
Title of host publicationProceedings of the 2012 IEEE 33rd Real-Time Systems Symposium, RTSS 2012
Number of pages10
StatePublished - 2012
Externally publishedYes
Event2012 IEEE 33rd Real-Time Systems Symposium, RTSS 2012 - San Juan, Puerto Rico
Duration: 5 Dec 20127 Dec 2012

Publication series

NameProceedings - Real-Time Systems Symposium
ISSN (Print)1052-8725


Conference2012 IEEE 33rd Real-Time Systems Symposium, RTSS 2012
Country/TerritoryPuerto Rico
CitySan Juan


Dive into the research topics of 'A generalized parallel task model for recurrent real-time processes'. Together they form a unique fingerprint.

Cite this