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

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

30. IF (DependG_Lock c 不存在有向环)
31. 将 c 加入集合 DeadlockCycles(LockG_Order σ ); //得到一个潜在死锁
32. } //IF
33. } //IF
34. } //IF
35. } //IF
36. } //FOR EACH
37. RETURN DeadlockCycles(LockG_Order σ ).
相比传统方法基于分段图和扩展锁图进行的死锁检测,算法 1 的规则(3)基于锁增广分段图进行的段间因
果依赖的判定更加准确,第 5 条规则能排除“历史持有锁-持有锁”耦合因果依赖关系导致的误报.如此一来,对于
图 3 中 4 组有向弧对{2,7},{5,7},{8,12},{11,15}构成的有向环路,算法 1 能准确地识别出其中{5,7}和{8,12}对应
的环路会导致死锁,而{2,7}和{11,15}对应的环路不会导致死锁,从而避免了它们给传统方法带来的死锁误报.

4 相关工作对比与实验评估

4.1 相关工作对比

基于锁图、环锁依赖链、分段图与分段锁图以及本文方法对表 2 中的程序运行轨迹进行分析,所得死锁检
测结果见表 3.除本文方法之外,其余 3 类方法会将锁图中的每条环路都认定为一个死锁.第 1 行对应的死锁误
报,是因为它们无法识别“锁-start”耦合因果依赖关系;第 4 行对应的死锁误报,是因为它们未处理“历史持有锁-
持有锁”耦合因果依赖关系.而实际上,这两类关系都可能导致环路中的某些操作无法并发.本文方法通过对传
统锁图和分段图的改进弥补了上述不足,并借助锁增广分段图和“历史持有锁-持有锁”耦合因果关系图对上述
情形进行了识别,从而能避免了传统方法中存在的上述死锁误报现象.
Table 3 Deadlock detection results of different methods towards dynamic analysis of the trace in Table 1
表 3 不同方法对表 1 运行轨迹进行动态分析所得之死锁检测结果
是否 不同模型的死锁检测结果
锁对象的循环等待
(对应潜在死锁状态) 时序增广锁图中对应的操作与弧 真实 锁图 环锁 分段图与 本文
死锁 依赖链 分段锁图 方法
threadA 第 1 次执行第 14 行代码 acq(o2)@2:〈5,(threadA,{G,o1}),1,5〉 (5) 否 是 是 是 否
threadB 执行第 22 行代码 acq(o1)@7:〈6,(threadB,{o2}),1,6〉 (18)
threadA 第 2 次执行第 14 行代码 acq(o2)@5:〈7,(threadA,{G,o1}),2,7〉 (11) 是 是 是 是 是
threadB 执行第 22 行代码 acq(o1)@7:〈6,(threadB,{o2}),1,6〉 (18)
threadB 执行第 25 行代码 acq(n)@8:〈6,(threadB,{m}),1,6〉 (22)
threadC 执行第 33 行代码 acq(m)@12:〈4,(threadC,{n}),1,4〉 (33) 是 是 是 是 是
threadB 执行第 27 行代码 acq(p)@11:〈6,(threadB,{m,q}),1,6〉 (25)
threadC 执行第 35 行代码 acq(q)@15:〈4,(threadC,{n,p}),1,4〉 (36) 否 是 是 是 否

需要进一步指出的是:动态分析方法从程序运行轨迹中捕获的程序行为信息始终有限,丢失的信息既可能
导致检测出的潜在死锁不是真实死锁,还可能导致原本不存在死锁的程序被误定为存在死锁.针对这种情况,在
死锁分析领域,除上述提到的死锁检测方法外,有学者开始研究潜在死锁的重演.所谓死锁重演,就是针对检测
到的潜在死锁,通过对程序执行的主动干预和调度,使潜在死锁在为真实死锁的情况下会被尽可能地触发,重演
成功的潜在死锁必是真实死锁.例如,对本文提出的“历史持有锁-持有锁”耦合因果依赖导致的死锁误报,文献
[21]中曾有一个程序实例.但文献[21]中采用的死锁检测算法 ConLock+并不能排除该误报,文中是通过死锁重
演来排除这一误报的.相比而言,本文提出的死锁检测算法无需重演,在检测阶段即可将该误报排除.不过,即便
如此,由于程序轨迹中不可避免地会丢失一些程序行为信息,即使本文方法也存在某些类似的误报现象,所以死
锁的重演也是本文后续研究的重点方向之一.
在死锁重演方面,文献[20,22]首次提出一种面向缺陷重演的随机调度方法,通过不同调度方案下程序的大