@TechReport{ it:2003-051,
author = {Pavel Krcal and Wang Yi},
title = {Decidable and Undecidable Problems in Schedulability
Analysis Using Timed Automata},
institution = {Department of Information Technology, Uppsala University},
department = {Division of Computer Systems},
year = {2003},
number = {2003-051},
month = nov,
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.}
}