Multi-processor schedulability analysis of preemptive real-time tasks with variable execution times
2007 (English)In: Formal Modeling and Analysis of Timed Systems: FORMATS 2007 / [ed] Raskin JF; Thiagarajan PS, 2007, 274-289 p.Conference paper (Refereed)
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.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 4763
IdentifiersURN: urn:nbn:se:uu:diva-19157DOI: 10.1007/978-3-540-75454-1_20ISI: 000250420400020ISBN: 978-3-540-75453-4OAI: oai:DiVA.org:uu-19157DiVA: diva2:46929
5th International Conference on Formal Modeling and Analysis of Timed Systems Salzburg, AUSTRIA, OCT 03-05, 2007