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

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

添加一个关系(lock 1 ,γ,lock 2 )∈R σ ,其中的γ形如:
(k)
〈seg 1 ID,(t,lockSet),m,seg 2 ID〉 ,
其中,seg 1 ID 是线程 t 获取锁 lock 1 时所在的段号,seg 2 ID 是线程 t 获取锁对象 lock 2 时所在的段号,
lockSet 是线程 t 获取锁 lock 2 前持有的锁集,m 记录线程 t 的当前操作是其第几次获取锁 lock 2 ;
(4) 是满足上述条件的最小有向图.
以表 2 中的程序运行轨迹为例,按照上述定义得到的时序增广锁图如图 3 所示.
显然,时序增广锁图中任意两点间若存在有向环,则它对应着一组锁对象的循环持有和等待.例如,图 3 中共
有 4 组有向弧对{2,7},{5,7},{8,12},{11,15}构成有向环.传统的基于锁图以及基于分段图和扩展锁图的死锁检
测方法会判定这 4 组有向环均导致死锁.实际上,如第 1 节所述,它们当中只有两个是真实死锁,而另两个是误报.
基于本文提出的时序增广锁图和锁增广分段图可以排除上述误报.下节给出具体方法.

3 基于锁增广分段图与时序增广锁图的死锁检测
传统的基于分段图和扩展锁图的死锁检测方法通过如下规则识别死锁:(1) 锁图中多个锁的申请操作构成

一条有向环;(2) 锁申请操作分属于不同的线程;(3) 记任意两个锁操作所在的段为 s 1 和 s 2 ,则分段图中 s 1 和 s 2
之间不存在有向路相连,意即这些操作在执行顺序的先后上无因果依赖关系;(4) 锁操作执行时的持有锁集不
相交.
第 1 个规则要求多个锁申请操作满足锁对象的环路等待条件,后 3 个规则本意是要保证多个锁申请操作能
够并发.然而,上述识别规则仅在部分情况下是正确的.例如,图 3 右侧子图中{5,7},{8,12}两组有向弧对满足上述
规则,它们对应的操作既构成锁对象的环路等待,又可以并发,故对应两个真实死锁.但是存在某些情况,虽然前
述规则均满足,但它们却不能并发,从而会导致死锁误报,具体如下.
(1) 以图 3 左侧子图中 ID 为 2 和 7 的两条有向弧为例,它们对应的 5 号段与 6 号段虽然在图 1(a)的传统
分段图中不存在有向路径相连,但是如第 1.2 节所述,两者却因为锁对象 G 而存在“锁-start”耦合因果
依赖关系(仅当弧 2 对应的操作执行完并释放锁 G 后,弧 7 对应的操作方能执行).这种因果关系在传
统分段图中得不到体现,但是,如第 2.2 节所述,锁增广分段图通过将 5 号段细分为两个段,并在细分后
的段间添加依赖关系解决了这一问题(图 1 中的 5 号段在图 2 中细分为了段 5 和段 7,而且段 5 和段 6
间添加了一条依赖关系).因此,对这一误报,只要基于锁增广分段图对段间的依赖关系进行更为精准
的判定,便可消除之.例如,在图 2 中,ID 为 2 的有向弧对应的操作属于 5 号段,ID 为 7 的有向弧对应的
操作属于 6 号段,5 6 成立,由此可断定{2,7}不会导致死锁;
(2) 锁申请操作执行时的持有锁集互不相交,但持有锁集与历史持有锁集却可能相交.此时可能存在“历
史持有锁-持有锁”耦合因果依赖关系,这种关系有时会导致操作无法并发.以图 3 中 ID 为 11 和 15 的
弧为例,它们所对应操作的持有锁集分别为{m,q}和{n,p},持有锁集互不相交,看似不存在门锁而可并
发.然而如第 1.1 节所述,这两个操作却因为其持有锁集与历史持有锁集中的公共元素 m 和 n 无法满
足“历史持有锁-持有锁”耦合因果依赖关系而无法并发.
为排除上述死锁误报,除记录操作执行时持有的锁集 lockSet 外,还要计算它们的历史持有锁集 lockSet_
OnceHeld.不难发现,lockSet_OnceHeld 可通过锁增广分段图计算得到:首先,根据操作 ID定位其在锁增广分段图
的位置,假设其对应的段号为 x、在段标签中的序号为 index,并假设该操作属于线程 t;接下来,从中 index−1 位置
开始,按照段内标签从右向左、一个段访问结束后访问线程 t 的上一段这种规则,遍历各段的标签,直至 lockSet
中所有锁都在遍历过程中被获取为止.上述遍历过程中,曾出现过的锁对象的集合即为 lockSet_OnceHeld.以图 3
中 ID 为 11 的弧为例,它属于线程 threadB,对应锁增广分段图中的 6 号段,该操作执行时的持有锁集 lockSet 11 =
{m (21) ,q (24) }.根据前述规则,需访问的标签依次为 q (24) ,n (23) ,n (22) ,m (21) ,由此可得 lockSet_OnceHeld 11 ={q (24) ,n (22) ,
m (21) }.类似地,对图 3 中 ID 为 15 的弧,它对应线程 threadC 段 4 中的一个操作,操作执行时的持有锁集 lockSet 15 =
{n (32) ,p (35) },需访问的标签依次为 p (35) ,m (34) ,m (33) ,n (32) ,由此可得 lockSet_OnceHeld 15 ={p (35) ,m (33) ,n (32) }.