TY - GEN
T1 - A generalized parallel task model for recurrent real-time processes
AU - Baruah, Sanjoy
AU - Bonifaci, Vincenzo
AU - Marchetti-Spaccamela, Alberto
AU - Stougie, Leen
AU - Wiese, Andreas
PY - 2012
Y1 - 2012
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84874295466&partnerID=8YFLogxK
U2 - 10.1109/RTSS.2012.59
DO - 10.1109/RTSS.2012.59
M3 - Conference contribution
AN - SCOPUS:84874295466
SN - 9780769548692
T3 - Proceedings - Real-Time Systems Symposium
SP - 63
EP - 72
BT - Proceedings of the 2012 IEEE 33rd Real-Time Systems Symposium, RTSS 2012
T2 - 2012 IEEE 33rd Real-Time Systems Symposium, RTSS 2012
Y2 - 5 December 2012 through 7 December 2012
ER -