Mixed Pfair/ERfair scheduling of asynchronous periodic tasks

摘要

Pfair scheduling was proposed by Baruah, Cohen, Plaxton, and Varvel as a non-work-conserving way of optimally and efficiently scheduling periodic tasks on a multiprocessor. In this paper, we introduce a work-conserving variant of Pfair scheduling called "early-release" fair (ERfair) scheduling. We also present a new scheduling algorithm called PD~2 and show that it is optimal for scheduling any mix of early-release and non-early-release asynchronous, periodic tasks. In contrast, almost all prior work on Pfair scheduling has been limited to synchronous systems. PD~2 is an optimization of an earlier deadline-based algorithm of Baruah, Gehrke, and Plaxton called PD; PD~2 uses a simpler tie-breaking scheme than PD to disambiguate equal deadlines. We present a series of counterexamples that suggest that, in general, the PD~2 tie-breaking mechanism cannot be simplified. In contrast to this, we show that no tie-breaking information is needed on two-processor systems.