Please use this identifier to cite or link to this item:
Title: Schedulability analysis of non-preemptive recurring real-time tasks
Authors: Baruah, S.K.
Chakraborty, S. 
Issue Date: 2006
Citation: Baruah, S.K.,Chakraborty, S. (2006). Schedulability analysis of non-preemptive recurring real-time tasks. 20th International Parallel and Distributed Processing Symposium, IPDPS 2006 2006. ScholarBank@NUS Repository.
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. © 2006 IEEE.
Source Title: 20th International Parallel and Distributed Processing Symposium, IPDPS 2006
ISBN: 1424400546
DOI: 10.1109/IPDPS.2006.1639406
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Dec 10, 2018

Page view(s)

checked on Nov 24, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.