Abstract: Deadlock bugs are hard to expose, reproduce and diagnose. Once happening, they will cause increasing response time, decreasing throughput, or even crash to the target multithreaded programs. However, current deadlock detection techniques can detect only one mutex-caused deadlock at a time. In order to detect all possible deadlocks one time caused by multiple threads and multiple mutexes or rwlocks, this paper proposes the concept of multiple-type lock allocation graph (MLAG) and its construction method. Then a MLAG-based dynamic detection algorithm to detect multiple types of deadlocks is proposed. By instrumenting all lockunlock operations on mutexes and rwlocks, our method dynamically constructs and real-time updates a MLAG which reflects the synchronization state of the target program. Our method detects deadlock bugs by detecting cycles on the MALG and checking whether or not a cycle is a deadlock cycle. When a deadlock is detected, the method outputs information about that bug to assist debugging. The experimental results on benchmarks show that our method is strong in deadlock detection for successfully detecting all 13 deadlock bugs with 5 types, and has a slight impact on target programs for incurring at most 10.15% slowdown to openldap-2.2.20’s performance, and is scalable because the overhead increase gently along with an exponentially increasing number of threads.

Key words: dynamic analysis, software testing, concurrency bug detection, deadlock detection, cycle detection