University of North Carolina
The authors consider the issue of deadline tardiness under global multiprocessor scheduling algorithms. They present a general tardiness-bound derivation that is applicable to a wide variety of such algorithms (including some whose tardiness behavior has not been analyzed before). Their derivation is very general: job priorities may change rather arbitrarily at runtime, capacity restrictions may exist on certain processors, and, under certain conditions, non-preemptive regions are allowed. Their results show that, with the exception of static-priority algorithms, most global algorithms considered previously have bounded tardiness.