DocumentCode :
2790134
Title :
Multiprocessor algorithms for uniprocessor feasibility analysis
Author :
Goossens, Joël ; Baruah, Sanjoy
Author_Institution :
Univ. Libre de Bruxelles, Belgium
fYear :
2000
fDate :
2000
Firstpage :
315
Lastpage :
322
Abstract :
Feasibility analysis of a hard-real-time system refers to the process of determining off-line whether the specified system will meet all deadlines at runtime. For many important (and interesting) task models and scheduling algorithms, feasibility analysis is provably computationally very expensive. A framework is established for speeding up the feasibility analysis of uniprocessor real-time systems by implementing these algorithms on parallel machines. The viability of this framework is validated by developing a parallel algorithm for the feasibility analysis of systems of asynchronous periodic tasks that are to be scheduled using the preemptive earliest deadline first scheduling algorithm, and by implementing and testing the performance of this parallel algorithm
Keywords :
multiprocessing systems; parallel algorithms; parallel machines; real-time systems; scheduling; asynchronous periodic tasks; deadlines; hard real-time system; multiprocessor algorithms; parallel algorithm; parallel machines; preemptive earliest deadline first scheduling; scheduling algorithms; task models; uniprocessor feasibility analysis; uniprocessor real-time systems; Algorithm design and analysis; Analytical models; NP-hard problem; Parallel algorithms; Parallel machines; Polynomials; Runtime; Scheduling algorithm; Terminology; Upper bound;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Real-Time Computing Systems and Applications, 2000. Proceedings. Seventh International Conference on
Conference_Location :
Cheju Island
ISSN :
1530-1427
Print_ISBN :
0-7695-0930-4
Type :
conf
DOI :
10.1109/RTCSA.2000.896407
Filename :
896407
Link To Document :
بازگشت