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

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

境中,CPU 为 Intel(R) Core(TM)i5-6300HQ CPU@2.30GHz,内存为 8.00GB,操作系统为 Ubuntu 18.10.
就死锁检测的准确性而言,iGoodlock 仅消除了单线程环和门锁环导致的误报,而本文方法进一步消除了线
程间因果依赖关系、“锁-start”耦合因果依赖关系以及“历史持有锁-持有锁”耦合因果关系导致的误报.就死锁
检测的时间性能而言,当程序中存在潜在死锁时,本文方法的时间性能要优于 iGoodlock.一个主要原因是:本文
基于文献[28]所提出的图矩阵化方法计算锁增广分段图中的环路,其时间复杂度是多项式级的,而 iGoodlock 基
于图的遍历完成环路检测,其时间复杂度是指数级的.当程序中不存在潜在死锁时,矩阵化方法检测环路与遍历
法检测环路的时间开销接近,此时,因本文需要构造的锁增广分段图和时序增广锁图相比 iGoodlock 要构造的环
锁依赖链含有更多的信息,同时,本文方法还需构建“历史持有锁-持有锁”耦合因果图并要判断其中是否包含环
路,故本文方法的时间性能此时会稍差.就空间性能而言,本文方法比 iGoodlock 消耗更多的内存:一方面,本文需
要构建的锁增广分段图和时序增广锁图相比 iGoodlock 构建的环锁依赖链包含了锁的获取和释放以及操作时
序等额外信息,这会占用更多的内存;另一方面,本文检测死锁过程中构造的“历史持有锁-持有锁”耦合因果关
系图也是 iGoodlock 等传统方法中不曾有的,它也会引起更大的内存开销.

5 总结与展望

围绕多线程程序的死锁检测问题,通过对传统动态死锁分析方法所存误报现象的分析,本文对锁图、分段
图等传统的死锁分析模型进行改进:一方面,在扩展锁图的基础上添加语句的执行时序信息来区分同一循环中
不同轮次的锁获取操作,据此提出了时序增广锁图的概念;另一方面,在分段图的基础上扩充锁的获取和释放信
息,并对段进行更细粒度的划分以刻画锁对象的释放和获取操作导致的因果依赖关系,据此提出了锁增广分段
图的概念.最终,在上述两个模型的基础上提出了一种新的死锁检测方法,它不仅可以消除单线程环、门锁环、
多线程间由于线程的 start 和 join 操作而引起的因果关系导致的死锁误报,还能消除由于“锁-start”耦合因果依
赖导致的死锁误报,而且能排除“历史持有锁-持有锁”耦合因果依赖导致的误报,由此减少了死锁的误报,提高了
死锁检测的准确率.然而,本文方法也存在一定不足:一方面,本文仅考虑了线程的 start/stop/join 以及锁对象的释
放和获取等并发原语,而实际上,线程的 wait/notify/notifyAll 等并发原语和其他一些程序的条件控制结构等操作
也会对死锁产生影响,要进行更为准确的死锁检测,需要考虑更多的可能影响死锁的程序原语;另一方面,程序
自动修复也是当前的研究热点之一 [29] ,而如何基于本文的模型开展上述研究值得探究;最后,死锁同样存在于
MPI 并行程序 [30] 、柔性制造系统 [31,32] 、软件定义网络 [33] 等多种领域,如何将本文方法像更多的领域推广也是
后续重点需要研究的工作.

References:
[1] Su XH, Yu Z, Wang TT, Ma PJ. A survey on exposing, detecting and avoiding concurrency bugs. Chinese Journal of Computers,
2015,395(11):93−111 (in Chinese with English abstract). [doi: 10.11897/SP.J.1016.2015.02215]
[2] Zhang J, Zhang C, Xuan JF, Xiong YF, Wang QX, Liang B, Li L, Dou WS, Chen ZB, Chen LQ, Cai Y. Recent progress in program
analysis. Ruan Jian Xue Bao/Journal of Software, 2019,30(1):80−109 (in Chinese with English abstract). http://www.jos.org.cn/
1000-9825/5651.htm [doi: 10.13328/j.cnki.jos.005651]
[3] Lu S, Park S, Seo E, Zhou YY. Learning from mistakes—A comprehensive study on real world concurrency bug characteristics.
Computer Architecture News, 2008,36(1):329−339.
[4] Bensalem S, Griesmayer A, Legay A, Nguyen TH, Peled D. Efficient deadlock detection for concurrent systems. In: Proc. of the
9th ACM/IEEE Int’l Conf. on Formal Methods and Models for Codesign. IEEE Computer Society, 2011. 119−129. https://doi.
org/10.1109/MEMCOD.2011.5970518
[5] Sun J, Liu Y, Dong JS, Liu Y, Shi L, Andre E. Modeling and verifying hierarchical real-time systems using stateful timed CSP.
ACM Trans. on Software Engineering and Methodology, 2013,22(1):1−29. [doi: 10.1145/2430536.2430537]
[6] Artho C, Biere A. Applying static analysis to large-scale, multi-threaded Java programs. In: Proc. of the 13th Australian Conf. on
Software Engineering. IEEE Computer Society, 2001. 68−75.