Document Open Access Logo

Tight Tardiness Bounds for Pseudo-Harmonic Tasks Under Global-EDF-Like Schedulers

Authors Shareef Ahmed, James H. Anderson

PDF

File

Thumbnail PDF
PDF
LIPIcs.ECRTS.2021.11.pdf
  • Filesize: 0.94 MB
  • 24 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Computer systems organization → Real-time systems
Keywords
  • soft real-time systems
  • multicore
  • tardiness bounds

Metrics

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

Abstract

The global earliest-deadline-first (GEDF) scheduler and its variants are soft-real-time (SRT) optimal for periodic/sporadic tasks, meaning they provide bounded tardiness so long as the underlying platform is not over-utilized. Although their SRT-optimality has long been known, tight tardiness bounds for these schedulers have remained elusive. In this paper, a tardiness bound, that does not depend on the processor or task count, is derived for pseudo-harmonic periodic tasks, which are commonly used in practice, under global-EDF-like (GEL) schedulers. This class of schedulers includes both GEDF and first-in-first-out (FIFO). This bound is shown to be generally tight via an example. Furthermore, it is shown that exact tardiness bounds for GEL-scheduled pseudo-harmonic periodic tasks can be computed in pseudo-polynomial time.

Cite As Get BibTex

Shareef Ahmed and James H. Anderson. Tight Tardiness Bounds for Pseudo-Harmonic Tasks Under Global-EDF-Like Schedulers. In 33rd Euromicro Conference on Real-Time Systems (ECRTS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 196, pp. 11:1-11:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ECRTS.2021.11

Author Details

Shareef Ahmed
  • University of North Carolina at Chapel Hill, NC, USA
James H. Anderson
  • University of North Carolina at Chapel Hill, NC, USA

Funding

Work was supported by NSF grants CNS 1563845, CNS 1717589, CPS 1837337, CPS 2038855, and CPS 2038960, ARO grant W911NF-20-1-0237, and ONR grant N00014-20-1-2698.

References

  1. S. Ahmed and J. Anderson. A soft-real-time-optimal semi-clustered scheduler with a constant tardiness bound. In RTCSA'20, pages 1-10. IEEE, 2020. Google Scholar
  2. J. Anderson and A. Srinivasan. Mixed pfair/erfair scheduling of asynchronous periodic tasks. Journal of Computer and System Sciences, 68(1):157-204, 2004. Google Scholar
  3. S. Anssi, S. Kuntz, S. Gérard, and F. Terrier. On the gap between schedulability tests and an automotive task model. Journal of Systems Architecture, 59(6):341-350, 2013. Google Scholar
  4. S. Baruah, N. Cohen, C. Plaxton, and D. Varvel. Proportionate progress: A notion of fairness in resource allocation. Algorithmica, 15(6):600-625, 1996. Google Scholar
  5. S. Baruah, J. Gehrke, and C. Plaxton. Fast scheduling of periodic tasks on multiple resources. In IPSS'95, pages 280-288. IEEE, 1995. Google Scholar
  6. J. Busquets-Mataix, J. Serrano, R. Ors, P. Gil, and A. Wellings. Using harmonic task-sets to increase the schedulable utilization of cache-based preemptive real-time systems. In RTCSA '96, pages 195-202. IEEE, 1996. Google Scholar
  7. L. Cucu-Grosjean and J. Goossens. Exact schedulability tests for real-time scheduling of periodic tasks on unrelated multiprocessor platforms. Journal of Systems Architecture, 57(5):561-569, 2011. Google Scholar
  8. U. Devi and J. Anderson. Tardiness bounds under global EDF scheduling on a multiprocessor. In RTSS '05, pages 330-341. IEEE, 2005. Google Scholar
  9. U. Devi and J. Anderson. Tardiness bounds under global EDF scheduling on a multiprocessor. Real-Time Systems, 38(2):133-189, 2008. Google Scholar
  10. S. Dhall and C. Liu. On a real-time scheduling problem. Operations Research, 26(1):127-140, 1978. Google Scholar
  11. J. Erickson, J. Anderson, and B. Ward. Fair lateness scheduling: reducing maximum lateness in G-EDF-like scheduling. Real-Time Systems, 50(1):5-47, 2014. Google Scholar
  12. J. Erickson, U. Devi, and S. Baruah. Improved tardiness bounds for global EDF. In ECRTS'10, pages 14-23. IEEE, 2010. Google Scholar
  13. L. Abeni et al. Deadline task scheduling. Linux kernel documentation. https://github.com/torvalds/linux/blob/master/Documentation/scheduler/sched-deadline.rst. [Online; accessed 06-May-2021].
  14. Y. Fu, N. Kottenstette, Y. Chen, C. Lu, X. Koutsoukos, and H. Wang. Feedback thermal control for real-time systems. In RTAS'10, pages 111-120. IEEE, 2010. Google Scholar
  15. J. Goossens, E. Grolleau, and L. Cucu-Grosjean. Periodicity of real-time schedules for dependent periodic tasks on identical multiprocessor platforms. Real-Time Systems, 52(6):808-832, 2016. Google Scholar
  16. C. Kenna, J. Herman, B. Brandenburg, A. Mills, and J. Anderson. Soft real-time on multiprocessors: Are analysis-based schedulers really worth it? In RTSS'11, pages 93-103. IEEE, 2011. Google Scholar
  17. Simon Kramer, Dirk Ziegenbein, and Arne Hamann. Real world automotive benchmarks for free. In WATERS'15, 2015. Google Scholar
  18. M. Leoncini, M. Montangero, and P. Valente. A parallel branch-and-bound algorithm to compute a tighter tardiness bound for preemptive global EDF. Real-Time Systems, 55(2):349-386, 2019. Google Scholar
  19. H. Leontyev and J. Anderson. Tardiness bounds for FIFO scheduling on multiprocessors. In ECRTS'07, page 71. IEEE, 2007. Google Scholar
  20. H. Leontyev and J. Anderson. Generalized tardiness bounds for global multiprocessor scheduling. Real-Time Systems, 44(1-3):26-71, 2010. Google Scholar
  21. H. Li, J. Sweeney, K. Ramamritham, R. Grupen, and P. Shenoy. Real-time support for mobile robotics. In RTAS'03, pages 10-18. IEEE, 2003. Google Scholar
  22. V. Nélis, P. Yomsi, and J. Goossens. Feasibility intervals for homogeneous multicores, asynchronous periodic tasks, and FJP schedulers. In RTNS'13, pages 277-286. ACM, 2013. Google Scholar
  23. P. Regnier, G. Lima, E. Massa, G. Levin, and S. Brandt. RUN: optimal multiprocessor real-time scheduling via reduction to uniprocessor. In RTSS'11, pages 104-115. IEEE, 2011. Google Scholar
  24. C. Shih, S. Gopalakrishnan, P. Ganti, M. Caccamo, and L. Sha. Scheduling real-time dwells using tasks with synthetic periods. In RTSS'03, pages 210-219. IEEE, 2003. Google Scholar
  25. S. Tang and J. Anderson. Towards practical multiprocessor EDF with affinities. In RTSS'20, IEEE, pages 89-101, 2020. Google Scholar
  26. S. Tang, S. Voronov, and J. Anderson. GEDF tardiness: Open problems involving uniform multiprocessors and affinity masks resolved. In ECRTS'19, pages 13:1-13:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  27. P. Valente. Using a lag-balance property to tighten tardiness bounds for global EDF. Real-Time Systems, 52(4):486-561, 2016. Google Scholar
  28. K. Yang and J. Anderson. On the soft real-time optimality of global EDF on uniform multiprocessors. In RTSS'17, pages 319-330. IEEE, 2017. 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