2026-07-25T15:15:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2537 2024-03-06T11:09:09Z ddc:004 open_access

A Stochastic Framework for Multiprocessor Soft Real-Time Scheduling Anderson, James Mills, Alex GEDF multiprocessor tardiness 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik James Anderson and Alex Mills 2010 Is Part Of Dagstuhl Seminar Proceedings, Volume 10071, Scheduling (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.10071.4 urn:nbn:de:0030-drops-25374 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.4 eng https://creativecommons.org/licenses/by/4.0/legalcode