Skip to main content
SpringerLink
Log in

Parallel Real-Time Scheduling

  • Living reference work entry
  • First Online:
Handbook of Real-Time Computing

  • 61 Accesses

Abstract

This chapter of the survey provides a basic introduction to real-time scheduling for parallel tasks on multicore platforms and gives an overview of the relevant results. Parallel real-time tasks are the tasks that can utilize multiple cores at the same time to complete more computation with the same real-time constraints than sequential tasks. For parallel real-time systems, researchers have studied three types of scheduling strategies: decomposition-based scheduling, global scheduling, and federated scheduling. The survey summarizes the results of these three types of scheduling strategies, including results for different parallel task models, different response time analyses, and theoretical bounds, as well as system implementation and empirical evaluations. In addition, the survey also covers some work for mixed-criticality systems that have parallel tasks.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Similar content being viewed by others

References

  • K. Agrawal, S. Baruah, A measurement-based model for parallel real-time tasks, in Proceedings of the 30th Euromicro Conference on Real-Time Systems (ECRTS), Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, 2018

    Google Scholar 

  • B. Andersson, D. de Niz, Analyzing Global-Edf for Multiprocessor Scheduling of Parallel Tasks, in: International Conference On Principles Of Distributed Systems, Springer, 2012, pp. 16–30

    Google Scholar 

  • P. Axer, S. Quinton, M. Neukirchner, R. Ernst, B. Döbel, H. Härtig, Response-time analysis of parallel fork-join workloads with real-time constraints. In: Proceedings of the 25th Euromicro Conference on Real-Time Systems (ECRTS), 2013, pp. 215–224

    Google Scholar 

  • S. Baruah, Improved multiprocessor global schedulability analysis of sporadic dag task systems, in Proceedings of the 26th Euromicro Conference on Real-Time Systems (ECRTS), IEEE, 2014, pp. 97–105

    Google Scholar 

  • S. Baruah, The federated scheduling of constrained-deadline sporadic dag task systems, in: Proceedings of the 2015 Design, Automation & Test in Europe Conference & Exhibition, EDA Consortium, 2015a, pp. 1323–1328

    Google Scholar 

  • S. Baruah, Federated scheduling of sporadic dag task systems, in: Parallel and Distributed Processing Symposium (IPDPS), 2015 IEEE International, IEEE, 2015b, pp. 179–186

    Google Scholar 

  • S. Baruah, The federated scheduling of systems of conditional sporadic dag tasks, in Proceedings of the 12th International Conference on Embedded Software, IEEE Press, 2015c, pp. 1–10

    Google Scholar 

  • S. Baruah, The federated scheduling of systems of mixed-criticality sporadic dag tasks, in Real-time systems symposium (RTSS), 2016 IEEE, IEEE, 2016, pp. 227–236

    Google Scholar 

  • S. Baruah, V. Bonifaci, A. Marchetti-Spaccamela, L. Stougie, A. Wiese, A generalized parallel task model for recurrent real-time processes. In: Real-Time Systems Symposium (RTSS), 2012 IEEE 33rd, IEEE, 2012, pp 63–72

    Google Scholar 

  • R.D. Blumofe, C.F. Joerg, B.C. Kuszmaul, C.E. Leiserson, K.H. Randall, Y. Zhou, Cilk: an efficient multithreaded runtime system. J. Parallel Distrib. Comput. 37(1), 55–69 (1996)

    Article  Google Scholar 

  • V. Bonifaci, A. Marchetti-Spaccamela, S. Stiller, A. Wiese, Feasibility analysis in the sporadic dag task model, in Proceedings of the 25th Euromicro Conference on Real-Time Systems (ECRTS), IEEE, 2013, pp. 225–233

    Google Scholar 

  • B.B. Brandenburg, J.H. Anderson, (2009) On the implementation of global real-time schedulers, in 30th IEEE Real-Time Systems Symposium (RTSS), pp 214–224

    Google Scholar 

  • G. Buttazzo, E. Bini, Y. Wu, Partitioning parallel applications on multiprocessor reservations, in Proceedings of the 22nd Euromicro Conference on Real-Time Systems (ECRTS), IEEE, 2010, pp. 24–33

    Google Scholar 

  • J.J. Chen, Federated scheduling admits no constant speedup factors for constrained-deadline dag task systems. Real-Time Syst 52(6), 833–838 (2016)

    Article  Google Scholar 

  • H.S. Chwa, J. Lee, K.M. Phan, A. Easwaran, I. Shin, Global edf schedulability analysis for synchronous parallel tasks on multicore platforms, in Proceedings of the 25th Euromicro Conference on Real-Time Systems (ECRTS), IEEE, 2013, pp. 25–34

    Google Scholar 

  • H.S. Chwa, J. Lee, J. Lee, K.M. Phan, A. Easwaran, I. Shin, Global edf schedulability analysis for parallel tasks on multi-core platforms. IEEE Trans. Parallel Distrib. Syst. 28(5), 1331–1345 (2017)

    Article  Google Scholar 

  • CilkPlus, Intel CilkPlus v1.2, 2013., https://www.cilkplus.org/sites/default/files/open_specifications/Intel_Cilk_plus_lang_spec_1.2.htm

  • R.I. Davis, A. Burns, A survey of hard real-time scheduling for multiprocessor systems. ACM Comput. Surv. 43(4), 35 (2011)

    Article  Google Scholar 

  • D. Ferry, J. Li, M. Mahadevan, K. Agrawal, C. Gill, C. Lu (2013) A real-time scheduling service for parallel tasks, in Real-Time and Embedded Technology and Applications Symposium (RTAS), 2013 IEEE 19th, IEEE, pp 261–272

    Google Scholar 

  • Y. He, C.E. Leiserson, W.M. Leiserson, The Cilkview scalability analyzer, in: Proceedings of the Twenty-Second Annual ACM Symposium on Parallelism in Algorithms and Architectures, ACM, 2010, pp. 145–156

    Google Scholar 

  • X. Jiang, X. Long, N. Guan, H. Wan, On the decomposition-based global edf scheduling of parallel real-time tasks, in Real-Time Systems Symposium (RTSS), 2016 IEEE, IEEE, 2016, pp. 237–246

    Google Scholar 

  • X. Jiang, N. Guan, X. Long, W. Yi, Semi-federated scheduling of parallel real-time tasks on multiprocessors. In Real-Time Systems Symposium (RTSS), IEEE, 2017, pp. 80–91.

    Google Scholar 

  • J. Kim, H. Kim, K. Lakshmanan, R.R. Rajkumar, Parallel scheduling for cyber-physical systems: analysis and case study on a self-driving car, in Proceedings of the ACM/IEEE 4th International Conference on Cyber-Physical Systems, ACM, 2013, pp. 31–40

    Google Scholar 

  • K. Lakshmanan, S. Kato, R. Rajkumar, Scheduling parallel real-time tasks on multi-core processors, in Real-Time Systems Symposium (RTSS), 2010 IEEE 31st, IEEE, 2010, pp. 259–268

    Google Scholar 

  • D. Leijen, W. Schulte, S. Burckhardt, The design of a task parallel library. ACM SIGPLAN Not. 44(10), 227–242 (2009)

    Article  Google Scholar 

  • J. Li, K. Agrawal, C. Lu, C. Gill, Analysis of global edf for parallel tasks, in Proceedings of the 25th Euromicro Conference on Real-Time Systems (ECRTS), IEEE, 2013, pp. 3–13

    Google Scholar 

  • J. Li, K. Agrawal, C. Gill, C. Lu, Federated scheduling for stochastic parallel real-time tasks, in Embedded and real-time computing systems and applications (RTCSA), 2014 IEEE 20th International Conference on, IEEE, 2014a, pp. 1–10

    Google Scholar 

  • J. Li, J.J. Chen, K. Agrawal, C. Lu, C. Gill, A. Saifullah, Analysis of federated and global scheduling for parallel real-time tasks, in Proceedings of the 26th Euromicro Conference on Real-Time Systems (ECRTS), IEEE, 2014b, pp. 85–96

    Google Scholar 

  • J. Li, Z. Luo, D. Ferry, K. Agrawal, C. Gill, C. Lu, Global edf scheduling for parallel real-time tasks. Real-Time Syst 51(4), 395–439 (2015)

    Article  Google Scholar 

  • J. Li, S. Dinh, K. Kieselbach, K. Agrawal, C. Gill, C. Lu, Randomized work stealing for large scale soft real-time systems, in Real-Time Systems Symposium (RTSS), 2016 IEEE, IEEE, 2016, pp. 203–214

    Google Scholar 

  • J. Li, D. Ferry, S. Ahuja, K. Agrawal, C. Gill, C. Lu, Mixed-criticality federated scheduling for parallel real-time tasks. Real-Time Syst. 53(5), 760–811 (2017)

    Article  Google Scholar 

  • C. Liu, J.H. Anderson, Supporting soft real-time parallel applications on multicore processors, in Embedded and Real-Time Computing Systems and Applications (RTCSA), 2012 IEEE 18th International Conference on, IEEE, 2012, pp. 114–123

    Google Scholar 

  • G. Liu, Y. Lu, S. Wang, Z. Gu, Partitioned multiprocessor scheduling of mixed-criticality parallel jobs, in: Embedded and real-time computing systems and applications (RTCSA), 2014 IEEE 20th International Conference on, IEEE, 2014, pp. 1–10

    Google Scholar 

  • C. Maia, M. Bertogna, L. Nogueira, L.M. Pinho, Response-time analysis of synchronous parallel tasks in multiprocessor systems, in: Proceedings of the 22nd International Conference on Real-Time Networks and Systems, ACM, 2014, p. 3

    Google Scholar 

  • G. Nelissen, V. Berten, J. Goossens, D. Milojevic, Techniques optimizing the number of processors to schedule multi-threaded tasks, in Proceedings of the 24th Euromicro Conference on Real-Time Systems (ECRTS), IEEE, 2012, pp. 321–330

    Google Scholar 

  • OpenMP, OpenMP Application Program Interface v4.0, 2013., http://www.openmp.org/mp-documents/OpenMP4.0.0.pdf

  • J. Reinders, Intel Threading Building Blocks: Outfitting C++ for Multi-Core Processor Parallelism (O’Reilly Media, 2010)

    Google Scholar 

  • A. Saifullah, J. Li, K. Agrawal, C. Lu, C. Gill, Multi-core real-time scheduling for generalized parallel task models. Real-Time Syst. 49(4), 404–435 (2013)

    Article  Google Scholar 

  • A. Saifullah, D. Ferry, J. Li, K. Agrawal, C. Lu, C.D. Gill, Parallel real-time scheduling of dags. IEEE Trans. Parallel Distrib. Syst. 25(12), 3242–3252 (2014)

    Article  Google Scholar 

  • T.B. Schardl, B.C. Kuszmaul, I. Lee, W.M. Leiserson, C.E. Leiserson, et al., The Cilkprof scalability profiler, in Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures, ACM, 2015, pp. 89–100

    Google Scholar 

  • M.A. Serrano, A. Melani, S. Kehr, M. Bertogna, E. Quinones, An analysis of lazy and eager limited preemption approaches under dag-based global fixed priority scheduling, in Real-Time Distributed Computing (ISORC), 2017 IEEE 20th International Symposium on, IEEE, 2017, pp. 193–202

    Google Scholar 

  • O. Tardieu, H. Wang, H. Lin, A work-stealing scheduler for x10’s task parallelism with suspension. ACM SIGPLAN Not. 47(8), 267–276 (2012)

    Article  Google Scholar 

  • Q. Wang, G. Parmer, 2014 FJOS: Practical, predictable, and efficient system support for fork/join parallelism. in Real-Time and Embedded Technology and Applications Symposium (RTAS), 2014 IEEE 20th, IEEE, pp. 25–36

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. New Jersey Institute of Technology, Newark, NJ, USA

    Jing Li

  2. Washington University in St. Louis, St. Louis, MO, USA

    Kunal Agrawal & Chenyang Lu

Authors
  1. Jing Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Kunal Agrawal
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Chenyang Lu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jing Li .

Editor information

Editors and Affiliations

  1. School of Electrical Engineering and Computer Science, Queensland University of Technology, Brisbane, QLD, Australia

    Yu-Chu Tian

  2. School of Electrical and Information Engineering, The University of Sydney, Sydney, NSW, Australia

    David Charles Levy

Section Editor information

  1. School of Computer Science and Engineering, Nanyang Technological University, Singapore, Singapore

    Arvind Easwaran

Rights and permissions

Reprints and permissions

Copyright information

© 2021 Springer Nature Singapore Pte Ltd.

About this entry

Check for updates. Verify currency and authenticity via CrossMark

Cite this entry

Li, J., Agrawal, K., Lu, C. (2021). Parallel Real-Time Scheduling. In: Tian, YC., Levy, D.C. (eds) Handbook of Real-Time Computing. Springer, Singapore. https://doi.org/10.1007/978-981-4585-87-3_28-1

Download citation

  • DOI: https://doi.org/10.1007/978-981-4585-87-3_28-1

  • Received:

  • Accepted:

  • Published:

  • Publisher Name: Springer, Singapore

  • Print ISBN: 978-981-4585-87-3

  • Online ISBN: 978-981-4585-87-3

  • eBook Packages: Springer Reference EngineeringReference Module Computer Science and Engineering

Publish with us

Policies and ethics

Search

Navigation