Schedulability analysis of non-preemptive recurring real-time tasks

Sanjoy K. Baruah, Samarjit Chakraborty

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

32 Scopus citations

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.

Original languageEnglish
Title of host publication20th International Parallel and Distributed Processing Symposium, IPDPS 2006
PublisherIEEE Computer Society
ISBN (Print)1424400546, 9781424400546
DOIs
StatePublished - 2006
Externally publishedYes
Event20th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2006 - Rhodes Island, Greece
Duration: 25 Apr 200629 Apr 2006

Publication series

Name20th International Parallel and Distributed Processing Symposium, IPDPS 2006
Volume2006

Conference

Conference20th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2006
Country/TerritoryGreece
CityRhodes Island
Period25/04/0629/04/06

Fingerprint

Dive into the research topics of 'Schedulability analysis of non-preemptive recurring real-time tasks'. Together they form a unique fingerprint.

Cite this