Page 123 - 《软件学报》2021年第6期

鲁法明 等:基于锁增广分段图的多线程程序死锁检测 1697

Fig.6 Running interface of the prototype system
图 6 原型系统运行界面
4.2.2 实验评估
第 1 节结合多线程程序 Program 1,从原理上说明了本文方法相比 iGoodlock 等经典死锁分析方法的优势.
本节结合表 4 中更多的 Java 多线程程序实例进行实验评估,表中前 8 个样例来自于 CalFuzzer 开源项目中提供
的程序样例;pingpong,cyclicDemo 来自于文献[27];ConLockDemo 为文献[21]设计的程序实例,其中包含本文要
解决的“历史持有锁-持有锁”耦合因果依赖导致的死锁误报,文中通过重演的方法排除误报,检测阶段无法排
除;PetriDeadLockDemo 包含“锁-start”耦合因果依赖关系导致的传统方法的死锁误报,文中通过 Petri 网行为分
析排除误报,效率较低;OnceHeldLockDemo 是在本文 Program 1 基础上添加延时等操作后得到的完整程序实例,
它既包含“锁-start”耦合因果依赖导致的死锁误报,也包含“历史持有锁-持有锁”耦合因果依赖导致的误报.以上
程序实例仅涉及两个线程导致的死锁.为进行更一般化的验证,MulThreadDeadlockDemo 是专门设计的一个多
线程死锁的程序实例,其中包含一个 3 线程导致的真死锁和 4 线程导致的死锁误报.
Table 4 Experimental results of program examples
表 4 程序实例实验结果
潜在死锁数 死锁误报数 时间开销(s) 内存开销(MB)
Java 多线程 Java 多线程程序 iGood- 本文 iGood- 本文 iGood- 本文 iGood- 本文
程序样例 包含的线程总数
lock 方法 lock 方法 lock 方法 lock 方法
Test1a 5 1 1 0 0 0.198 0.157 3.695 5.219
Test1b 3 1 1 0 0 0.129 0.115 3.656 4.842
Test2a 5 0 0 0 0 0.113 0.171 4.020 6.551
Test3 3 1 1 0 0 0.190 0.144 3.621 4.960
Test4 3 1 1 0 0 0.196 0.122 3.641 4.594
Test6 5 0 0 0 0 0.113 0.146 3.785 5.158
Test7 3 1 1 0 0 0.190 0.153 3.523 5.233
Test8 5 4 4 0 0 0.202 0.200 3.566 4.892
pingpong 5 0 0 0 0 0.162 0.156 3.910 4.486
cyclicDemo 5 0 0 0 0 0.130 0.111 4.286 5.009
ConLockDemo 3 4 3 1 0 0.192 0.176 3.884 4.730
PetriDeadLockDemo 3 2 1 1 0 0.135 0.112 3.898 4.812
OnceHeldLockDemo 4 4 2 2 0 2.158 2.118 3.904 4.956
MulThreadDeadlockDemo 4 2 1 1 0 0.726 0.235 3.816 5.026
注:1. PetriDeadLockDemo 来自链接 http://kns.cnki.net/kcms/detail/11.5946.TP.20210421.1820.049.html 的 Program 1;
2. OnceHeldLockDemo 的链接 https://pan.baidu.com/s/14jUjNflAQ1uyk1N-X_NFcw 提取码:og9n;
3. MulThreadDeadlockDemo 的链接 https://pan.baidu.com/s/1-ng2uVOuOlgYwizM_zLy8g 提取码:zquj
具体实验结果见表 4.下面从死锁检测准确性、时间和内存开销这 3 个方面进行实验对比,对比结果优势明
显的项目用加粗显示.对照的死锁检测基准程序为 CalFuzzer 自身集成的死锁动态分析工具 iGoodlock.实验环