Document Open Access Logo

Hard Real-Time Stationary GANG-Scheduling

Authors Niklas Ueter , Mario Günzel , Georg von der Brüggen , Jian-Jia Chen

PDF

File

Thumbnail PDF
PDF
LIPIcs.ECRTS.2021.10.pdf
  • Filesize: 1.23 MB
  • 19 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Computing methodologies → Concurrent algorithms
  • Computer systems organization → Embedded and cyber-physical systems
  • Computer systems organization → Real-time operating systems
Keywords
  • Real-Time Systems
  • Gang Scheduling
  • Parallel Computing
  • Scheduling Algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

The scheduling of parallel real-time tasks enables the efficient utilization of modern multiprocessor platforms for systems with real-time constrains. In this situation, the gang task model, in which each parallel sub-job has to be executed simultaneously, has shown significant performance benefits due to reduced context switches and more efficient intra-task synchronization. 
In this paper, we provide the first schedulability analysis for sporadic constrained-deadline gang task systems and propose a novel stationary gang scheduling algorithm. We show that the schedulability problem of gang task sets can be reduced to the uniprocessor self-suspension schedulability problem. Furthermore, we provide a class of partitioning algorithms to find a stationary gang assignment and show that it bounds the worst-case interference of each task. To demonstrate the effectiveness of our proposed approach, we evaluate it for implicit-deadline systems using randomized task sets under different settings, showing that our approach outperforms the state-of-the-art.

Cite As Get BibTex

Niklas Ueter, Mario Günzel, Georg von der Brüggen, and Jian-Jia Chen. Hard Real-Time Stationary GANG-Scheduling. In 33rd Euromicro Conference on Real-Time Systems (ECRTS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 196, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ECRTS.2021.10

Author Details

Niklas Ueter
  • Department of Computer Science, TU Dortmund University, Germany
Mario Günzel
  • Department of Computer Science, TU Dortmund University, Germany
Georg von der Brüggen
  • Max Planck Institute for Software Systems, Kaiserslautern, Germany
Jian-Jia Chen
  • Department of Computer Science, TU Dortmund University, Germany

Funding

This work has been supported by Deutsche Forschungsgemeinschaft (DFG), as part of Sus-Aware (Project no. 398602212). This result is part of two projects (PropRT and TOROS) that have received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreements No. 865170 and No. 803111).

References

  1. W. Ali and H. Yun. RT-Gang: Real-time gang scheduling framework for safety-critical systems. In 2019 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 143-155, 2019. URL: https://doi.org/10.1109/RTAS.2019.00020.
  2. Theodore P. Baker. Multiprocessor EDF and deadline monotonic schedulability analysis. In IEEE Real-Time Systems Symposium, pages 120-129, 2003. URL: https://doi.org/10.1109/REAL.2003.1253260.
  3. Sanjoy Baruah. Techniques for multiprocessor global schedulability analysis. In Proceedings of the 28th IEEE International Real-Time Systems Symposium, pages 119-128, 2007. Google Scholar
  4. Sanjoy Baruah. The federated scheduling of constrained-deadline sporadic DAG task systems. In Proceedings of the Design, Automation & Test in Europe Conference & Exhibition, DATE, pages 1323-1328, 2015. URL: http://dl.acm.org/citation.cfm?id=2757121.
  5. Sanjoy Baruah. Federated scheduling of sporadic DAG task systems. In IEEE International Parallel and Distributed Processing Symposium, IPDPS, pages 179-186, 2015. URL: https://doi.org/10.1109/IPDPS.2015.33.
  6. Marko Bertogna and Michele Cirinei. Response-time analysis for globally scheduled symmetric multiprocessor platforms. In Real-Time Systems Symposium (RTSS), pages 149-160, 2007. URL: https://doi.org/10.1109/RTSS.2007.31.
  7. Enrico Bini and Giorgio C. Buttazzo. Measuring the performance of schedulability tests. Real-Time Systems, 30(1-2):129-154, 2005. URL: https://doi.org/10.1007/s11241-005-0507-9.
  8. Alessandro Biondi and Youcheng Sun. On the ineffectiveness of 1/m-based interference bounds in the analysis of global EDF and FIFO scheduling. Real Time Syst., 54(3):515-536, 2018. URL: https://doi.org/10.1007/s11241-018-9303-1.
  9. J. Błażewicz, P. Dell' Olmo, M. Drozdowski, and M.G. Speranza. Corrigendum to: Scheduling multiprocessor tasks on three dedicated processors. Inf. Process. Lett., 49(5):269-270, 1994. Google Scholar
  10. Vincenzo Bonifaci, Alberto Marchetti-Spaccamela, Sebastian Stiller, and Andreas Wiese. Feasibility analysis in the sporadic dag task model. In ECRTS, pages 225-233, 2013. Google Scholar
  11. Daniel Casini, Alessandro Biondi, Geoffrey Nelissen, and Giorgio C. Buttazzo. Partitioned fixed-priority scheduling of parallel tasks without preemptions. In RTSS, pages 421-433. IEEE Computer Society, 2018. Google Scholar
  12. Jian-Jia Chen, Geoffrey Nelissen, and Wen-Hung Huang. A unifying response time analysis framework for dynamic self-suspending tasks. In Euromicro Conference on Real-Time Systems (ECRTS), pages 61-71, 2016. Google Scholar
  13. Jian-Jia Chen, Geoffrey Nelissen, Wen-Hung Huang, Maolin Yang, Björn Brandenburg, Konstantinos Bletsas, Cong Liu, Pascal Richard, Frédéric Ridouard, Neil Audsley, Raj Rajkumar, Dionisio de Niz, and Georg von der Brüggen. Many suspensions, many problems: a review of self-suspending tasks in real-time systems. Real Time Syst., 55(1):144-207, 2019. URL: https://doi.org/10.1007/s11241-018-9316-9.
  14. Jian-Jia Chen, Georg von der Brüggen, Wen-Hung Huang, and Cong Liu. State of the art for scheduling and analyzing self-suspending sporadic real-time tasks. In 23rd IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2017, Hsinchu, Taiwan, August 16-18, 2017, pages 1-10. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/RTCSA.2017.8046321.
  15. Robert I. Davis and Alan Burns. A survey of hard real-time scheduling for multiprocessor systems. ACM Comput. Surv., 43(4):35, 2011. URL: https://doi.org/10.1145/1978802.1978814.
  16. Zheng Dong and Cong Liu. Analysis techniques for supporting hard real-time sporadic gang task systems. In IEEE Real-Time Systems Symposium, RTSS, pages 128-138, 2017. URL: https://doi.org/10.1109/RTSS.2017.00019.
  17. Dror G. Feitelson and Larry Rudolph. Gang scheduling performance benefits for fine-grain synchronization. Journal of Parallel and Distributed Computing, 16:306-318, 1992. Google Scholar
  18. José Fonseca, Geoffrey Nelissen, and Vincent Nélis. Improved Response Time Analysis of Sporadic DAG Tasks for Global FP Scheduling. In Proceedings of the 25th International Conference on Real-Time Networks and Systems, 2017. URL: https://doi.org/10.1145/3139258.3139288.
  19. José Carlos Fonseca, Geoffrey Nelissen, Vincent Nélis, and Luís Miguel Pinho. Response time analysis of sporadic DAG tasks under partitioned scheduling. In SIES, pages 290-299. IEEE, 2016. Google Scholar
  20. Joël Goossens and Pascal Richard. Optimal scheduling of periodic gang tasks. LITES, 3(1):04:1-04:18, 2016. URL: https://doi.org/10.4230/LITES-v003-i001-a004.
  21. Nan Guan, Martin Stigge, Wang Yi, and Ge Yu. New response time bounds for fixed priority multiprocessor scheduling. In IEEE Real-Time Systems Symposium, pages 387-397, 2009. Google Scholar
  22. J.A. Hoogeveen, S.L. van de Velde, and B. Veltman. Complexity of scheduling multiprocessor tasks with prespecified processor allocations. Discrete Appl. Math., 55(3):259-272, 1994. Google Scholar
  23. Morris A. Jette. Performance characteristics of gang scheduling in multiprogrammed environments. In Proceedings of the 1997 ACM/IEEE Conference on Supercomputing, SC '97, 1997. Google Scholar
  24. Shinpei Kato and Yutaka Ishikawa. Gang EDF scheduling of parallel task systems. In IEEE Real-Time Systems Symposium, RTSS, pages 459-468, 2009. URL: https://doi.org/10.1109/RTSS.2009.42.
  25. M. Kubale. The complexity of scheduling independent two-processor tasks on dedicated processors. Inf. Process. Lett., 24(3):141-147, 1987. Google Scholar
  26. Karthik Lakshmanan, Shinpei Kato, and Ragunathan (Raj) Rajkumar. Scheduling parallel real-time tasks on multi-core processors. In Proceedings of the 2010 31st IEEE Real-Time Systems Symposium, RTSS '10, pages 259-268, 2010. Google Scholar
  27. C. L. Liu and James W. Layland. Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the ACM, 20(1):46-61, 1973. Google Scholar
  28. Alessandra Melani, Marko Bertogna, Vincenzo Bonifaci, Alberto Marchetti-Spaccamela, and Giorgio C. Buttazzo. Response-Time Analysis of Conditional DAG Tasks in Multiprocessor Systems. In Proceedings of the 2015 27th Euromicro Conference on Real-Time Systems, 2015. Google Scholar
  29. Aloysius K. Mok. Fundamental design problems of distributed systems for the hard-real-time environment. Technical report, Massachusetts Institute of Technology, Cambridge, MA, USA, 1983. Google Scholar
  30. Pascal Richard, Joël Goossens, and Shinpei Kato. Comments on "gang EDF schedulability analysis". CoRR, http://arxiv.org/abs/1705.05798, 2017.
  31. Youcheng Sun and Marco Di Natale. Assessing the pessimism of current multicore global fixed-priority schedulability analysis. In Proceedings of the 33rd Annual ACM Symposium on Applied Computing, SAC, pages 575-583. ACM, 2018. Google Scholar
  32. Saud Wasly and Rodolfo Pellizzoni. Bundled scheduling of parallel real-time tasks. In RTAS, pages 130-142. IEEE, 2019. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact