A Randomized Dynamic Program Analysis Technique for Detecting Real Deadlocks

Date Added: Jun 2009
Format: PDF

The authors present a novel dynamic analysis technique that finds real deadlocks in multi-threaded programs. Their technique runs in two stages. In the first stage, they use an imprecise dynamic analysis technique to find potential deadlocks in a multi-threaded program by observing an execution of the program. In the second stage, they control a random thread scheduler to create the potential deadlocks with high probability. Unlike other dynamic analysis techniques, their approach has the advantage that it does not give any false warnings. They have implemented the technique in a prototype tool for Java, and have experimented on a number of large multi-threaded Java programs.