uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • 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 using Two Clocks
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology, Computer Systems. DoCS. (Real-Time Systems)
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology, Computer Systems. DoCS. (Real-Time Systems)
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology, Computer Systems. DoCS. (Real-Time Systems)
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology, Computer Systems. DoCS. (Real-Time Systems)
2003 (English)In: Proceedings of the International Conference on Tools and Algorithms for the Construction and Analysis of Systems, 2003Conference paper, Published paper (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
2003.
National Category
Computer Science
Identifiers
URN: urn:nbn:se:uu:diva-19159ISBN: 978-3-540-00898-9 (print)OAI: oai:DiVA.org:uu-19159DiVA: diva2:46931
Available from: 2006-11-27 Created: 2006-11-27

Open Access in DiVA

No full text

Other links

http://www.springerlink.com/content/n6hpx79cueaw9rnb/?p=fd59b257722b4e768bc79175459c8d4f&pi=0

Authority records BETA

Mokrushin, LeonidPettersson, PaulYi, Wang

Search in DiVA

By author/editor
Mokrushin, LeonidPettersson, PaulYi, Wang
By organisation
Department of Information TechnologyComputer Systems
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 389 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • 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