Desynchronized Pfair Scheduling on Multiprocessors
UmaMaheswari C. Devi, James H. Anderson · 2005
Pfair scheduling, currently the only known way of optimally scheduling recurrent real-time tasks on multiprocessors, imposes certain requirements that may limit its practical implementation. In this paper, we address one such limitation - which requires processor time to always be allocated in units of fixed-sized quanta that are synchronized across processors - and determine the impact of relaxing it. We show that if this requirement, which may lead to wasted processor time, is relaxed, then under an otherwise-optimal Pfair scheduling algorithm deadlines are missed by at most one quantum only, which is sufficient to provide soft real-time guarantees. This result can be shown to extend to most prior work on Pfair scheduling: in general, tardiness bounds guaranteed by previously-proposed suboptimal Pfair algorithms are worsened by at most one quantum only.