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

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

导致的误报.类似地,文献[18]定义了一类时间戳和向量时钟来刻画线程之间由于 start 和 join 语句所引起的操
作上的因果关系,并进而与环锁依赖链相结合,提出了一种基于向量时钟和环锁依赖链的死锁检测新方法,也可
以排除单线程环、门锁环和多线程间具有因果关系的段锁授权操作环导致的误报.
然而,上述死锁检测方法均存在如下问题.
(1) 通过锁图、锁树、环锁依赖链和扩展锁图等模型刻画锁授权顺序时,对同一个锁授权语句的多次执
行不加区分.而实际当中,位于一个循环中的同一个锁获取语句,可能在某些轮次的循环中引起死锁,
而另一些轮次中不会引起死锁,后面这类情况会引起死锁的误报;
(2) 分段图被用来确定构成环路的锁获取操作之间是否具有因果依赖,但分段图仅刻画了同一线程内操
作间的因果依赖以及由于线程的 start,join 操作导致的线程间因果依赖关系,而实际上,锁对象的释放
和获取在与线程的 start 操作耦合时也可能导致不同线程操作上的因果依赖;
(3) 传统锁图等工具仅记录了锁申请操作执行时正持有的锁集,并据此排除门锁环导致的误报.然而,除
了持有锁集中的锁对象外,线程在获取上述锁的过程中可能存在某些其他曾经获取而又随后释放锁
的操作,它们也可能导致死锁的误报.
文献[21]曾指出过上述第 3 类误报,但他们是通过死锁重演来排除这一误报,其给出的死锁检测方法并不能
排除该误报.
为解决上述问题,本文一方面在扩展锁图的基础上添加语句的执行时序信息以区分循环中不同轮次的锁
获取操作,据此提出时序增广锁图的概念;另一方面,在分段图的基础上扩充锁的获取和释放信息,对段进行更
细粒度地划分,以更为准确地刻画操作上的因果依赖关系,据此提出了锁增广分段图的概念;最终,综合这两个
工具提出一种新的死锁检测方法,它不仅可以消除单线程环、门锁环、多线程间由于线程的 start 和 join 操作
而引起的因果关系导致的死锁误报,还能消除由于锁对象的释放和获取与线程 start 操作耦合引起的因果关系
导致的死锁误报,而且能排除历史持有锁导致的误报,由此减少死锁误报,提高死锁检测的准确率.

1 实例与动机分析

1.1 程序实例

表 1 给出了一个多线程程序的实例 Program 1.它包含 4 个线程(主线程、threadA、threadB、threadC)和 7
个锁对象(G,o1,o2,m,n,p,q).threadA 中包含一个循环语句块,循环体中的锁授权语句会被多次执行.某些轮次的
锁授权操作会引起死锁,而另一些轮次则不会导致死锁.此外,threadB 和 threadC 中关于锁对象 m,n 的嵌套获取
会导致一个死锁,而关于 p,q 的嵌套获取由于曾经持有的锁构成门锁而不会导致死锁.
具体而言,主线程依次启动 threadA 和 threadC,之后阻塞直到 threadA 执行结束.threadA 启动后执行两轮循
环,每一轮循环都是先获取锁 G;之后,在持有锁 G 的前提下,依次执行获取锁 o1、释放锁 o1、获取锁 o2、释放
锁 o2 的操作;最后释放锁 G.两轮循环的不同之处在于:第 1 轮循环时(flag=0 时),threadA 会创建并启动 threadB;
而第 2 轮循环时(flag=1 时)无此操作.threadB 被启动后,先执行获取锁 G 和释放锁 G 的操作,之后顺序执行获取
o2、获取 o1、释放 o1 和释放 o2 的操作.不难发现,“threadA 第 1 轮循环中关于锁 o1 和 o2 的嵌套获取”与“threadB
中关于锁 o2 和 o1 的嵌套获取”不会导致死锁.因为 threadA 第 1 轮循环中始终持有锁对象 G,而 threadB 中各个
操作会因无法获取锁 G 而阻塞,仅当 threadA 释放锁 G 后,threadB 才能执行后续操作.换言之,锁 G 的释放和获
取在上述两个操作之间构成一种因果依赖关系,使得两者无法并发,从而不导致死锁.相反地,threadA 第 2 轮循
环的执行过程中,若是 threadB 先获取锁 G 并释放,之后在持有锁 o2 的同时申请锁 o1,而此时,threadA 在持有锁
G 和 o1 的同时申请 o2,则此时会触发死锁.
此外,threadB 除上述操作外,还将依次执行获取锁 m、获取锁 n、释放锁 n 的操作,并在持有锁 m 的情况下
执行获取 q、获取 p、释放 p、释放 q 的操作,最后再释放锁 m.threadC 被主线程启动后,先依次获取 n、获取 m、
释放 m,之后在持有锁 n 的前提下依次获取 p、获取 q、释放 q、释放 p,最后再释放锁 n.不难发现:threadB和 threadC
中关于锁对象 m,n 的嵌套获取构成一个锁对象的持有等待回路,对应一个真实死锁.然而,“threadB 在第 27 行和