Schedulability Analysis using Two Clocks

• In classic scheduling theory, real-time tasks are usually assumed tobe periodic, i.e. tasks arrive and compute with fixed ratesperiodically. To relax the stringent constraints on task arrivaltimes, we propose to use timed automata to describe task arrivalpatterns. In a previous work, it is shown that the generalschedulability checking problem for such models is a reachabilityproblem for a decidable class of timed automata extended withsubtraction. Unfortunately, the number of clocks needed in theanalysis is proportional to the maximal number of schedulable taskinstances 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 reachabilityanalysis on standard timed automata using only two extra clocksin addition to the clocks used in the original model to describe taskarrival times. The analysis can be done in a similar manner toresponse 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.

Subject headings

NATURVETENSKAP  -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences -- Computer Sciences (hsv//eng)

Keyword

Computer science

Datalogi

Publication and Content Type

ref (subject category)

kon (subject category)