1 Search Results for "Voronov, Sergey"

Document
DOI: 10.4230/LIPIcs.ECRTS.2019.13
GEDF Tardiness: Open Problems Involving Uniform Multiprocessors and Affinity Masks Resolved

Authors: Stephen Tang, Sergey Voronov, and James H. Anderson

Published in: LIPIcs, Volume 133, 31st Euromicro Conference on Real-Time Systems (ECRTS 2019)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{tang_et_al:LIPIcs.ECRTS.2019.13,
  author =	{Tang, Stephen and Voronov, Sergey and Anderson, James H.},
  title =	{{GEDF Tardiness: Open Problems Involving Uniform Multiprocessors and Affinity Masks Resolved}},
  booktitle =	{31st Euromicro Conference on Real-Time Systems (ECRTS 2019)},
  pages =	{13:1--13:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-110-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{133},
  editor =	{Quinton, Sophie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2019.13},
  URN =		{urn:nbn:de:0030-drops-107504},
  doi =		{10.4230/LIPIcs.ECRTS.2019.13},
  annote =	{Keywords: scheduling theory, multicore, processor affinity masks, GEDF, uniform multiprocessors}
}
  • Refine by Author
  • 1 Anderson, James H.
  • 1 Tang, Stephen
  • 1 Voronov, Sergey

  • Refine by Classification
  • 1 Software and its engineering → Real-time schedulability

  • Refine by Keyword
  • 1 GEDF
  • 1 multicore
  • 1 processor affinity masks
  • 1 scheduling theory
  • 1 uniform multiprocessors

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

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