DP-FAIR: A Simple Model for Understanding Optimal Multiprocessor Scheduling

TitleDP-FAIR: A Simple Model for Understanding Optimal Multiprocessor Scheduling
Publication TypeConference Paper
Year of Publication2010
AuthorsLevin, G, Funk, S, Sadowski, C, Pye, I, Brandt, S
Conference NameEuromicro Conference on Real-Time Systems (ECRTS) (Best Paper Award)
Conference LocationBrussels, Belgium
ISBN Number978-1-4244-7546-9

We consider the problem of optimal real-time scheduling of periodic and sporadic tasks for identical multiprocessors. A number of recent papers have used the notions of fluid scheduling and deadline partitioning to guarantee optimality and improve performance. In this paper, we develop a unifying theory with the DP-FAIR scheduling policy and examine how it overcomes problems faced by greedy scheduling algorithms. We then present a simple DP-FAIR scheduling algorithm, DP-WRAP, which serves as a least common ancestor to many recent algorithms. We also show how to extend DP-FAIR to the scheduling of sporadic tasks with arbitrary deadlines.

Full Text