DocumentCode :
1913864
Title :
DP-FAIR: A Simple Model for Understanding Optimal Multiprocessor Scheduling
Author :
Levin, Greg ; Funk, Shelby ; Sadowski, Caitlin ; Pye, Ian ; Brandt, Scott
Author_Institution :
Comput. Sci. Dept., Univ. of California, Santa Cruz, CA, USA
fYear :
2010
fDate :
6-9 July 2010
Firstpage :
3
Lastpage :
13
Abstract :
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.
Keywords :
greedy algorithms; processor scheduling; DP-FAIR; DP-WRAP; greedy scheduling algorithms; optimal multiprocessor scheduling; Algorithm design and analysis; Partitioning algorithms; Program processors; Schedules; Scheduling; Scheduling algorithm;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Real-Time Systems (ECRTS), 2010 22nd Euromicro Conference on
Conference_Location :
Brussels
ISSN :
1068-3070
Print_ISBN :
978-1-4244-7546-9
Electronic_ISBN :
1068-3070
Type :
conf
DOI :
10.1109/ECRTS.2010.34
Filename :
5562894
Link To Document :
بازگشت