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.

Google ScholarTM



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