Feasibility Analysis in the Sporadic DAG Task Model (Articolo in rivista)

Type
Label
  • Feasibility Analysis in the Sporadic DAG Task Model (Articolo in rivista) (literal)
Anno
  • 2013-01-01T00:00:00+01:00 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#doi
  • 10.1109/ECRTS.2013.32 (literal)
Alternative label
  • Bonifaci V; Marchetti-Spaccamela A; Stiller S; Wiese A (2013)
    Feasibility Analysis in the Sporadic DAG Task Model
    in Proceedings (Euromicro Conf. Real-Time Syst., Print); IEEE Computer Society, Los Alamitos, CA (Stati Uniti d'America)
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • Bonifaci V; Marchetti-Spaccamela A; Stiller S; Wiese A (literal)
Pagina inizio
  • 225 (literal)
Pagina fine
  • 233 (literal)
Rivista
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#pagineTotali
  • 9 (literal)
Note
  • ISI Web of Science (WOS) (literal)
  • Scopu (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
  • Istituto di Analisi dei Sistemi ed Informatica, CNR, Rome, Italy Sapienza University of Rome, Rome, Italy Technische Universitaet Berlin, Berlin, Germany Max Planck Institute for Computer Science, Saarbruecken, Germany (literal)
Titolo
  • Feasibility Analysis in the Sporadic DAG Task Model (literal)
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 acyclic 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. (literal)
Editore
Prodotto di
Autore CNR

Incoming links:


Prodotto
Autore CNR di
Editore di
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi
data.CNR.it