Please use this identifier to cite or link to this item: https://doi.org/10.1109/IPDPS.2006.1639406
Title: Schedulability analysis of non-preemptive recurring real-time tasks
Authors: Baruah, S.K.
Chakraborty, S. 
Issue Date: 2006
Source: 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. https://doi.org/10.1109/IPDPS.2006.1639406
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
URI: http://scholarbank.nus.edu.sg/handle/10635/40202
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.

SCOPUSTM   
Citations

16
checked on Nov 29, 2017

Page view(s)

46
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


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