A new algorithm to prove the schedulability of real-time systems

In hard real-time multiprocessor systems, tasks not only have timing constr aints but also often have precedence constraints caused by communication am ong themselves. In this paper a new algorithm to prove the schedulability o f real-time systems is proposed, in which both precedence constraints and c ommunication costs are considered and represented by offsets and modified d eadlines. To obtain a tight upper bound for the worst-case response time, t he concepts of local critical instant and local worst-case response time ar e introduced. The proposed algorithm is compared with other algorithms usin g test cases. The comparison shows that the proposed algorithm has improved the performances to these compared algorithms. (C) 2000 Elsevier Science L td. All rights reserved.