中文摘要：

死锁难以暴露、重演和调试．一旦发生，将导致多线程程序响应时间增长、吞吐量下降甚至宕机崩溃．现有死锁检测技术每次只能检测一个互斥锁死锁．为一次性检测由多个线程和多个互斥锁或读写锁造成的所有类型死锁，首先提出混合锁分配图的概念和构建方法，然后提出一种利用混合锁分配图动态检测混合死锁的方法．通过劫持所有互斥锁和读写锁的加锁解锁操作，以动态构建和实时更新一个反映目标程序同步状态的混合锁分配图．通过在锁分配图上检测环并判定该环是否为死锁环来检测死锁．当检测到死锁时，输出死锁信息来辅助调试．死锁检测实验、性能影响实验和可扩展性实验结果表明：该方法成功检测出所有13个共5种类型的死锁缺陷，检测能力强；给openldap-2．2．20带来至多10．15％的性能下降幅度，对目标程序造成的性能影响较小；性能开销随线程数目指数级增大而平缓增长，扩展性良好．

英文摘要：

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 MAI.G 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.