Scalable Dynamic Deadlock Analysis of MultiThreaded Programs

This paper presents a dynamic program analysis algorithm that can detect deadlock potentials in a multi-threaded program by examining a single execution trace, obtained by running an instrumented version of the program. The algorithm is interesting because it can identify deadlock potentials even though no deadlocks occur in the examined execution, and therefore it scales very well in contrast to more formal approaches to deadlock detection. It is an improvement of an existing algorithm in that it reduces the number of false positives (false warnings). The paper describes an implementation, Java PathExplorer, for analyzing Java programs. An application of the implementation to two case studies is described