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

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

threadID 获取锁 lock 2 前持有的锁集.图 1(b)为表 1 运行轨迹对应的扩展锁图,它由 2 个子图构成.
得到分段图和扩展锁图后,文献[17]按照如下规则识别死锁:(1) 扩展锁图中两个锁的获取操作构成一条有
向环;(2) 两个操作分属于的不同的线程;(3) 分段图中,这两个操作所在的段不存在有向路径相连(若存在有向
路径则说明这两个操作存在执行次序上的先后依赖关系,无法并发,也就不构成死锁);(4) 这两个操作执行时所
持有的锁集互不相交.
Table 2 A running trace of Program 1
表 2 Program 1 的一条运行轨迹
操作序号 ID 主线程 threadA threadB threadC
1 03:start(Main,threadA)
2 09:acq(threadA,G)
3 11:start(threadA,threadB)
4 14:acq(threadA,o1)
5 15:acq(threadA,o2)
6 15:rel(threadA,o2)
7 16:rel(threadA,o1)
8 17:rel(threadA,G)
9 09:acq(threadA,G)
10 14:acq(threadA,o1)
11 15:acq(threadA,o2)
12 15:rel(threadA,o2)
13 16:rel(threadA,o1)
14 17:rel(threadA,G)
15 21:acq(threadB,G)
16 21:rel(threadB,G)
17 22:acq(threadB,o2)
18 23:acq(threadB,o1)
19 23:rel(threadB,o1)
20 24:rel(threadB,o2)
21 25:acq(threadB,m)
22 26:acq(threadB,n)
23 26:rel(threadB,n)
24 27:acq(threadB,q)
25 28:acq(threadB,p)
26 28:rel(threadB,p)
27 29:rel(threadB,q)
28 30:rel(threadB,m)
29 19:stop(threadA)
30 31:stop(threadB)
31 04:start(Main,threadC)
32 33:acq(threadC,n)
33 34:acq(threadC,m)
34 34:rel(threadC,m)
35 35:acq(threadC,p)
36 36:acq(threadC,q)
37 36:rel(threadC,q)
38 37:rel(threadC,p)
39 38:rel(threadC,n)
40 39:stop(threadB)
41 05:join(Main,threadA)
42 06:stop(Main)
按上述规则,图 1(b)中 ID 为 2,7 的两条有向弧对应的操作会被认为导致死锁.因为两者在扩展锁图中形成
环路,分属不同的线程,所在的 5 号段和 6 号段不存在有向路径相连,两者持有的锁集{G,o1}与{o2}不相交.此外,
ID 为 5 的有向弧与 ID 为 2 的两条有向弧是同一个锁获取语句在两个不同轮次循环中的具体执行,扩展锁图无
法对其区分,两者的标记信息完全一样,从而也会认为导致一个死锁.而实际上,如第 1.1 节所述,其中一个是真实
死锁,另一个是死锁的误报.最后,图 1(b)中 ID 为 11,15 的两条有向弧对应的操作也符合前述 4 条规则,从而也会
被判定导致死锁.但如上节所述,这个死锁也是误报.
上述第 1 个误报的产生根源是:threadA 在持有锁 G 之后方才启动线程 threadB,从而导致图 1 中 2,7 两条弧
对应的操作间具有因果关系(仅当弧 2 对应的操作执行完并释放锁 G 后,弧 7 对应的操作方能执行),而这种因果
关系在分段图中未能刻画(5 号段和 6 号段间不存在有向路径).为处理这一问题,本文稍后将定义一种“锁-start”
耦合因果依赖关系.
第 2 个误报产生的根源是:threadB 获取锁 p 必须先获取 n,而锁 n 的释放导致了 threadB 获取 q 时的持有锁