Horst F. Wedde und Arnim Wedig
Worst-Case Blocking Scenarios for Distributed Real-Time Programs
Proc. of the 8th EUROMICRO Workshop on Real-Time Systems, L’Aquila, Italy, 1996-06
For detecting timing errors in distributed real-time programs it is essential to know all combinations of execution paths of subprograms t0,t1,...,tn where a given path of t o experiences a worst-case blocking time caused by a scenario of operations on execution paths of t1,...,tn, due to such operations blocking certain operations of to while accessing shared resources. This paper deals with the problem of determining all possible worst-case blocking scenarios of an execution path of to by execution paths of t1,...,tn . While this problem is NP-hard we give a polynomial algorithm for an associated (reduced) problem which computes an often tight superset of these scenarios in a variety of practically relevant application situations.