Elastic Scheduling for Parallel Real-Time Systems

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

doi:10.4230/LITES-v006-i001-a005

File

LITES-v006-i001-a005.pdf

Filesize: 0.54 MB
14 pages

Document Identifiers

DOI: 10.4230/LITES-v006-i001-a005
URN:

Author Details

James Orr

{Washington University in St. Louis, 1 Brookings Dr, St. Louis, MO 63130, USA

Chris Gill

Washington University in St. Louis, 1 Brookings Dr, St. Louis, MO 63130, USA

Kunal Agrawal

Washington University in St. Louis, 1 Brookings Dr, St. Louis, MO 63130, USA

Jing Li

New Jersey Institute of Technology, University Heights, Newark, NJ 07102, USA

Sanjoy Baruah

Washington University in St. Louis, 1 Brookings Dr, St. Louis, MO 63130, USA

Cite AsGet BibTex

James Orr, Chris Gill, Kunal Agrawal, Jing Li, and Sanjoy Baruah. Elastic Scheduling for Parallel Real-Time Systems. In LITES, Volume 6, Issue 1 (2019). Leibniz Transactions on Embedded Systems, Volume 6, Issue 1, pp. 05:1-05:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LITES-v006-i001-a005

Abstract

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.

Subject Classification

ACM Subject Classification

Software and its engineering → Real-time schedulability
Computer systems organization → Real-time system architecture
Computer systems organization → Real-time system specification
Computer systems organization → Embedded software

Keywords

Parallel real-time tasks
multiprocessor federated scheduling
elasticity coefficient

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

References

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.