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
Multi-processor schedulability analysis of preemptive real-time tasks with variable execution times
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. (Embedded Systems)
2007 (English)In: Formal Modeling and Analysis of Timed Systems: FORMATS 2007 / [ed] Raskin JF; Thiagarajan PS, 2007, 274-289 p.Conference paper, Published paper (Refereed)
Abstract [en]

In this paper, we study schedulability analysis problems for multi-processor real-time systems. Assume a set of real-time tasks whose execution times and deadlines are known. We use timed automata to describe the non-deterministic arrival times of tasks. The schedulability problem is to check whether the released task instances can be executed within their given deadlines on a multi-processor platform where each. processor has a task queue to buffer task instances scheduled to run on the processor. On the positive side, we show that the problem is decidable for systems with non-preemptive schedulers or tasks with fixed execution times. A surprising negative result is that for multi-processor systems with variable task execution times and a preemptive scheduler, the schedulability analysis problem is undecidable, which is still an open problem in the single-processor setting.

Place, publisher, year, edition, pages
2007. 274-289 p.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 4763
National Category
Computer Science
Identifiers
URN: urn:nbn:se:uu:diva-19157DOI: 10.1007/978-3-540-75454-1_20ISI: 000250420400020ISBN: 978-3-540-75453-4 (print)OAI: oai:DiVA.org:uu-19157DiVA: diva2:46929
Conference
5th International Conference on Formal Modeling and Analysis of Timed Systems Salzburg, AUSTRIA, OCT 03-05, 2007
Available from: 2008-01-28 Created: 2008-01-28 Last updated: 2011-04-14Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Krcal, PavelStigge, MartinYi, Wang

Search in DiVA

By author/editor
Krcal, PavelStigge, MartinYi, Wang
By organisation
Computer Systems
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 455 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