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

1696 Journal of Software 软件学报 Vol.32, No.6, June 2021

量运行,来尽量触发死锁等并发缺陷.该方法面向缺陷重演的调度是盲目的、完全随机的,考虑到死锁通常是低
概率事件,这导致该方法在效率和可靠性方面的不足.相比而言,文献[14,18,21,23−25]先进行潜在死锁的检测,
之后有针对性地设计程序调度方案,以此提高真实死锁重演成功的概率.具体地说,文献[14,18,23]面向潜在死锁
提出一种启发式调度策略,在线程到达潜在的死锁点时挂起线程,以此增加死锁触发的概率.不过,这种方法本
质上仍是随机的,真实死锁通常需多次运行才能重演成功,而且它们不能提供系统的、完整的覆盖.考虑到死锁
的触发应同时考虑死锁的发生位置和该位置之前一些相关的锁授权操作,文献[24]提出一种基于屏障的死锁重
演调度算法 ASN,将程序调度的干预时机进行了优化.类似地,文献[21,25]针对潜在死锁生成一组程序调度的约
束集,当程序的运行不符合生成的约束时,挂起线程的执行.上述方法提高了真实死锁重演成功的概率,不过,其
面向死锁重演生成的程序调度方案不够直观,而且同前述潜在死锁的检测方法一样,均对同一个锁授权语句的
多次执行不加区分,这也为死锁重演带来了困难.
本文所提出的死锁检测工具,一方面能对循环中同一个锁授权语句的多次执行加以区分;另一方面,锁增广
分段图中既对不同线程中的各个操作根据执行顺序上的依赖关系进行了刻画,还完整记录了锁的获取和释放
操作.基于它们,有望为死锁的重演生成一种更为直观可行的重演方案,篇幅所限,具体方法将在以后展开.
4.2 原型系统与实验评估

4.2.1 原型系统
作者基于开源的 Java 多线程程序主动调试平台 CalFuzzer [26] 开发了相应的死锁检测工具.基于该工具,用户
只需要输入一个多线程程序,通过分析 CalFuzzer 产生的程序运行事件流,工具便能自动生成相应的时序增广锁
图和锁增广分段图,并给出死锁检测的结果.所开发工具的架构和运行界面如图 5、图 6 所示.
原型系统架构分为 3 层:最底层为用户输入层,需要用户输入一个多线程程序,然后运用 Calfuzzer 挖掘出程
序的运行轨迹;中间层为处理层,处理层接收到运行轨迹,进行模型挖掘,构建时序增广锁图和锁增广分段图,并
基于算法 1 的检测规则识别潜在死锁;界面层向用户展示挖掘得到的锁增广分段图、时序增广锁图,在显示模
型的同时给出死锁检测的结果(如图 5 所示).
工具运行界面截图中,位于左侧的是锁增广分段图,在锁增广分段图中,同一颜色的段号代表属于同一个线
程,其中段中所记录的锁获取释放信息可设置为对隐藏或显示;位于右上的是时序增广锁图;位于右下的是用本
文方法检测到的潜在死锁信息.图中给出的是对论文中程序实例 Program 1 的死锁检测结果(如图 6 所示).

界面层 死锁检测结果 时序增广锁图 锁增广分段图

处理层 死锁检测 模型挖掘
锁图存在有向环路
操作分属不同线程
时序增广锁图
无线程间因果依赖
无“锁-start”耦合因果依赖
锁增广分段图
持有锁集不相交
因果关系图无环路
输入层 Java多线程程序 Calfuzzer 程序运行轨迹

Fig.5 Architecture of the deadlock detection prototype system
图 5 死锁检测原型系统架构