Real-time systems increasingly contain processing units with multiple cores. To use this additional computational power in hard deadline environments, one needs schedulability tests for task models that represent the possibilities of parallel execution of jobs of a task. A standard model is to represent a (sporadically) recurrent task by a directed a cyclic graph (DAG). The nodes of the DAG correspond to the jobs of the task. All such jobs are released simultaneously, have to be completed within some common relative deadline, and some pairs of jobs are linked by a precedence constraint, i.e., an arc of the DAG. This poses new challenges for analyzing whether a task system is feasible, in particular for the commonly used online algorithms Earliest Deadline First (EDF) and Deadline Monotonic (DM). While for ordinary sporadic tasks the required algorithmic techniques are well-understood, despite recent research much remains open in this model. In this work, we completely close the gap between the algorithmic understanding of feasibility analysis for the usual sporadic task model and the case where each sporadic task is a DAG. We show for DAG tasks that EDF has a tight speedup bound of 2 - 1/m, where m is the number of processors, while DM has a speedup bound of at most 3 - 1/m. Moreover, we present polynomial and pseudopolynomial time tests, of differing effectiveness, for determining whether a set of sporadic DAG tasks can be scheduled by EDF or DM to meet all deadlines on a specified number of processors. We remark that the effectiveness of some of our tests matches the best known algorithms for ordinary sporadic task sets, thus closing the gap. © 2013 IEEE.

Feasibility analysis in the sporadic DAG task model / Bonifaci, Vincenzo; MARCHETTI SPACCAMELA, Alberto; Sebastian, Stiller; Andreas, Wiese. - STAMPA. - (2013), pp. 225-233. (Intervento presentato al convegno 25th Euromicro Conference on Real-Time Systems, ECRTS 2013 tenutosi a Paris nel 9 July 2013 through 12 July 2013) [10.1109/ecrts.2013.32].

Feasibility analysis in the sporadic DAG task model

BONIFACI, VINCENZO;MARCHETTI SPACCAMELA, Alberto;
2013

Abstract

Real-time systems increasingly contain processing units with multiple cores. To use this additional computational power in hard deadline environments, one needs schedulability tests for task models that represent the possibilities of parallel execution of jobs of a task. A standard model is to represent a (sporadically) recurrent task by a directed a cyclic graph (DAG). The nodes of the DAG correspond to the jobs of the task. All such jobs are released simultaneously, have to be completed within some common relative deadline, and some pairs of jobs are linked by a precedence constraint, i.e., an arc of the DAG. This poses new challenges for analyzing whether a task system is feasible, in particular for the commonly used online algorithms Earliest Deadline First (EDF) and Deadline Monotonic (DM). While for ordinary sporadic tasks the required algorithmic techniques are well-understood, despite recent research much remains open in this model. In this work, we completely close the gap between the algorithmic understanding of feasibility analysis for the usual sporadic task model and the case where each sporadic task is a DAG. We show for DAG tasks that EDF has a tight speedup bound of 2 - 1/m, where m is the number of processors, while DM has a speedup bound of at most 3 - 1/m. Moreover, we present polynomial and pseudopolynomial time tests, of differing effectiveness, for determining whether a set of sporadic DAG tasks can be scheduled by EDF or DM to meet all deadlines on a specified number of processors. We remark that the effectiveness of some of our tests matches the best known algorithms for ordinary sporadic task sets, thus closing the gap. © 2013 IEEE.
2013
25th Euromicro Conference on Real-Time Systems, ECRTS 2013
earliest deadline first; dag model; schedulability; speedup bound; deadline monotonic
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Feasibility analysis in the sporadic DAG task model / Bonifaci, Vincenzo; MARCHETTI SPACCAMELA, Alberto; Sebastian, Stiller; Andreas, Wiese. - STAMPA. - (2013), pp. 225-233. (Intervento presentato al convegno 25th Euromicro Conference on Real-Time Systems, ECRTS 2013 tenutosi a Paris nel 9 July 2013 through 12 July 2013) [10.1109/ecrts.2013.32].
File allegati a questo prodotto
File Dimensione Formato  
VE_2013_11573-559725.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 286.06 kB
Formato Adobe PDF
286.06 kB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/559725
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 133
  • ???jsp.display-item.citation.isi??? 79
social impact