Change search
ReferencesLink to record
Permanent link

Direct link
Schedulability Analysis of Fixed-Priority Systems using Timed Automata
Ericsson Research, Ericsson AB.ORCID iD: 0000-0002-0182-8390
2006 (English)In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 354, no 2, 301-317 p.Article in journal (Refereed) Published
Abstract [en]

In classic scheduling theory, real-time tasks are usually assumed to be periodic, i.e. tasks are released and computed 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 is in many cases huge. In this paper, we show that for fixed-priority scheduling strategy, the schedulability checking problem can be solved using standard timed automata with 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 Analysis (RMA). The result is further extended to systems with data-dependent control, in which the release time of a task may depend on the time-point at which other tasks finish their execution. For the case when the execution times of tasks are constants, we show that the schedulability problem can be solved using n+1n+1 extra clocks, where nn is the number of tasks. The presented analysis techniques have been implemented in the Times tool. For systems with only periodic tasks, the performance of the tool is comparable with tools implementing the classic RMA technique based on equation-solving, without suffering from the exponential explosion in the number of tasks.

Place, publisher, year, edition, pages
Elsevier, 2006. Vol. 354, no 2, 301-317 p.
National Category
Mechanical Engineering Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-180571DOI: 10.1016/j.tcs.2005.11.019ISI: 000236485400008ScopusID: 2-s2.0-33644699319OAI: oai:DiVA.org:kth-180571DiVA: diva2:895448
Conference
9th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2003)
Note

QC 20160218

Available from: 2016-01-19 Created: 2016-01-19 Last updated: 2016-02-18Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Fersman, Elena
In the same journal
Theoretical Computer Science
Mechanical EngineeringComputer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 19 hits
ReferencesLink to record
Permanent link

Direct link