使用锁分配图动态检测混合死锁

禹 振 苏小红 邱 景

(哈尔滨工业大学计算机科学与技术学院 哈尔滨 150001)



使用锁分配图动态检测混合死锁

禹 振 苏小红 邱 景

(哈尔滨工业大学计算机科学与技术学院 哈尔滨 150001)

(yuzhen_3301@aliyun.com)

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

动态分析；软件测试；并发缺陷检测；死锁检测；环检测

多线程程序中，一个线程集合中的每一个线程都在各自等待另一个线程占据的互斥性资源，由此导致的循环等待即为死锁.在所有并发缺陷中[1]，死锁是其中最常见和最重要的一种：多方统计调查显示[2-4]，死锁缺……