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

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

第 28 行关于锁 q 和 p 的嵌套获取”与“threadC 在第 35 行和 36 行关于锁 p 和 q 的嵌套获取”不会导致死锁,因
为 threadB 获取 q 和 p 的前提是持有锁 m,而一旦 threadB 先持有了 m,则 threadC 便会被阻塞在第 34 行获取 m
的位置,从而无法嵌套获取 p 和 q;反之,threadC 获取 p 和 q 的前提是持有锁 n,而一旦 threadC 先持有了 n,则
threadB 将被阻塞在第 26 行获取 n 的位置,从而无法嵌套获取 q 和 p.由此可见:虽然 threadB 执行第 28 行获取 p
的操作时持有的锁集为{m,q},threadC 执行第 36 行获取 q 的操作时持有的锁集为{n,p},两个持有锁集互不相交,
但是它们之前曾经持有和随后释放的锁对象 n 和 m 却也形成一组门锁,从而消除了这两个操作并发的可能性,
使得它们不会导致死锁.
Table 1 Pseudo-code of a multithreaded program, denoted by Program 1
表 1 多线程程序 Program 1 的伪代码
ThreadB:
20: poblic void run{
21: synchronized(G){⋅}
Main Thread: 22: synchronized(o2){
01:public static void main(String[⋅] args) throws InterruptedExce{ 23: synchronized(o1){⋅}
02: flag=0; 24: }
03: new threadA.start(⋅); 25: synchronized(m){
04: new theradC.start(⋅); 26: synchronized(n){⋅}
05: threadA.join(⋅); 27: synchronized(q){
06:} 28: synchronized(p){⋅}
29: }
30: }
31: }
ThreadA:
07: poblic void run{
08: for (int i=0; i<2; i++){ ThreadC:
09: synchronized(G){ 32: poblic void run{
10: if (flag==0){
11: new threadB.start(⋅); 33: synchronized(n){
12: flag=1; 34: synchronized(m){⋅}
35: synchronized(p){
13: }
14: synchronized(o1){ 36: synchronized(q){⋅}
15: synchronized(o2){⋅} 37: }
16: } 38: }
39: }
17: }
18: }
19: }

1.2 动机分析
如上节所述,Program 1 存在 4 处锁对象嵌套获取构成的循环依赖环路,但只有两处对应真实死锁,另两处不
是死锁.然而,传统的动态死锁分析方法无法区分上述情况,由此导致死锁误报.
具体来说,假设 Program 1 某次运行轨迹见表 2.其中,start(u,v)代表线程 u 启动线程 v 的操作,stop(u)代表线
程 u 的终止操作,join(u,v)代表线程 u 同步等待直至线程 v 终止,acq(t,l)表示线程 t 获取锁 l 的操作,rel(t,l)代表线
程 t 释放锁 l 的操作.下面以基于分段图和扩展锁图的死锁检测方法为例,说明传统动态分析方法的检测结果.
文献[17]基于 start 和 join 将源程序的操作分为很多段,并根据各个段在执行顺序上的先后依赖关系构造分
段图.具体来说,最初仅为主线程添加一个初始段;之后,每当执行操作 start(u,v)时,在线程 u 此操作之处添加一个
新段,为线程 v 添加一个初始段,并在线程 u 的上一个段与这两个新段之间各添加一条有向弧;每当执行操作
join(u,v)时,为线程 u 添加一个新段,在 u 的上一个段与此段间添加一条有向弧,并在线程 v 的线程终止段与此段
间也添加一条有向弧(该有向弧的添加需要待线程 v 执行终止操作时方能添加).对于表 1 的运行轨迹,构造所得
的分段图如图 1(a)所示.
除构造分段图外,文献[17]为锁图每条有向弧〈lock 1 ,lock 2 〉扩充标记信息 arcID:〈seg 1 ID,(threadID,lockSet),
seg 2 ID〉,提出了扩展锁图的概念.其中,arcID 表示弧的唯一 ID,threadID 表示当前锁申请操作所属线程的 ID,
seg1ID 代表 threadID 获取锁 lock 1 所在的段号,seg 2 ID 代表 threadID 获取锁 lock 2 时所在的段号,lockSet 代表