Frame-Based Proportional Round-Robin

Abstract—All known real-time proportional fair scheduling mechanisms either have high scheduling overheads (Oðlg nÞ per time-slot) or do not efficiently handle dynamic task sets. This paper presents Frame-Based Proportional Round-Robin (FBPRR), a real-time fair scheduler providing high and bounded proportional fairness accuracy and Oð1Þ scheduling overhead with the ability to efficiently handle a set of dynamic tasks. FBPRR achieves this by applying the benefits of Virtual-Time Round-Robin (VTRR) scheduling mechanism within a frame-based scheduling approach. Simulation results show that the algorithm gains a speedup of 5 to 20 times (over Oðlg nÞ complexity schedulers) with fairly high fairness