Change search
ReferencesLink to record
Permanent link

Direct link
Timed Automata with Asynchronous Processes: Schedulability and Decidability
Division of Computer Systems, Department of Information Technology, Uppsala University.ORCID iD: 0000-0002-0182-8390
2002 (English)Conference paper (Refereed)
Abstract [en]

In this paper, we exend timed automata with asynchronous processes i.e. tasks triggered by events as a model for real-time systems. The model is expressive enough to describe concurrency and synchronization, and real time tasks which may be periodic, sporadic, preemptive or non-preemptive. We generalize the classic notion of schedulability to timed automata. An automaton is schedulable if there exists a scheduling strategy such that all possible sequences of events accepted by the automaton are schedulable in the sense that all associated tasks can be computed within their deadlines. We believe that the model may serve as a bridge between scheduling theory and automata-theoretic approaches to system modeling and analysis. Our main result is that the schedulability checking problem is decidable. To our knowledge, this is the first general decidability result on dense-time models for real time scheduling without assuming that preemptions occur only at integer time points. The proof is based on a decidable class of updatable automata: timed automata with subtraction in which clocks may be updated by subtractions within a bounded zone. The crucial observation is that the schedulability checking problem can be encoded as a reachability problem for such automata. Based on the proof, we have developed a symbolic technique and a prototype tool for schedulability analysis.

Place, publisher, year, edition, pages
Springer-Verlag , 2002. 67-82 p.
Series
, Lecture Notes in Computer Science, 1885
National Category
Mechanical Engineering Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-180647OAI: oai:DiVA.org:kth-180647DiVA: diva2:895520
Conference
8th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2002, Grenoble, France, April 8-12, 2002.
Note

NR 20160216

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

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Fersman, Elena
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

Total: 7 hits
ReferencesLink to record
Permanent link

Direct link