Improved conditions for bounded tardiness under EPDF fair multiprocessor scheduling

Summary form only given. The earliest-pseudo-deadline-first (EPDF) Pfair algorithm is more efficient than other known Pfair scheduling algorithms, but is not optimal on more than two processors. Srinivasan and Anderson established a sufficient per-task utilization restriction for ensuring a tardiness of at most one quantum under EPDF. They also conjectured that a tardiness bound of one quantum applies to systems that are not restricted in any way. We present counterexamples that show that this conjecture is false. We also present sufficient utilization restrictions that are more liberal than theirs.