Search Results

Documents authored by Mills, Alex


Document
A Stochastic Framework for Multiprocessor Soft Real-Time Scheduling

Authors: James Anderson and Alex Mills

Published in: Dagstuhl Seminar Proceedings, Volume 10071, Scheduling (2010)


Abstract
Prior work has shown that the global earliest-deadline-first (GEDF) scheduling algorithm ensures bounded deadline tardiness on multiprocessors with no utilization loss; therefore, GEDF may be a good candidate scheduling algorithm for soft real-time workloads. However, such workloads are often implemented assuming an average-case provisioning, and in prior tardiness-bound derivations for GEDF, worst-case execution costs are assumed. As worst-case costs can be orders of magnitude higher than average-case costs, using a worst-case provisioning may result in significant wasted processing capacity. In this paper, prior tardiness-bound derivations for GEDF are generalized so that execution times are probabilistic, and a bound on expected (mean) tardiness is derived. It is shown that, as long as the total expected utilization is strictly less than the number of available processors, the expected tardiness of every task is bounded under GEDF. The result also implies that any quantile of the tardiness distribution is also bounded. The uploaded paper is from the upcoming RTAS. I would like to hear suggestions about how to ease the assumption of independent execution times in this analysis.

Cite as

James Anderson and Alex Mills. A Stochastic Framework for Multiprocessor Soft Real-Time Scheduling. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{anderson_et_al:DagSemProc.10071.4,
  author =	{Anderson, James and Mills, Alex},
  title =	{{A Stochastic Framework for Multiprocessor Soft Real-Time Scheduling}},
  booktitle =	{Scheduling},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10071},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.4},
  URN =		{urn:nbn:de:0030-drops-25374},
  doi =		{10.4230/DagSemProc.10071.4},
  annote =	{Keywords: GEDF, multiprocessor, tardiness}
}
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