Treffer: Quasi-Static Scheduling of Communicating Tasks

Title:
Quasi-Static Scheduling of Communicating Tasks
Authors:
Darondeau, Philippe, Genest, Blaise, Thiagarajan, P.S., Yang, Shaofa
Contributors:
System synthesis and supervision, scenarios (S4), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre Inria de l'Université de Rennes, Institut National de Recherche en Informatique et en Automatique (Inria), Image & Pervasive Access Lab (IPAL), National University of Singapore (NUS)-Agency for science, technology and research [Singapore] (A*STAR)-Centre National de la Recherche Scientifique (CNRS)-Institute for Infocomm Research - I²R [Singapore], School of computing [Singapore] (NUS), National University of Singapore (NUS), International Institute for Software Technology [Macao] (UNU-IIST), United Nations University (UNU)
Source:
Information and Computation. 208(10):1154-1168
Publisher Information:
CCSD; Elsevier, 2010.
Publication Year:
2010
Collection:
collection:EC-PARIS
collection:UNIV-RENNES1
collection:CNRS
collection:INRIA
collection:INSA-RENNES
collection:INRIA-RENNES
collection:IRISA
collection:IRISA_SET
collection:INRIA_TEST
collection:TESTALAIN1
collection:IPAL
collection:IRISA-D4
collection:INRIA2
collection:UR1-HAL
collection:UR1-MATH-STIC
collection:UR1-UFR-ISTIC
collection:TEST-UNIV-RENNES
collection:TEST-UR-CSS
collection:UNIV-RENNES
collection:INRIA-RENGRE
collection:INSA-GROUPE
collection:SORBONNE-UNIVERSITE
collection:SU-SCIENCES
collection:SU-TI
collection:UR1-MATH-NUM
collection:ALLIANCE-SU
collection:INRIA-JAPON
collection:INRIA-SINGAPOUR
Subject Terms:
C.: Computer Systems Organization, C.2: COMPUTER-COMMUNICATION NETWORKS, [INFO.INFO-OH]Computer Science [cs], Other [cs.OH], [INFO.INFO-ES]Computer Science [cs], Embedded Systems, [INFO.INFO-NI]Computer Science [cs], Networking and Internet Architecture [cs.NI], [INFO.INFO-FL]Computer Science [cs], Formal Languages and Automata Theory [cs.FL]
Original Identifier:
HAL: hal-00591759
Document Type:
Zeitschrift article<br />Journal articles
Language:
English
ISSN:
0890-5401
1090-2651
Access URL:
https://hal.science/hal-00591759
https://hal.science/hal-00591759v1/document
https://hal.science/hal-00591759v1/file/DGTY10.pdf
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.hal.00591759v1
Database:
HAL

Weitere Informationen

Good scheduling policies for distributed embedded applications are required for meeting hard real time constraints and for optimizing the use of computational resources. We study the quasi-static scheduling problem in which (uncontrollable) control flow branchings can influence scheduling decisions at run time. Our abstracted distributed task model consists of a network of sequential processes that communicate via point-to-point buffers. In each round, the task gets activated by a request from the environment. When the task has finished computing the required responses, it reaches a pre-determined configuration and is ready to receive a new request from the environment. For such systems, we prove that determining the existence of a scheduling policy that guarantees upper bounds on buffer capacities is undecidable. However, we show that the problem is decidable for the important subclass of "data-branching" systems in which control flow branchings are exclusively due to data-dependent internal choices made by the sequential components. This decidability result exploits ideas derived from the Karp and Miller coverability tree for Petri nets as well as the existential boundedness notion of languages of message sequence charts.