License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ECRTS.2019.13
URN: urn:nbn:de:0030-drops-107504
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10750/
Go to the corresponding LIPIcs Volume Portal

Tang, Stephen ; Voronov, Sergey ; Anderson, James H.

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

pdf-format:
LIPIcs-ECRTS-2019-13.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{tang_et_al:LIPIcs:2019:10750,
  author =	{Stephen Tang and Sergey Voronov and James H. Anderson},
  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 =	{Sophie Quinton},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10750},
  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}
}

Keywords: scheduling theory, multicore, processor affinity masks, GEDF, uniform multiprocessors
Collection: 31st Euromicro Conference on Real-Time Systems (ECRTS 2019)
Issue Date: 2019
Date of publication: 02.07.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI