Characterizing G-EDF scheduling tardiness with uniform instances on multiprocessors

Soft real-time multiprocessor systems frequently adopt the G-EDF (Global-Earliest Deadline First) scheduling policy as it is lightweight and it guarantees bounded tardiness. Much effort has been spent in literature to provide efficiently computable tardiness bounds for periodic task systems scheduled on multiprocessors, but still, no exact bound is known and the best-known approximation takes non-polynomial time to compute. In this paper, we consider synchronous and periodic task systems in which tasks have the same period length and the same job length, named uniform scheduling instances. We analytically derive a tight bound on the maximum tardiness and provide the exact values of the tardiness of each processor, showing that the latter can be computed in time linear in the number of processors. This result provides a lower bound to tardiness for the more general class of instances and is intended to close the gap with the upper bound from below. We also show that the results can be applied in practice to a wider set of instances than those considered in the theoretical study.