Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-540-85361-9_26
Title: Quasi-static scheduling of communicating tasks
Authors: Darondeau, P.
Genest, B.
Thiagarajan, P.S. 
Yang, S.
Issue Date: 2008
Source: Darondeau, P.,Genest, B.,Thiagarajan, P.S.,Yang, S. (2008). Quasi-static scheduling of communicating tasks. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 5201 LNCS : 310-324. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-540-85361-9_26
Abstract: 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 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 existence of quasi-static scheduling policies is undecidable. However, we show that the problem is decidable for the important sub-class of "data branching" systems in which control flow branchings are due exclusively to data-dependent internal choices made by the sequential components. This decidability result-which is non-trivial to establish-exploits ideas derived from the Karp and Miller coverability tree [8] as well as the existential boundedness notion of languages of message sequence charts [6]. © Springer-Verlag Berlin Heidelberg 2008.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/42163
ISBN: 354085360X
ISSN: 03029743
DOI: 10.1007/978-3-540-85361-9_26
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

5
checked on Dec 13, 2017

Page view(s)

47
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.