License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-25374
URL: http://drops.dagstuhl.de/opus/volltexte/2010/2537/
Go to the corresponding Portal


Anderson, James ; Mills, Alex

A Stochastic Framework for Multiprocessor Soft Real-Time Scheduling

pdf-format:
Document 1.pdf (483 KB)


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.

BibTeX - Entry

@InProceedings{anderson_et_al:DSP:2010:2537,
  author =	{James Anderson and Alex Mills},
  title =	{A Stochastic Framework for Multiprocessor Soft Real-Time Scheduling},
  booktitle =	{Scheduling},
  year =	{2010},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M{\"o}hring and Kirk Pruhs},
  number =	{10071},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2537},
  annote =	{Keywords: GEDF, multiprocessor, tardiness}
}

Keywords: GEDF, multiprocessor, tardiness
Seminar: 10071 - Scheduling
Issue Date: 2010
Date of publication: 03.05.2010


DROPS-Home | Fulltext Search | Imprint Published by LZI