Title :
Multiprocessor algorithms for uniprocessor feasibility analysis
Author :
Goossens, Joël ; Baruah, Sanjoy
Author_Institution :
Univ. Libre de Bruxelles, Belgium
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;
Conference_Titel :
Real-Time Computing Systems and Applications, 2000. Proceedings. Seventh International Conference on
Conference_Location :
Cheju Island
Print_ISBN :
0-7695-0930-4
DOI :
10.1109/RTCSA.2000.896407