Formal analysis of waiting times for distributed real-time processes
Horst F. Wedde, Bogdan Korel, Dorota M. Huizinga · 2003
An approach to automated timing analysis of distributed real-time programs is presented. The method is based on the static analysis of the task system and generation of global operation (GO) paths for which the timing analysis is applied. It is shown that a closed form solution algorithm is NP-complete. In order to more efficiently determine maximum waiting times for tasks sharing resources, even for large programs with many tasks, a reduced flow graph problem is defined by neglecting the differences in the execution times of the local operations. A solution for this problem gives an upper bound for the original analysis problem. A conjecture that the reduced problem is NP-complete even for two tasks is disproved by giving a formally correct polynomial time solution algorithm. The maximum number of steps for computing the maximum waiting for the reduced problem is linear with respect to the numbers of task's server requests.>