License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.10071.4
URN: urn:nbn:de:0030-drops-25374
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2537/
Go to the corresponding Portal

Anderson, James ; Mills, Alex

A Stochastic Framework for Multiprocessor Soft Real-Time Scheduling

pdf-format:
10071.AndersonJames.Paper.2537.pdf (0.5 MB)

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: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/opus/volltexte/2010/2537},
  URN =		{urn:nbn:de:0030-drops-25374},
  doi =		{10.4230/DagSemProc.10071.4},
  annote =	{Keywords: GEDF, multiprocessor, tardiness}
}

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

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