Tardiness bounds under global EDF scheduling on a 

Authors: UmaMaheswari C Devi J H Anderson

Publish Date: 2007/11/16

Volume: 38, Issue: 2, Pages: 133-189

PDF Link

Abstract

We consider the scheduling of a sporadic realtime task system on an identical multiprocessor Though Pfair algorithms are theoretically optimal for such task systems in practice their runtime overheads can significantly reduce the amount of useful work that is accomplished On the other hand if all deadlines need to be met then every known nonPfair algorithm requires restrictions on total system utilization that can approach approximately 50 of the available processing capacity This may be overkill for soft realtime systems which can tolerate occasional or bounded deadline misses ie bounded tardiness In this paper we derive tardiness bounds under preemptive and nonpreemptive global mathsfEDF when the total system utilization is not restricted except that it not exceed the available processing capacity Hence processor utilization can be improved for soft realtime systems on multiprocessors Our tardiness bounds depend on the total system utilization and pertask utilizations and execution costs—the lower these values the lower the tardiness bounds As a final remark we note that global mathsfEDF may be superior to partitioned mathsfEDF for multiprocessorbased soft realtime systems in that the latter does not offer any scope to improve system utilization even if bounded tardiness can be tolerated

Keywords: