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

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

• stop(v):线程执行终止;
• join(u,v):线程等待线程执行终止;
• acq(u,l):线程锁对象;
• rel(u,l):线程释放获取锁对象.
表 2 给出的就是 Program 1 的一个程序运行轨迹.
2.2 锁增广分段图
本节在传统分段图的基础上扩充锁的申请和释放信息,并根据“锁-start”耦合因果依赖关系对段的划分进
行细化,由此提出了锁增广分段图的概念.以表 2 中的程序运行轨迹为例,拟构造的锁增广分段图如图 2 所示.

Main
0 threadA.start(⋅)

threadA.start(⋅) threadA
2
1 threadC (G ) threadB.start(⋅) threadB
(2)
threadC.start(⋅) threadB.start(⋅)
threadC.start(⋅)
4 5 rel(threadA,G) 6
3 (32) (33) (34) (35) (4) (5) (15) (16) (17)
(n ,m ,m ,p , (o1 ,o2 , (G ,G ,o2 ,
(8)
(6)
(7)
q (36) ,q (37) ,p (38) ,n (39) ) o2 ,o1 ,G ) o1 (18) ,o1 (19) ,o2 (20) ,
m (21) ,n (22) ,n (23) ,q (24) ,
threadA.join(⋅) rel(threadA,G) p (25) ,p (26) ,q (27) ,m (28) )
7
(G (11) ,o1 (12) ,o2 (13) ,
o2 (14) ,o1 (15) ,G (16) )
8 threadA.join(⋅)

Fig.2 Lock-augmented segmentation graph corresponding to the running trace in Table 2
图 2 表 2 运行轨迹对应的锁增广分段图
在锁增广分段图中,每个段除含有段号信息外,增加了此段中所执行的锁授权和释放操作的信息.以 4 号段
为例,它依次执行了获取锁 n、获取 m、释放 m、获取 p、获取 q、释放 q、释放 p、释放 n 的操作,这一过程通
过标记(n (32) ,m (33) ,m (34) ,p (35) ,q (36) ,q (37) ,p (38) ,n (39) )刻画(标记中,各个锁对象右上角括号中的序号是本次操作在运行
轨迹中的操作序号 ID,锁对象底部加下划线表示锁的释放操作,不加下划线时表示锁的获取操作).
此外,由于线程 threadA 在 2 号段获取了锁 G 而未释放,“threadB 在 6 号段开始处获取锁 G 的操作”只有待
“threadA 于 5 号段释放锁 G 的操作”结束后方能执行,两者间构成一种因果关系.为了刻画这种关系,锁增广分段
图中,将传统分段图中的 5 号段以锁 G 的释放操为分割点一分为二,并在新的 5 号段与 6 号段之间添加一条有
向弧,据此刻画“锁-start”耦合导致的依赖关系.
对这种“锁-start”耦合因果依赖关系,锁增广分段图构造过程中的识别规则及对应的段/弧添加规则如下.
(1) 每当有一个线程 t 在段 s 中执行一次锁 l 的释放操作,检查 t 此前获取 l 的操作是否在同一个段 s 中:
若不是,则在此处为线程 t 添加一个新段(例如,图 2 中 5 号段末尾锁 G 的释放导致了 7 号段以及 5 号
段到 7 号段之间有向弧的添加);
(2) 每当有一个线程 t′在段 s′中执行一次锁 l 的获取操作,从该段节点逆向寻找第一个获取锁 l 的段节点
s″,若 s″不属于线程 t′且 s″中未释放 l(例如,图 2 中线程 threadB 获取锁 G 时,s″为 6,s′为 2),则:
(2.1) 将 s′从当前 l 的获取操作处开始一个新的分段,记段号为 s′_new(图 2 中 G 的获取操作位于 6 号