Schedulability analysis of non-preemptive recurring real-time tasks

Sanjoy K. Baruah, Samarjit Chakraborty

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

32 Zitate (Scopus)

Abstract

The recurring real-time task model was recently proposed as a model for real-time processes that contain code with conditional branches. In this paper, we present a necessary and sufficient condition for uniprocessor non-preemptive schedulability analysis for this task model. We also derive a polynomial-time approximation algorithm for testing this condition. Preemptive schedulers usually have a larger schedulability region compared to their non-preemptive counterparts. Further, for most realistic task models, schedulability analysis for the non-preemptive version is computationally more complex compared to the corresponding preemptive version. Our results in this paper show that (surprisingly) the recurring real-time task model does not fall in line with these intuitive expectations, i.e. there exists polynomial-time approximation algorithms for both preemptive and non-preemptive versions of schedulability analysis. This has important implications on the applicability of this model, since fully preemptive scheduling algorithms often have significantly larger runtime over-heads.

OriginalspracheEnglisch
Titel20th International Parallel and Distributed Processing Symposium, IPDPS 2006
Herausgeber (Verlag)IEEE Computer Society
ISBN (Print)1424400546, 9781424400546
DOIs
PublikationsstatusVeröffentlicht - 2006
Extern publiziertJa
Veranstaltung20th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2006 - Rhodes Island, Griechenland
Dauer: 25 Apr. 200629 Apr. 2006

Publikationsreihe

Name20th International Parallel and Distributed Processing Symposium, IPDPS 2006
Band2006

Konferenz

Konferenz20th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2006
Land/GebietGriechenland
OrtRhodes Island
Zeitraum25/04/0629/04/06

Fingerprint

Untersuchen Sie die Forschungsthemen von „Schedulability analysis of non-preemptive recurring real-time tasks“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren