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

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

(b) 每当有线程 u 执行操作 acq(u,l)时,假设该操作当前所在的段为 currentSeg,该操作的序号 ID 为
(k)
k,则令ϕ s (currentSeg):=ϕ s (currentSeg)Dl (其中,D表示字符串的拼接函数);
(c) 每当有线程 v 执行操作 rel(u,l)时,假设该操作当前所在的段为 currentSeg,该操作的序号 ID 为 k,
(k)
则令ϕ s (currentSeg):=ϕ s (currentSeg)Dl .
以表 1 中的程序运行轨迹为例,按照上述定义得到的锁增广分段图如图 2 所示.
+
显然,锁增广分段图中的每个段对应一个线程的若干操作.若图中的两个段 s 1 和 s 2 满足 (, )s s ∈ SegR (其
σ
1
2
中, 表示关系的闭包运算),则仅当 s 1 中的操作全部执行完毕后方能执行 s 2 中的操作,记此种关系为 s 1 s 2 .
+
图 2 中,2 6 与 5 6 成立,意味着仅当 2 号段与 5 号段中操作执行完毕后方能执行 6 号段中的操作;6 7 与
7 6 均不成立,这意味着,6 号段与 7 号段之间的操作不存在执行次序上的先后依赖关系,此时认为这两组操作可
以并发.
2.3 时序增广锁图
本节在扩展锁图的基础上添加语句的执行时序信息,以区分循环中不同轮次的锁获取操作;同时,在图中标
注每个操作在运行轨迹中的操作序号 ID(据此定位操作在分段图中的位置),由此提出时序增广锁图的概念.
以表 2 中的程序运行轨迹为例,拟构造的时序增广锁图如图 3 所示.其中,2 号弧的标记信息由扩展锁图图
(5)
1(b)中的〈5,(threadA,{G,o1}),5〉扩充为了〈5,(threadA,{G,o1}),1,5〉 ,扩充图中的数字 1 表示本次操作是线程
threadA 第 1 次申请锁 o2,标记右上角数字 5 为该弧所对应操作在执行轨迹上的操作序号 ID.5 号弧的标记信息
变为了〈7,(threadA,{G,o1}),2,7〉 (11) .在扩展锁图中标记相同、无法区分的 2 号弧和 5 号弧,在图 3 的时序增广锁
图中有了不同的标记.

1:〈2,(threadA,{G}),1,5〉 (4) 3:〈2,(threadA,{G,o1}),1,5〉 (5)
8:〈6,(threadB,{m}),1,6〉 (22)
G
n m
12:〈4,(threadC,{n}),1,4〉 (33)
6:〈7,(threadA,{G,o1}),2,7〉 (11) 13:〈4,(threadC,{n}),1,4〉 (35)
4:〈7,(threadA,{G}),2,7〉 (10) 10:〈6,(threadB,{m,q}),1,6〉 (25)

p 9:〈6,(threadB,{n}),1,6〉 (24)
(5)
o1 2:〈5,(threadA,{G,o1}),1,5〉 o2
15:〈4,(threadC,{n,p}),1,4〉 (36)
5:〈7,(threadA,{G,o1}),2,7〉 (11)
11:〈6,(threadB,{m,q}),1,6〉 (25)
q
7:〈6,(threadB,{o2}),1,6〉 (18)
14:〈4,(threadC,{n,p}),1,4〉 (36)
Fig.3 Time-augmented lock graph corresponding to the running trace in Table 2
图 3 表 2 运行轨迹对应的时序增广锁图

经上述处理后,一方面可以保证同一个锁授权语句在循环中的多次执行能区分开来;另一方面,可根据各条
弧所对应操作在运行轨迹中的序号 ID 确定其在锁增广分段图中的位置,从而为后续死锁检测提供方便.下面给
出时序增广锁图的形式化定义与构造规则.
定义 4(时序增广锁图). 给定一个多线程程序的运行轨迹σ=e 1 e 2 e 3 ...e n ,其对应的时序增广锁图 LockG_
Order σ 是满足如下条件的二元组(V σ ,R σ ).
(1) V σ 为顶点集,每个顶点对应σ中出现的一个锁对象;
(2) R σ ⊆V σ ×Γ×V σ 为关系集,Γ是图中各关系所对应之有向弧的标签集合;
(3) 每当σ中有一个线程 t 在持有锁 lock 1 的前提下获取锁 lock 2 时,假设该操作的序号 ID 为 k,则为此操作