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.