mdh.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Schedulability Analysis of Fixed Priority Systems using Timed Automata
Uppsala University, Sweden.
Uppsala University, Sweden.
Uppsala University, Sweden.ORCID iD: 0000-0003-4040-3480
Uppsala University, Sweden.
2006 (English)In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 354, no 2, p. 301-317Article 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+1 extra clocks, where n 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
2006. Vol. 354, no 2, p. 301-317
National Category
Computer Engineering Embedded Systems
Identifiers
URN: urn:nbn:se:mdh:diva-6990DOI: 10.1016/j.tcs.2005.11.019ISI: 000236485400008Scopus ID: 2-s2.0-33644699319OAI: oai:DiVA.org:mdh-6990DiVA, id: diva2:237000
Conference
9th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2003), Warzaw, Poland
Available from: 2009-09-25 Created: 2009-09-25 Last updated: 2018-01-13Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Pettersson, Paul

Search in DiVA

By author/editor
Pettersson, PaulYi, Wang
In the same journal
Theoretical Computer Science
Computer EngineeringEmbedded Systems

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 181 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf