×

Decidable and undecidable problems in schedulability analysis using timed automata. (English) Zbl 1126.68456

Jensen, Kurt (ed.) et al., Tools and algorithms for the construction and analysis of systems. 10th international conference, TACAS 2004, held as part of the joint conferences on theory and practice of software, ETAPS 2004, Barcelona, Spain, March 29 – April 2, 2004. Proceedings. Berlin: Springer (ISBN 3-540-21299-X/pbk). Lecture Notes in Computer Science 2988, 236-250 (2004).
Summary: We study schedulability problems of timed systems with non-uniformly recurring computation tasks. Assume a set of real time tasks whose best and worst execution times, and deadlines are known. We use timed automata to describe the arrival patterns (and release times) of tasks. From the literature, it is known that the schedulability problem for a large class of such systems is decidable and can be checked efficiently. In this paper, we provide a summary on what is decidable and what is undecidable in schedulability analysis using timed automata. Our main technical contribution is that the schedulability problem will be undecidable if these three conditions hold: (1) the execution times of tasks are intervals, (2) a task can announce its completion time, and (3) a task can preempt another task. We show that if one of the above three conditions is dropped, the problem will be decidable. Thus our result can be used as an indication in identifying classes of timed systems that can be analysed efficiently.
For the entire collection see [Zbl 1046.68008].

MSC:

68Q45 Formal languages and automata
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems

Software:

Kronos; TIMES; Uppaal; HyTech
PDFBibTeX XMLCite
Full Text: DOI