Elastic Scheduling for Parallel Real-Time Systems

James Orr, Chris Gill, Kunal Agrawal, Jing Li, Sanjoy Baruah


The elastic task model was introduced by Buttazzo et al.~in order to represent recurrent real-time workloads executing upon uniprocessor platforms that are somewhat flexible with regards to timing constraints.  In this work, we propose an extension of this model and apply it to represent recurrent real-time workloads that exhibit internal parallelism and are executed on multiprocessor platforms. In our proposed extension, the elasticity coefficient - the quantitative measure of a task's elasticity that was introduced in the model proposed by Buttazzo et al. - is interpreted in the same manner as in the original (sequential) model. Hence, system developers who are familiar with the elastic task model in the uniprocessor context may use our more general model as they had previously done, now for real-time tasks whose computational demands require them to utilize more than one processor. 


Parallel real-time tasks; multiprocessor federated scheduling; elasticity coefficient

Full Text:



P. Antsaklis and J. Baillieul.Guest Editorial Special Issue on Networked Control Systems. IEEE Transactions on Automatic Control, 49(9):1421-1423, September 2004. URL: http://dx.doi.org/10.1109/TAC.2004.835210

Sanjoy Baruah, Vincenzo Bonifaci, Alberto Marchetti-Spaccamela, Leem Stougie, and Andreas Wiese.A generalized parallel task model for recurrent real-time processes. In Proceedings of the IEEE Real-Time Systems Symposium, RTSS 2012, pages 63-72, San Juan, Puerto Rico, 2012.

Giorgio Buttazzo, Enrico Bini, and Darren Buttle.Rate-Adaptive Tasks: Model, Analysis, and Design Issuess. In Proceedings of DATE 2014: Design, Automation and Test in Europe, March 2014.

Giorgio C. Buttazzo, Giuseppe Lipari, and Luca Abeni.Elastic Task Model for Adaptive Rate Control. In 1998 IEEE Real-Time Systems Symposium (RTSS), 1998.

Giorgio C. Buttazzo, Giuseppe Lipari, Marco Caccamo, and Luca Abeni.Elastic Scheduling for Flexible Workload Management. IEEE Trans. Comput., 51(3):289-302, March 2002. URL: http://dx.doi.org/10.1109/12.990127

M. Caccamo, G. Buttazzo, and Lui Sha.Elastic feedback control. In Proceedings 12th Euromicro Conference on Real-Time Systems. Euromicro RTS 2000, pages 121-128, 2000. URL: http://dx.doi.org/10.1109/EMRTS.2000.853999

T. Chantem, X. S. Hu, and M. D. Lemmon.Generalized Elastic Scheduling. In 2006 27th IEEE International Real-Time Systems Symposium (RTSS'06), pages 236-245, 2006.

T. Chantem, X. S. Hu, and M. D. Lemmon.Generalized Elastic Scheduling for Real-Time Tasks. IEEE Transactions on Computers, 58(4):480-495, April 2009. URL: http://dx.doi.org/10.1109/TC.2008.175

D. Ferry, G. Bunting, A. Maqhareh, A. Prakash, S. Dyke, K. Aqrawal, C. Gill, and C. Lu.Real-time system support for hybrid structural simulation. In 2014 International Conference on Embedded Software (EMSOFT), pages 1-10, October 2014. URL: http://dx.doi.org/10.1145/2656045.2656067

David Ferry, Jing Li, Mahesh Mahadevan, Kunal Agrawal, Christopher Gill, and Chenyang Lu.A Real-time Scheduling Service for Parallel Tasks. In Proceedings of the 2013 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS), RTAS '13, pages 261-272, Washington, DC, USA, 2013. IEEE Computer Society. URL: http://dx.doi.org/10.1109/RTAS.2013.6531098

David Ferry, Amin Maghareh, Gregory Bunting, Arun Prakash, Kunal Agrawal, Chris Gill, Chenyang Lu, and Shirley Dyke.On the performance of a highly parallelizable concurrency platform for real-time hybrid simulation. In The Sixth World Conference on Structural Control and Monitoring, 2014.

R. Graham.Bounds on multiprocessor timing anomalies.SIAM Journal on Applied Mathematics, 17:416-429, 1969.

J. Kim, H. Kim, K. Lakshmanan, and R. Rajkumar.Parallel scheduling for cyber-physical systems: Analysis and case study on a self-driving car. In 2013 ACM/IEEE International Conference on Cyber-Physical Systems (ICCPS), pages 31-40, April 2013.

Jing Li, Abusayeed Saifullah, Kunal Agrawal, Christopher Gill, and Chenyang Lu.Analysis Of Federated And Global Scheduling For Parallel Real-Time Tasks. In Proceedings of the 2012 26th Euromicro Conference on Real-Time Systems, ECRTS '14, Madrid (Spain), 2014. IEEE Computer Society Press.

C. Liu and J. Layland.Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment. Journal of the ACM, 20(1):46-61, 1973.

J. Ullman.NP-complete scheduling problems. Journal of Computer and System Sciences, 10(3):384-393, 1975.

DOI: https://doi.org/10.4230/LITES-v006-i001-a005

URN (PDF): http://nbn-resolving.de/urn:nbn:de:0030-lites-v006-i001-a005-pdf7

Copyright (c) 2019 James Orr, Chris Gill, Kunal Agrawal, Jing Li, and Sanjoy Baruah

Creative Commons License CC BY
This work is licensed under a Creative Commons Attribution 3.0 Germany License (CC BY 3.0 DE).

License URL: http://creativecommons.org/licenses/by/3.0/de/deed.en
To make this site work properly, we sometimes place small data files called cookies on your device. Cookies are only here to manage user sessions. Cookies aren’t required for simply visiting the site and read content.

Published by the European Design and Automation Association (EDAA) \ EMbedded Systems Special Interest Group (EMSIG) and Schloss Dagstuhl -- Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing. | Imprint | Data Privacy Policy