Document Open Access Logo

Push Forward: Global Fixed-Priority Scheduling of Arbitrary-Deadline Sporadic Task Systems

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

PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2018.8.pdf
  • Filesize: 0.68 MB
  • 24 pages

Document Identifiers

Author Details

Jian-Jia Chen
  • TU Dortmund University, Germany
Georg von der Brüggen
  • TU Dortmund University, Germany
Niklas Ueter
  • TU Dortmund University, Germany

Funding

This paper is supported by DFG, as part of the Collaborative Research Center SFB876 (http://sfb876.tu-dortmund.de/), project B2.

Cite AsGet BibTex

Jian-Jia Chen, Georg von der Brüggen, and Niklas Ueter. Push Forward: Global Fixed-Priority Scheduling of Arbitrary-Deadline Sporadic Task Systems. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 8:1-8:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ECRTS.2018.8

Abstract

The sporadic task model is often used to analyze recurrent execution of tasks in real-time systems. A sporadic task defines an infinite sequence of task instances, also called jobs, that arrive under the minimum inter-arrival time constraint. To ensure the system safety, timeliness has to be guaranteed in addition to functional correctness, i.e., all jobs of all tasks have to be finished before the job deadlines. We focus on analyzing arbitrary-deadline task sets on a homogeneous (identical) multiprocessor system under any given global fixed-priority scheduling approach and provide a series of schedulability tests with different tradeoffs between their time complexity and their accuracy. Under the arbitrary-deadline setting, the relative deadline of a task can be longer than the minimum inter-arrival time of the jobs of the task. We show that global deadline-monotonic (DM) scheduling has a speedup bound of 3-1/M against any optimal scheduling algorithms, where M is the number of identical processors, and prove that this bound is asymptotically tight.

Subject Classification

ACM Subject Classification
  • Computer systems organization → Real-time systems
Keywords
  • global fixed-priority scheduling
  • schedulability analyses
  • speedup bounds

Metrics

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

Related Versions

Supplementary Materials

References

  1. Björn Andersson. Global static-priority preemptive multiprocessor scheduling with utilization bound 38%. In Principles of Distributed Systems, 12th International Conference, OPODIS, pages 73-88, 2008. URL: http://dx.doi.org/10.1007/978-3-540-92221-6_7.
  2. Björn Andersson, Sanjoy K. Baruah, and Jan Jonsson. Static-priority scheduling on multiprocessors. In Real-Time Systems Symposium (RTSS), pages 193-202, 2001. URL: http://dx.doi.org/10.1109/REAL.2001.990610.
  3. Theodore P Baker. An analysis of fixed-priority schedulability on a multiprocessor. Real-Time Systems, 32(1-2):49-71, 2006. URL: http://dx.doi.org/10.1007/S11241-005-4686-1.
  4. Theodore P. Baker and Michele Cirinei. Brute-force determination of multiprocessor schedulability for sets of sporadic hard-deadline tasks. In Principles of Distributed Systems, 11th International Conference, OPODIS, pages 62-75, 2007. URL: http://dx.doi.org/10.1007/978-3-540-77096-1_5.
  5. Sanjoy Baruah. Techniques for multiprocessor global schedulability analysis. In Proceedings of the 28th IEEE International Real-Time Systems Symposium, pages 119-128, 2007. URL: http://dx.doi.org/10.1109/RTSS.2007.35.
  6. Sanjoy Baruah and Enrico Bini. Partitioned scheduling of sporadic task systems: an ILP-based approach. In Proc. DASIP, 2008. Google Scholar
  7. Sanjoy K. Baruah, Vincenzo Bonifaci, Alberto Marchetti-Spaccamela, and Sebastian Stiller. Improved multiprocessor global schedulability analysis. Real-Time Systems, 46(1):3-24, 2010. URL: http://dx.doi.org/10.1007/s11241-010-9096-3.
  8. Sanjoy K. Baruah and Nathan Fisher. Global deadline-monotonic scheduling of arbitrary-deadline sporadic task systems. In Principles of Distributed Systems, 11th International Conference, OPODIS 2007, Guadeloupe, French West Indies, December 17-20, 2007. Proceedings, pages 204-216, 2007. URL: http://dx.doi.org/10.1007/978-3-540-77096-1_15.
  9. Sanjoy K. Baruah and Nathan Fisher. Global fixed-priority scheduling of arbitrary-deadline sporadic task systems. In Distributed Computing and Networking, 9th International Conference, ICDCN, pages 215-226, 2008. URL: http://dx.doi.org/10.1007/978-3-540-77444-0_20.
  10. Sanjoy K. Baruah, Aloysius K. Mok, and Louis E. Rosier. Preemptively scheduling hard-real-time sporadic tasks on one processor. In In Proceedings of the 11th Real-Time Systems Symposium, pages 182-190, 1990. URL: http://dx.doi.org/10.1109/REAL.1990.128746.
  11. Marko Bertogna, Michele Cirinei, and Giuseppe Lipari. New schedulability tests for real-time task sets scheduled by deadline monotonic on multiprocessors. In Principles of Distributed Systems, 9th International Conference, OPODIS, pages 306-321, 2005. URL: http://dx.doi.org/10.1007/11795490_24.
  12. Enrico Bini and Giorgio C. Buttazzo. Schedulability analysis of periodic fixed priority systems. IEEE Trans. Computers, 53(11):1462-1473, 2004. URL: http://dx.doi.org/10.1109/TC.2004.103.
  13. Enrico Bini and Giorgio C. Buttazzo. Measuring the performance of schedulability tests. Real-Time Systems, 30(1-2):129-154, 2005. URL: http://dx.doi.org/10.1007/s11241-005-0507-9.
  14. Enrico Bini, Thi Huyen Chau Nguyen, Pascal Richard, and Sanjoy K. Baruah. A response-time bound in fixed-priority scheduling with arbitrary deadlines. IEEE Trans. Computers, 58(2):279-286, 2009. URL: http://dx.doi.org/10.1109/TC.2008.167.
  15. Enrico Bini, Andrea Parri, and Giacomo Dossena. A quadratic-time response time upper bound with a tightness property. In IEEE Real-Time Systems Symposium (RTSS), pages 13-22, 2015. URL: http://dx.doi.org/10.1109/RTSS.2015.9.
  16. Vincenzo Bonifaci, Ho-Leung Chan, Alberto Marchetti-Spaccamela, and Nicole Megow. Algorithms and complexity for periodic real-time scheduling. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1350-1359, 2010. URL: http://dx.doi.org/10.1137/1.9781611973075.109.
  17. Jian-Jia Chen. Erratum: Global deadline-monotonic scheduling of arbitrary-deadline sporadic task systems, 2017. URL: http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2016-chen-erratum-globalDM.pdf.
  18. Jian-Jia Chen, Wen-Hung Huang, and Cong Liu. k2q: A quadratic-form response time and schedulability analysis framework for utilization-based analysis. In Real-Time Systems Symposium, RTSS, pages 351-362, 2016. URL: http://dx.doi.org/10.1109/RTSS.2016.041.
  19. Jian-Jia Chen, Georg von der Brüggen, Wen-Hung Huang, and Robert I. Davis. On the pitfalls of resource augmentation factors and utilization bounds in real-time scheduling. In Euromicro Conference on Real-Time Systems, ECRTS, pages 9:1-9:25, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ECRTS.2017.9.
  20. Jian-Jia Chen, Georg von der Brüggen, and Niklas Ueter. Evaluation results: Push forward: Global fixed-priority scheduling of arbitrary-deadline sporadic task systems. URL: http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/eval_push_forward.zip.
  21. Jian-Jia Chen, Georg von der Brüggen, and Niklas Ueter. Push forward: Global fixed-priority scheduling of arbitrary-deadline sporadic task systems, 2017. URL: http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2018-chen-ecrts-push-forward-full.pdf.
  22. Robert I. Davis and Alan Burns. Response time upper bounds for fixed priority real-time systems. In Real-Time Systems Symposium (RTSS), pages 407-418, Nov 2008. URL: http://dx.doi.org/10.1109/RTSS.2008.18.
  23. Robert I. Davis and Alan Burns. A survey of hard real-time scheduling for multiprocessor systems. ACM Comput. Surv., 43(4):35, 2011. URL: http://dx.doi.org/10.1145/1978802.1978814.
  24. Friedrich Eisenbrand and Thomas Rothvoß. Static-priority real-time scheduling: Response time computation is np-hard. In Proceedings of the 29th IEEE Real-Time Systems Symposium, RTSS, pages 397-406, 2008. URL: http://dx.doi.org/10.1109/RTSS.2008.25.
  25. Friedrich Eisenbrand and Thomas Rothvoß. EDF-schedulability of synchronous periodic task systems is coNP-hard. In ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1029-1034, 2010. URL: http://dx.doi.org/10.1137/1.9781611973075.83.
  26. Pontus Ekberg and Wang Yi. Uniprocessor feasibility of sporadic tasks remains conp-complete under bounded utilization. In 2015 IEEE Real-Time Systems Symposium, RTSS, pages 87-95, 2015. URL: http://dx.doi.org/10.1109/RTSS.2015.16.
  27. Pontus Ekberg and Wang Yi. Uniprocessor feasibility of sporadic tasks with constrained deadlines is strongly coNP-Complete. In 27th Euromicro Conference on Real-Time Systems, ECRTS, pages 281-286, 2015. URL: http://dx.doi.org/10.1109/ECRTS.2015.32.
  28. Paul Emberson, Roger Stafford, and Robert I Davis. Techniques for the synthesis of multiprocessor tasksets. In International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS 2010), pages 6-11, 2010. Google Scholar
  29. Gilles Geeraerts, Joël Goossens, and Markus Lindström. Multiprocessor schedulability of arbitrary-deadline sporadic tasks: complexity and antichain algorithm. Real-time systems, 49(2):171-218, 2013. URL: http://dx.doi.org/10.1007/s11241-012-9172-y.
  30. 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. URL: http://dx.doi.org/10.1109/RTSS.2009.11.
  31. Wen-Hung Huang and Jian-Jia Chen. Response time bounds for sporadic arbitrary-deadline tasks under global fixed-priority scheduling on multiprocessors. In International Conference on Real Time Networks and Systems, RTNS, pages 215-224, 2015. URL: http://dx.doi.org/10.1145/2834848.2834849.
  32. John P. Lehoczky. Fixed priority scheduling of periodic task sets with arbitrary deadlines. In proceedings Real-Time Systems Symposium (RTSS), pages 201-209, Dec 1990. URL: http://dx.doi.org/10.1109/REAL.1990.128748.
  33. 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. URL: http://dx.doi.org/10.1145/321738.321743.
  34. Lars Lundberg. Analyzing fixed-priority global multiprocessor scheduling. In Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 145-153, 2002. URL: http://dx.doi.org/10.1109/RTTAS.2002.1137389.
  35. Mikael Sjodin and Hans Hansson. Improved response-time analysis calculations. In Real-Time Systems Symposium, 1998. Proceedings., The 19th IEEE, pages 399-408, 1998. URL: http://dx.doi.org/10.1109/REAL.1998.739773.
  36. Youcheng Sun and Giuseppe Lipari. A pre-order relation for exact schedulability test of sporadic tasks on multiprocessor global fixed-priority scheduling. Real-Time Systems, 52(3):323-355, 2016. URL: http://dx.doi.org/10.1007/s11241-015-9245-9.
  37. Youcheng Sun, Giuseppe Lipari, Nan Guan, and Wang Yi. Improving the response time analysis of global fixed-priority multiprocessor scheduling. In International Conference on Embedded and Real-Time Computing Systems and Applications, pages 1-9, 2014. URL: http://dx.doi.org/10.1109/RTCSA.2014.6910543.
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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact