|
Abstract : |
We present a variant of Pfair scheduling, which we call early-release fair (ERfair) scheduling. Like conventional Pfair scheduling, ERfair scheduling algorithms can be applied to optimally schedule periodic tasks on a multiprocessor system in polynomial time. However, ERfair scheduling differs from Pfair scheduling in that it is work conserving. As a result, average job response times may be much lower under ERfair scheduling than under Pfair scheduling, particularly in lightly-loaded systems. In addition, runtime costs are lower under ERfair scheduling. This is because, in Pfair-scheduled systems, significant bookkeeping information is required to determine when a job of a task is and is not eligible for execution. In an ERfair system, this bookkeeping information is not required because, once released, a job continues to be eligible until it completes. To the best of our knowledge, ERfair scheduling is the first truly work-conserving scheduling discipline for periodic task systems that is optimal for multiprocessors., |
