DocumentCode
2157302
Title
The partitioned scheduling of sporadic tasks according to static-priorities
Author
Fisher, Nathan ; Baruah, Sanjoy ; Baker, Theodore P.
Author_Institution
Dept. of Comput. Sci., North Carolina Univ., Chapel Hill, NC
fYear
0
fDate
0-0 0
Lastpage
127
Abstract
A polynomial-time algorithm is presented for partitioning a collection of sporadic tasks among the processors of an identical multiprocessor platform with static-priority scheduling on each individual processor. Since the partitioning problem is easily seen to be NP-hard in the strong sense, this algorithm is not optimal. A quantitative characterization of its worst-case performance is provided in terms of sufficient conditions and resource augmentation approximation bounds. The partitioning algorithm is also evaluated over randomly generated task systems
Keywords
computational complexity; multiprocessing systems; processor scheduling; NP-hard problem; multiprocessor platform; partitioned scheduling; polynomial-time algorithm; sporadic tasks; static-priority scheduling; Computational modeling; Computer science; Law; Legal factors; Partitioning algorithms; Polynomials; Processor scheduling; Real time systems; Scheduling algorithm; Sufficient conditions;
fLanguage
English
Publisher
ieee
Conference_Titel
Real-Time Systems, 2006. 18th Euromicro Conference on
Conference_Location
Dresden
ISSN
1068-3070
Print_ISBN
0-7695-2619-5
Type
conf
DOI
10.1109/ECRTS.2006.30
Filename
1647731
Link To Document