A Stochastic Framework for Multiprocessor Soft Real-Time Scheduling

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.