Change search
ReferencesLink to record
Permanent link

Direct link
Task Automata: Schedulability, Decidability and Undecidability
Ericsson Research, Ericsson AB.ORCID iD: 0000-0002-0182-8390
2007 (English)In: Information and Computation, ISSN 0890-5401, E-ISSN 1090-2651, Vol. 205, no 8, 1149-1172 p.Article in journal (Refereed) Published
Abstract [en]

We present a model, task automata, for real time systems with non-uniformly recurring computation tasks. It is an extended version of timed automata with asynchronous processes that are computation tasks generated (or triggered) by timed events. Compared with classical task models for real time systems, task automata may be used to describe tasks (1) that are generated non-deterministically according to timing constraints in timed automata, (2) that may have interval execution times representing the best case and the worst case execution times, and (3) whose completion times may influence the releases of task instances. We generalize the classical notion of schedulability to task automata. A task automaton is schedulable if there exists a scheduling strategy such that all possible sequences of events generated by the automaton are schedulable in the sense that all associated tasks can be computed within their deadlines. Our first technical result is that the schedulability for a given scheduling strategy can be checked algorithmically for the class of task automata when the best case and the worst case execution times of tasks are equal. The proof is based on a decidable class of suspension automata: timed automata with bounded subtraction in which clocks may be updated by subtractions within a bounded zone. We shall also study the borderline between decidable and undecidable cases. Our second technical result shows that the schedulability checking problem will be undecidable if the following three conditions hold: (1) the execution times of tasks are intervals, (2) the precise finishing time of a task instance may influence new task releases, and (3) a task is allowed to preempt another running task.

Place, publisher, year, edition, pages
Elsevier, 2007. Vol. 205, no 8, 1149-1172 p.
National Category
Mechanical Engineering Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-180570DOI: 10.1016/j.ic.2007.01.009ISI: 000248671000003ScopusID: 2-s2.0-68249132870OAI: oai:DiVA.org:kth-180570DiVA: diva2:895441
Note

QC 20160218

Available from: 2016-01-19 Created: 2016-01-19 Last updated: 2016-02-18Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Fersman, Elena
In the same journal
Information and Computation
Mechanical EngineeringComputer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 11 hits
ReferencesLink to record
Permanent link

Direct link