GEDF Tardiness: Open Problems Involving Uniform Multiprocessors and Affinity Masks Resolved

Authors Stephen Tang, Sergey Voronov, James H. Anderson



PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2019.13.pdf
  • Filesize: 0.59 MB
  • 21 pages

Document Identifiers

Author Details

Stephen Tang
  • Department of Computer Science, University of North Carolina at Chapel Hill, NC, USA
Sergey Voronov
  • Department of Computer Science, University of North Carolina at Chapel Hill, NC, USA
James H. Anderson
  • Department of Computer Science, University of North Carolina at Chapel Hill, NC, USA

Cite AsGet BibTex

Stephen Tang, Sergey Voronov, and James H. Anderson. GEDF Tardiness: Open Problems Involving Uniform Multiprocessors and Affinity Masks Resolved. In 31st Euromicro Conference on Real-Time Systems (ECRTS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 133, pp. 13:1-13:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ECRTS.2019.13

Abstract

Prior work has shown that the global earliest-deadline-first (GEDF) scheduler is soft real-time (SRT)-optimal for sporadic task systems in a variety of contexts, meaning that bounded deadline tardiness can be guaranteed under it for any task system that does not cause platform overutilization. However, one particularly compelling context has remained elusive: multiprocessor platforms in which tasks have affinity masks that determine the processors where they may execute. Actual GEDF implementations, such as the SCHED_DEADLINE class in Linux, have dealt with this unresolved question by foregoing SRT guarantees once affinity masks are set. This unresolved question, as it pertains to SCHED_DEADLINE, was included by Peter Zijlstra in a list of important open problems affecting Linux in his keynote talk at ECRTS 2017. In this paper, this question is resolved along with another open problem that at first blush seems unrelated but actually is. Specifically, both problems are closed by establishing two results. First, a proof strategy used previously to establish GEDF tardiness bounds that are exponential in size on heterogeneous uniform multiprocessors is generalized to show that polynomial bounds exist on a wider class of platforms. Second, both uniform multiprocessors and identical multiprocessors with affinities are shown to be within this class. These results yield the first polynomial GEDF tardiness bounds for the uniform case and the first such bounds of any kind for the identical-with-affinities case.

Subject Classification

ACM Subject Classification
  • Software and its engineering → Real-time schedulability
Keywords
  • scheduling theory
  • multicore
  • processor affinity masks
  • GEDF
  • uniform multiprocessors

Metrics

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

References

  1. Luca Abeni. SCHED_DEADLINE: a real-time CPU scheduler for Linux. 2nd TuTor at the 38th IEEE Real-Time Systems Symposium, 2017. URL: https://tutor2017.inria.fr/sched_deadline/.
  2. Luca Abeni et al. Deadline Task Scheduling. Linux kernel documentation, 2018. URL: https://github.com/torvalds/linux/blob/master/Documentation/scheduler/sched-deadline.txt.
  3. Claude Berge. Two theorems in graph theory. Proceedings of the National Academy of Sciences, 43(9):842-844, 1957. Google Scholar
  4. Aaron Block, UmaMaheswari C. Devi, and James H. Anderson. Task reweighting under global scheduling on multiprocessors. In Proceedings of the 18th Euromicro Conference on Real-Time Systems, pages 123-167, 2006. Google Scholar
  5. UmaMaheswari C. Devi and James H. Anderson. Tardiness bounds under global EDF scheduling on a multiprocessor. Real-Time Systems, 38(2):133-189, 2008. Google Scholar
  6. Shelby Funk, Joel Goossens, and Sanjoy Baruah. On-line scheduling on uniform multiprocessors. In Proceedings of the 22th IEEE Real-Time Systems Symposium, pages 183-192, 2001. Google Scholar
  7. Stephen Tang, Sergey Voronov, and James H. Anderson. GEDF tardiness: Open problems involving uniform multiprocessors and affinity masks resolved. Full version of this paper, available at http://www.cs.unc.edu/~anderson/papers.html.
  8. Sergey Voronov and James H. Anderson. AM-Red: An optimal semi-partitioned scheduler assuming arbitrary affinity masks. In Proceedings of the 39th IEEE Real-Time Systems Symposium, pages 408-420, 2018. Google Scholar
  9. Kecheng Yang and James H. Anderson. On the Soft Real-Time Optimality of Global EDF on Uniform Multiprocessors. In Proceedings of the 38th IEEE Real-Time Systems Symposium, pages 319-330, 2017. Google Scholar
  10. Peter Zijlstra. An update on Real-Time scheduling on Linux. Keynote talk at the 29th Euromicro Conference on Real-Time Systems, 2017. URL: https://www.ecrts.org/archives/index.php?id=284.
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