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

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

显然,lockSet_OnceHeld 11 ∩lockSet 15 ={n},lockSet_OnceHeld 15 ∩lockSet 11 ={m}.欲使弧 11 和弧 15 对应的操作
能够并发以触发死锁,则这两个交集中的锁对象获取操作应满足“历史持有锁-持有锁”耦合因果依赖.为此,定义
一种“历史持有锁-持有锁”耦合因果关系图,据此判定这种关系的可满足性:
定义 5(“历史持有锁-持有锁”耦合因果关系图). 设 c=e k_1 e k_2 ...e k_l 构成时序增广锁图中的一条有向环路,其
中每个 e k_i 是一条弧对应的锁申请操作.称满足如下条件的二元组 DependG_Lock c =(V c ,R c )为 c 对应的“历史持有
锁-持有锁”耦合因果关系图,其中,V C 为顶点集,每个顶点对应一个锁获取操作;点 R c ⊆V c ×V c 为有向边的集合,每
条有向边用以刻画两个弧顶点所对应操作之间的因果依赖关系.V C 与 R C 的产生规则如下.
(1) 只要存在锁对象 o 与操作 e k_i =acq(u,o),e k_j =acq(v,o)满足 o∈lockSet_OnceHeld(e k_i )∩lockSet(e k_j )且
u≠v,记线程 u 获取历史持有锁 o 的各个操作构成的集合为 E_OnceHeld(e k_i ,o),线程 v 最后一次获取持
有锁 o 的操作为 e′ k _ j ,则:
(1.1) 对应线程 v 最后一次获取持有锁 o 的操作 e′ ,向 V C 中添加一个 ID 为(v,o )的操作,其中,y 为
(y)
k _ j
操作 e′ 在程序运行轨迹中的序号 ID;
k _ j
(1.2) 对应线程 u 每一个获取历史持有锁 o 的操作 e′ ∈ E _OnceHeld (e , )o ,向 V C 中添加一个 ID 为
_
_
ki ki
(u,o )的操作,其中,x 为操作 e′ 在程序运行轨迹中的序号 ID;与此同时,向 Rc 中添加一条由顶
(x)
ki
_
(x)
(y)
点(u,o )指向顶点(v,o )的有向边;
(j)
(i)
(i)
(j)
(2) 对 Vc 中任意两顶点(u,p )与(v,q ),若 u=v∧i<j,则向 Rc 中添加一条由顶点(u,p )指向顶点(v,q )的有
向边.
不难发现:定义 5 中的规则(1.2)添加的有向边用以刻画第 1 节给出的“历史持有锁-持有锁”耦合因果依赖关
系,规则(2)添加的有向边用以刻画第 1 节给出的线程内因果依赖关系.若要使得环路 c 对应一个真实死锁,则这
些关系应该同时得到满足.而这些因果同时得到满足的一个必要条件就是“历史持有锁-持有锁”耦合因果关系
图中不存在有向环,因此,对于时序增广锁图中的任意一条有向环路 c 而言,若其对应的“历史持有锁-持有锁”耦
合因果关系图中存在有向环,则 c 对应的潜在死锁是一个误报.
以图 3 时序增广锁图中有向弧 11 与 15 构成的有向环路为例,它们对应的操作分别为 e 26 =28:acq(threadB,p)
和 e 36 =36:acq(threadC,q).不难发现,lockSet_OnceHeld(e 26 )={m,n,q},lockSet(e 36 )={n,p}.显然,threadB 与 theadC 是
两个不同的线程,且存在锁对象 n∈lockSet_OnceHeld(e 26 )∩lockSet(e 36 ),规则(1)的条件满足;接下来,根据规则
(1.1),应向 DependG_POrder c 中添加 ID 为(threadC,n (32) )的顶点,它对应 threadC 最后一次获取持有锁 n 的操作;
根据规则(1.2),向 DependG_POrder c 中添加 ID 为(threadB,n (22) )的顶点,它对应 threadB 获取历史持有锁 n 的操
作 ; 再 根据规则 (1.2) 添加一 条由 (threadB,n (22) ) 指向 (threadC,n (32) ) 的有向 边 . 类似 可见 ,m∈lockSet_
OnceHeld(e 26 )∩lockSet(e 36 ),根据规则(1),应向 DependG_Lock c 添加顶点(threadC,m (33) ),(threadB,m (21) )以及两者
之间的一条有向边.再根据规则(2),应根据线程内因果关系添加由(threadB,m (21) )指向(threadB,n (22) )以及由
(threadC,n (32) )指向(threadC,m (33) )的两条有向边,最终可得图 4 中的“历史持有锁-持有锁”耦合因果关系图.

(threadB,m (21) ) 历史持有锁-持有锁 (threadC,m (33) )
耦合因果关系
线 线
程 程
内 内
因 因
果 果
关 关
系 系
(threadB,n (22) ) 历史持有锁-持有锁 (threadC,n (32) )
耦合因果关系

Fig.4 Partial order dependency graph of deadlock detection corresponding to loops {11,15} in Fig.3
图 4 弧{11,15}构成之有向环路对应的“历史持有锁-持有锁”耦合因果关系图
显然,图 4 所示“历史持有锁-持有锁”耦合因果关系图存在有向环,这意味着图中各操作之间的线程内因果