Name
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 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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.ic.2009.09.005 | Information & Computation |
Keywords | Field | DocType |
communicating machines,channel bound,control flow branching,good scheduling policy,task model,hard real time constraint,new request,required response,quasi-static scheduling problem,flow branching,scheduling policy,run time,quasi-static scheduling,message sequence chart,scheduling problem,control flow,point to point | Fixed-priority pre-emptive scheduling,Fair-share scheduling,Computer science,Scheduling (computing),Two-level scheduling,Theoretical computer science,Decidability,Rate-monotonic scheduling,Dynamic priority scheduling,Round-robin scheduling,Distributed computing | Journal |
Volume | Issue | ISSN |
208 | 10 | Information and Computation |
Citations | PageRank | References |
7 | 0.49 | 14 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Philippe Darondeau | 1 | 715 | 77.04 |
| Blaise Genest | 2 | 304 | 25.09 |
| P. S. Thiagarajan | 3 | 1497 | 193.71 |
| Shaofa Yang | 4 | 46 | 4.76 |