Characterizing global work-conserving scheduling tardiness with uniform instances on multiprocessors

Abstract Soft real-time multiprocessor systems need scheduling policies introducing small overheads and for which it is possible to give guarantees on tardiness (i.e., the maximum delay that might arise with respect to job deadlines) in order to assess their feasibility in specific applications. For these reasons, lightweight policies such as Global Earliest Deadline First, and First-in First-out are preferred. Much effort has been spent in literature to provide efficiently computable tardiness bounds for periodic task systems scheduled on multiprocessors, but still, no exact bounds are known and results are given for specific classes of instances. In this paper, we use a work-conserving policy to schedule uniform instances, namely synchronous and periodic task systems in which tasks have the same period length and the same job length. We analytically derive a tight bound on the maximum tardiness and we give the exact length of the schedule hyper-period, 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.