In classic scheduling theory, real-time tasks are usually assumed to
be periodic, i.e. tasks arrive and compute with fixed rates
periodically. To relax the stringent constraints on task arrival
times, we propose to use timed automata to describe task arrival
patterns. In a previous work, it is shown that the general
schedulability checking problem for such models is a reachability
problem for a decidable class of timed automata extended with
subtraction. Unfortunately, the number of clocks needed in the
analysis is proportional to the maximal number of schedulable task
instances associated with a model, which in many cases is huge.
In this paper, we show that for fixed priority scheduling strategy,
the schedulability checking problem can be solved by reachability
analysis on standard timed automata using only two extra clocks
in addition to the clocks used in the original model to describe task
arrival times. The analysis can be done in a similar manner to
response time analysis in classic Rate-Monotonic Scheduling.
We believe that this is the optimal solution to the problem,
a problem that was suspected undecidable previously.
We also extend the result to systems in which the timed automata and the tasks may read and update shared data variables. Then the release time-point of a task may depend on the values of the shared variables, and hence on the time-point at which other tasks finish their exection. We show that this schedulability problem can be encoded as timed automata using n+1 extra clocks, where n is the number of tasks.
2003.