A randomized dynamic program analysis technique for detecting real deadlocks

TitleA randomized dynamic program analysis technique for detecting real deadlocks
Publication TypeConference Proceedings
Year of Conference2009
AuthorsJoshi, P., Park C. - S., Naik M., & Sen K.
Conference NameConference on Programming Language Design and Implementation (PLDI'09)
Series TitleProceedings of the 2009 ACM SIGPLAN conference on Programming language design and implementation
Pagination110 - 120
PublisherACM
Conference LocationDublin, Ireland
ISBN978-1-60558-392-1
Abstract

We present a novel dynamic analysis technique that finds real deadlocks in multi-threaded programs. Our technique runs in two stages. In the first stage, we 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, we control a random thread scheduler to create the potential deadlocks with high probability. Unlike other dynamic analysis techniques, our approach has the advantage that it does not give any false warnings. We have implemented the technique in a prototype tool for Java, and have experimented on a number of large multi-threaded Java programs. We report a number of previously known and unknown real deadlocks that were found in these benchmarks.

DOI10.1145/1542476.1542489
AttachmentSize
deadlock.pdf420.57 KB