Frame-Based Proportional Round-Robin

Author

Sarkar, Arnab ; Chakrabarti, Partha P. ; Kumar, Rajeev

Author_Institution

Dept. of Comput. Sci. & Eng., Indian Inst. of Technol., Kharagpur

Volume

55

Issue

9

fYear

2006

Firstpage

1121

Lastpage

1129

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

Keywords

computational complexity; real-time systems; scheduling; FBPRR; VTRR; computational complexity; frame-based proportional round-robin method; real-time proportional fair scheduling mechanism; virtual-time round-robin; Conference management; Dynamic scheduling; Multimedia systems; Processor scheduling; Resource management; Round robin; Scheduling algorithm; Streaming media; Video on demand; Videoconference; ERfair; O(1) scheduling; Proportional fairness; real time; round-robin.; virtual time;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/TC.2006.148

Filename

1668040