Detection of deadlock potentials in multithreaded programs

Concurrent programs are well known for containing errors that are difficult to detect, reproduce, and diagnose. Deadlock is a common concurrency error, which occurs when a set of threads are blocked, due to each attempting to acquire a lock held by another. This paper presents a collection of highly scalable static and dynamic techniques for exposing potential deadlocks. The basis is a known algorithm, which, when locks are acquired in a nested fashion, captures the nesting order in a lock graph. A cycle in the graph indicates a deadlock potential. We propose three extensions to this basic algorithm to eliminate, or label as low severity, false warnings of possible deadlocks (false positives). These false positives may be due to cycles within one thread, cycles guarded by a gate lock (an enclosing lock that prevents deadlocks), and cycles involving several code fragments that cannot possibly execute in parallel. We also present a technique that combines information from multiple runs of the program into a single lock graph, to find deadlock potentials that would not be revealed by analyzing one run at a time. Finally, this paper describes the use of static analysis to automatically reduce the overhead of dynamic checking for deadlock potentials.