Technical Report 2003-051

Decidable and Undecidable Problems in Schedulability Analysis Using Timed Automata

Pavel Krcal and Wang Yi

November 2003

Abstract:

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 two conditions hold: (1) the execution times of tasks are intervals and (2) a task is allowed to reset clocks. We show that if one of the above two conditions is dropped, the problem will be decidable again. Thus our result can be used as an indication in identifying classes of timed systems that can be analysed efficiently.

Available as Postscript (425 kB, no cover), PDF (223 kB, no cover), and compressed Postscript (182 kB, no cover)

Download BibTeX entry.