为提高软件系统的运行效率, 并行编程技术得到广泛应用.与此同时, 随着软件规模和复杂度的不断扩大, 加之并行程序在程序调度等方面的不确定性, 死锁、数据竞争和原子性违背等并发缺陷日益显现^{[1, 2]}.死锁是最具代表性的并发缺陷之一, 死锁的发生会导致程序无法正常运行甚至是系统崩溃, 由此带来不必要的损失.而且统计显示, 约30%的并发缺陷与死锁有关^[3].因此, 死锁检测成为提高软件可靠性和安全性亟需解决的问题.

文献[1]将近年来的死锁检测方法分为3类: 定理证明与模型检验^{[4, 5]}、数据流分析^[6-10]和动态分析^[11-20].

●   数据流分析技术直接分析程序源码, 组合使用调用图分析、指向分析和逃逸分析等静态分析技术, 计算静态锁占用约束或者锁占用顺序图, 使用约束求解和环检测算法在其上检测环, 将环作为可能的死锁报告出来.该类方法缺乏精确的运行时信息, 一般对变量值作保守估计, 因此能较全面地发现潜在死锁, 但会产生较多的误报;

●   定理证明与模型检验通常对程序行为进行形式化建模, 之后通过模型的分析探索程序所有可能的执行路径, 进而在理论上暴露潜在的死锁.该类方法的缺点是模型建模需大量的人工参与, 而且如何保证抽象模型与程序语义的等价性至今悬而未解;

●   动态分析通过运行代码, 获取程序执行轨迹, 进而抽取执行轨迹中蕴含的程序行为模式, 在此基础上进行死锁检测.动态分析方法充分利用了程序的运行时信息, 故而检测的准确度较高, 误报较少; 而且由于运行轨迹只蕴含了程序的部分行为, 这使得动态分析的效率也较高.不过, 这同时带来了动态分析漏报率高的缺点.然而, 鉴于死锁误报排除上的困难性, 以及动态分析可自动化、效率高等优点, 动态分析仍然是程序死锁检测的主流方法.

一般而言, 动态死锁分析方法从程序运行轨迹中提取锁授权顺序中存在的特定模式, 并据此检测潜在死锁.例如, 文献[11]首次基于锁图(将每个锁对象作为图中的一个节点; 当某线程在持有锁对象A的情况下申请锁对象B时, 在节点A到B之间添加一条有向弧, 由此形成的图称为锁图)提出了一个死锁的动态分析工具Visual Threads, 它将锁图中的每个环路视为一个潜在死锁.这种方法简单有效, 但是存在多种类型的误报.比如, 单一线程访问锁对象导致的环路、由门锁保护的环路、具有因果关系的多个线程之间的锁授权操作导致的环路等, 这些环路都会导致死锁误报.文献[12]提出了基于锁树的GoodLock死锁检测算法, 该算法能排除单线程环和门锁环导致的误报, 但只能检测两个线程之间由于资源的持有和等待导致的死锁.文献[13]对GoodLock算法进行了改进, 使其能够检测任意线程之间导致的死锁.文献[14]提出了环锁依赖链(cyclic lock dependency chain)的概念, 它在锁图有向弧的基础上扩充了线程ID、当前持有的锁集等信息, 能同时排除单线程环和门锁保护环导致的误报, 而且对构成死锁的线程数量没有限制.文献[15]设计方法对基于环锁依赖链的死锁检测方法进行性能改进, 基本思想是: 先设计算法识别和消除可移除的锁依赖关系, 之后再进行死锁的定位.由此提出了扩展性和效率更高的Magiclock死锁检测方法.前述死锁检测方法能消除单线程环和门锁环导致的误报, 实际上, 线程的start和join语句也会引起多个线程间锁授权操作上的因果关系, 这同样会导致误报.针对这一问题, 文献[16, 17]基于线程的start和join语句对线程的操作进行分段, 根据段之间的依赖关系提出了分段图的概念; 与此同时, 在传统锁图的基础上扩充线程ID、当前持有的锁集、段号等信息提出了扩展锁图的概念; 最终, 综合分段图和扩展锁图提出一种新型的死锁检测方法, 可以排除单线程环、门锁环和多线程间具有因果关系的锁授权操作环导致的误报.类似地, 文献[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行和第28行关于锁q和p的嵌套获取”与“threadC在第35行和36行关于锁p和q的嵌套获取”不会导致死锁, 因为threadB获取q和p的前提是持有锁m, 而一旦threadB先持有了m, 则threadC便会被阻塞在第34行获取m的位置, 从而无法嵌套获取p和q; 反之, threadC获取p和q的前提是持有锁n, 而一旦threadC先持有了n, 则threadB将被阻塞在第26行获取n的位置, 从而无法嵌套获取q和p.由此可见: 虽然threadB执行第28行获取p的操作时持有的锁集为{m, q}, threadC执行第36行获取q的操作时持有的锁集为{n, p}, 两个持有锁集互不相交, 但是它们之前曾经持有和随后释放的锁对象n和m却也形成一组门锁, 从而消除了这两个操作并发的可能性, 使得它们不会导致死锁.

1.2 动机分析

如上节所述, Program 1存在4处锁对象嵌套获取构成的循环依赖环路, 但只有两处对应真实死锁, 另两处不是死锁.然而, 传统的动态死锁分析方法无法区分上述情况, 由此导致死锁误报.

具体来说, 假设Program 1某次运行轨迹见表 2.其中, start(u, v)代表线程u启动线程v的操作, stop(u)代表线程u的终止操作, join(u, v)代表线程u同步等待直至线程v终止, acq(t, l)表示线程t获取锁l的操作, rel(t, l)代表线程t释放锁l的操作.下面以基于分段图和扩展锁图的死锁检测方法为例, 说明传统动态分析方法的检测结果.

文献[17]基于start和join将源程序的操作分为很多段, 并根据各个段在执行顺序上的先后依赖关系构造分段图.具体来说, 最初仅为主线程添加一个初始段; 之后, 每当执行操作start(u, v)时, 在线程u此操作之处添加一个新段, 为线程v添加一个初始段, 并在线程u的上一个段与这两个新段之间各添加一条有向弧; 每当执行操作join(u, v)时, 为线程u添加一个新段, 在u的上一个段与此段间添加一条有向弧, 并在线程v的线程终止段与此段间也添加一条有向弧(该有向弧的添加需要待线程v执行终止操作时方能添加).对于表 1的运行轨迹, 构造所得的分段图如图 1(a)所示.

除构造分段图外, 文献[17]为锁图每条有向弧〈lock₁, lock₂〉扩充标记信息arcID: 〈seg₁ID, (threadID, lockSet), seg₂ID〉, 提出了扩展锁图的概念.其中, arcID表示弧的唯一ID, threadID表示当前锁申请操作所属线程的ID, seg1ID代表threadID获取锁lock₁所在的段号, seg₂ID代表threadID获取锁lock₂时所在的段号, lockSet代表threadID获取锁lock₂前持有的锁集.图 1(b)为表 1运行轨迹对应的扩展锁图, 它由2个子图构成.

得到分段图和扩展锁图后, 文献[17]按照如下规则识别死锁: (1) 扩展锁图中两个锁的获取操作构成一条有向环; (2) 两个操作分属于的不同的线程; (3) 分段图中, 这两个操作所在的段不存在有向路径相连(若存在有向路径则说明这两个操作存在执行次序上的先后依赖关系, 无法并发, 也就不构成死锁); (4) 这两个操作执行时所持有的锁集互不相交.

按上述规则, 图 1(b)中ID为2, 7的两条有向弧对应的操作会被认为导致死锁.因为两者在扩展锁图中形成环路, 分属不同的线程, 所在的5号段和6号段不存在有向路径相连, 两者持有的锁集{G, o1}与{o2}不相交.此外, ID为5的有向弧与ID为2的两条有向弧是同一个锁获取语句在两个不同轮次循环中的具体执行, 扩展锁图无法对其区分, 两者的标记信息完全一样, 从而也会认为导致一个死锁.而实际上, 如第1.1节所述, 其中一个是真实死锁, 另一个是死锁的误报.最后, 图 1(b)中ID为11, 15的两条有向弧对应的操作也符合前述4条规则, 从而也会被判定导致死锁.但如上节所述, 这个死锁也是误报.

上述第1个误报的产生根源是: threadA在持有锁G之后方才启动线程threadB, 从而导致图 1中2, 7两条弧对应的操作间具有因果关系(仅当弧2对应的操作执行完并释放锁G后, 弧7对应的操作方能执行), 而这种因果关系在分段图中未能刻画(5号段和6号段间不存在有向路径).为处理这一问题, 本文稍后将定义一种“锁-start”耦合因果依赖关系.

第2个误报产生的根源是: threadB获取锁p必须先获取n, 而锁n的释放导致了threadB获取q时的持有锁集不会包含n; 同理, threadC欲获取锁q必须先获取m, 而锁m的释放导致了threadB获取p时的持有锁集不会包含m, 这就导致了他们的持有锁集交集为空, 而已有方法仅根据持有锁集是否相交排除门锁环误报, 所以会认定其构成一个潜在死锁.而实际上, 若要真正触发上述死锁, 则锁n需要被threadB获取并释放后才能授权给threadC.类似地, 锁m需要被threadC获取并释放后才能授权给threadB, 也就是说, 对于同时存在于线程u之历史持有锁集与另一线程v之持有锁集中的锁对象o而言, 历史持有锁的获取操作acg(u, o)应先于持有锁的获取操作acg(v, o), 我们称这种关系为“历史持有锁-持有锁”耦合因果依赖关系, 其严格定义稍后给出.Program 1中, 这种依赖关系要求操作26:acq(threadB, n)先于33:acq(threadC, n)执行; 同时, 操作34:acq(threadC, m)先于25: acq(threadB, m)执行.又因为33:acq(threadC, n)与34:acq(threadC, m)同属一个线程, 语句顺序在前的操作33: acq(threadC, n)必然先于34:acq(threadC, m)执行, 由此可得26:acq(threadB, n)需要先于25:acq(threadB, m)执行.然而这是不可能的, 因为作为同一线程threadB的两步操作, 第26行语句对应的26:acq(threadB, n)不可能先于第25行语句对应的操作25:acq(threadB, m)执行.这说明本例中的“历史持有锁-持有锁”耦合因果依赖关系无法得到满足, 此时, 即使多个锁获取操作构成环路也无法真正触发死锁.已有的分段图和扩展锁图等模型均未对这种“历史持有锁-持有锁”耦合因果依赖关系进行刻画和可满足性判定, 故导致了本例的第2种死锁误报.

一般而言, 死锁误报产生的原因就是程序模型遗漏了上述某些因果依赖或互斥关系, 本文将上述实例中展现的各种因果和互斥关系进行处理.为此, 首先定义多线程程序操作间的依赖和互斥关系如下.

定义1(操作的依赖与互斥关系). 给定一个多线程程序的运行轨迹σ=e₁e₂e₃...e_n.

(1)    若事件e_i与e_j同属一个线程(即e_i.thread=e_j.thread)且i < j, 则称e_i和e_j之间存在线程内因果依赖关系, 记为e_i < _threade_j;

(2)    若e_i=start(u, v), 存在k≤i使得e_k.thread=u, 存在m > i使得e_m.thread=v, 则称e_k与e_m之间存在线程间因果依赖关系, 记为e_k < _starte_m; 若e_i=join(u, v), 存在k < i使得e_k.thread=v, 存在m≥i使得e_m.thread=u, 则也称e_k与e_m之间存在线程间因果依赖关系, 记为e_k < _joine_m;

(3)    设e_i=acq(u, o), e_j=rel(u, o), i < j, 且e_i与e_j之间不存在事件rel(u, o), 但存在事件e_m=start(u, v), 则对于区间[m, j]中的任意整数k与线程v的任意操作e, 只要e_k.thread=u, 就称e_k与e之间存在“锁-start”耦合因果依赖关系, 记为e_k < _{lock_start}e;

统称前述3种关系为因果依赖, 记为 < ;

(4)    设e_i=acq(u, o1), e_j=acq(v, o2), 且两者相互间不具备前述3种因果依赖关系, 记线程u执行e_i时持有的锁集为lockSet(e_i), 线程v执行e_j时持有的锁集为lockSet(e_j).若lockSet(e_i)$ \cap $lockSet(e_j)≠Ø, 则称e_i和e_j之间存在锁集互斥关系, 记为e_i#_lockSete_j;

(5)    设e_i=acq(u, o1), e_j=acq(v, o2), 且两者相互间不具备前述3种因果依赖关系和锁集互斥关系, 记线程u获取lockSet(e_i)中各把锁的过程中曾经获取过的所有锁的集合为lockSet_OnceHeld(e_i), 称之为e_i执行时的历史持有锁集; 类似可得e_j对应的历史持有锁集lockSet_OnceHeld(e_j).记Lock_IntSecion=lockSet_ OnceHeld(e_i)$ \cap $lockSet(e_j), 若要使得e_i与e_j能并发以导致死锁, 则对于o∈Lock_IntSecion, 线程u获取

历史持有锁o的操作${e'_i} = acq(u, o)$应先于线程v最后一次获取持有锁o的操作${e'_j} = acq(v, o)$而执行, 称${e'_i}$与${e'_j}$之间存在“历史持有锁-持有锁”耦合因果依赖关系, 记为${e'_i}{ < _{lock\_held}}{e'_j}$.

不难发现: 对于上述5类关系, 若遗漏线程内依赖关系, 则可能导致单线程环死锁误报; 若遗漏线程间因果依赖关系, 则可能出现start/join导致的因果环死锁误报; 若遗漏锁集互斥关系, 则可能导致门锁环误报; 若遗漏“锁-start”耦合因果依赖关系和“历史持有锁-持有锁”耦合因果依赖关系, 则可能导致本文所给程序实例中的误报.已有的各类基于锁图及其各种变形模型的死锁动态分析方法主要识别和处理前3种关系导致的误报, 难以解决本文给出的两种新型关系导致的误报.

针对上述问题, 本文一方面在扩展锁图的基础上添加语句的执行时序信息, 以区分循环中不同轮次的锁获取操作, 据此提出时序增广锁图的概念; 另一方面, 在分段图的基础上扩充锁的申请和释放信息, 以此识别锁获取和释放操作与线程start操作耦合引起的因果关系, 在此基础上对分段图作进一步细化, 由此提出了锁增广分段图的概念; 最终, 综合两个工具提出一种更为准确的死锁检测方法.下面给出具体介绍.

2 锁增广分段图与时序增广锁图的构造

本节对多线程程序的运行轨迹给出形式化定义, 并对锁增广分段图和时序增广锁图的构造规则予以说明.

2.1 多线程程序的运行轨迹

定义2(多线程程序运行轨迹). 对于一个多线程程序, 其运行轨迹定义为死锁相关的并发原语在执行过程中形成的轨迹σ, 严格定义如下:

$ \begin{array}{*{20}{c}} {\sigma \in ConPrimitiv{e^*},}\\ {ConPrimitive:: = start(u,v)|stop(v)|join(u,v)|acq(u,l)|rel(u,l).} \end{array} $

其中,

●   ConPrimitive表示各类并发原语的集合, ConPrimitive^*为并发操作构成的序列全体;

●   u, v∈Tid表示线程, l∈Lock表示锁;

●   start(u, v): 线程启动线程;

●   stop(v): 线程执行终止;

●   join(u, v): 线程等待线程执行终止;

●   acq(u, l): 线程锁对象;

●   rel(u, l): 线程释放获取锁对象.

表 2给出的就是Program 1的一个程序运行轨迹.

2.2 锁增广分段图

本节在传统分段图的基础上扩充锁的申请和释放信息, 并根据“锁-start”耦合因果依赖关系对段的划分进行细化, 由此提出了锁增广分段图的概念.以表 2中的程序运行轨迹为例, 拟构造的锁增广分段图如图 2所示.

在锁增广分段图中, 每个段除含有段号信息外, 增加了此段中所执行的锁授权和释放操作的信息.以4号段为例, 它依次执行了获取锁n、获取m、释放m、获取p、获取q、释放q、释放p、释放n的操作, 这一过程通过标记(n⁽³²⁾, m⁽³³⁾, m⁽³⁴⁾, p⁽³⁵⁾, q⁽³⁶⁾, q⁽³⁷⁾, p⁽³⁸⁾, n⁽³⁹⁾)刻画(标记中, 各个锁对象右上角括号中的序号是本次操作在运行轨迹中的操作序号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号段的开头, 此时无需添加新的分段, s^'_new为6);

(2.2) 与s^''同属一个线程的、s^''的子孙节点中必然存在一个以l的释放为尾操作和分段点的段s^''_desc (例如图 2种的5号段), 显然, s^''_desc与s^'_new存在一种依赖关系, 仅当s^''_desc执行结束、释放l后, s^'_new中的操作方能执行, 故在s^''_desc与s^'_new之间添加一条有向弧(例如, 图 2种由5号段到6号段之间的有向弧).

相比传统的分段图, 锁增广分段图中添加的锁授权和释放信息有助于死锁检测过程中计算各个操作执行前历史曾经持有的锁信息, 而且按前述规则对段进行细分后, 能够刻画锁的释放和授权操作引起的段之间的因果关系, 这为后续准确地进行死锁检测奠定了基础.锁增广分段图的形式化定义及构造规则如下(与传统分段图构造规则不同的部分加粗显示).

定义3(锁增广分段图). 给定一个多线程程序的运行轨迹σ=e₁e₂e₃...e_n, 其对应的锁增广分段图SegG_Lock_σ是满足如下条件的四元组$\left(\operatorname{Seg} \operatorname{Set}_{\sigma}, \operatorname{Seg} R_{\sigma}, \varphi_{s}, \varphi_{r}\right) $, 其中, SegSetσ是顶点集, $Seg{R_s} \subseteq SegSe{t_s} \times SegSe{t_s} $是关系集, φ_s与φ_r分别是定义在顶点和边上的标签函数:

(1)    SegSet_σ是顶点集, 每个顶点对应程序的一个分段, 其生成规则如下.

   (a)   添加一个0号段作为主线程的初始分段;

   (b)   每当有线程u执行操作start(u, v)时, 则在线程u此操作之处添加一个新段, 并为线程v添加一个初始分段;

   (c)   每当有线程u执行操作join(u, v)时, 则为线程u添加一个新分段;

   (d)   每当有一个线程u在段s中执行操作rel(u, l)时, 若u此前获取l的操作不在段s中, 则在此处为线程u添加一个新段;

   (e)   每当有一个线程v在段s^'中执行操作acq(v, l)时, 从该段节点逆向寻找第一个获取锁l的段节点s^'', 若s^''所属线程u≠v且s^''中未释放l, 则将s^'从当前l的获取操作处开始一个新的分段, 记其段号为s^'_new(若acq(v, l)是s^'的第1个操作, 则不必添加新分段, 令s^'_new: =s^'即可); 记与s^''同属线程u的、s^''的子孙节点中第1个以rel(u, l)为尾操作的段为s^''_desc, 将(s^''_desc, s^'_new)加入关系集SegR_σ, 并令这个关系对应的φ_r标签函数值为rel(u, l);

   (f)   每个段设置一个全局唯一的段号作为其ID(从0开始递增, 每次增加1);

(2)    SegR_σ⊆SegSet_σ×SegSet_σ记录段之间执行次序上的先后关系, φ_r是定义在SegR_σ上的标签函数, 他们的产生和定义规则如下.

   (a)   每当有线程u执行操作start(u, v)时, 记线程u之前的最后一个段为latest_Seg(u), 记因为这个操作而为u和v添加的新段为new_Seg(u)和new_Seg(v), 向SegR_σ中添加两个新关系(latest_Seg(u), new_Seg(u))和(latest_Seg(u), new_Seg(v)); 并令这两个关系对应的φ_r标签函数值为start(u, v);

   (b)   每当有线程u执行操作join(u, v)时, 记线程u之前的最后一个段为latest_Seg(u), 记因为这个操作而为u添加的新段为new_Seg(u), 向SegR_σ中添加新关系(latest_Seg(u), new_Seg(u)); 并令这该关系对应的φ_r标签函数值为join(u, v);

   (c)   每当有线程v执行操作stop(v)时, 若之前曾有线程u执行操作join(u, v), 并假设线程u由于操作join(u, v)而新添加的分段为new_Seg(u), 同时记线程v的最后一个段为latest_Seg(v), 则向SegR_σ中添加新关系(latest_Seg(v), new_Seg(u)); 并令这两个关系对应的φ_r标签函数值为join(u, v);

   (d)   每当有线程u因执行锁的释放rel(u, l)操作而添加一个新段s时, 记线程u之前的最后一个分段为s^', 将(s^', s)加入关系集合SegR_σ中, 并令这个关系对应的φ_r标签函数值为rel(u, l);

   (e)   每当有线程u因执行锁的获取acq(u, l)操作而添加一个新段s时, 记线程u之前的最后一个分段为s^', 将(s^', s)加入关系集合SegR_σ中, 并令这个关系对应的φ_r标签函数值为acq(u, l);

(3)    φ_s是定义在SegSet_σ上的标签函数, 其生成规则如下.

   (a)   每个段最初生成时, 其φ_s标签函数值为空;

   (b)   每当有线程u执行操作acq(u, l)时, 假设该操作当前所在的段为currentSeg, 该操作的序号ID为

k, 则令φ_s(currentSeg): =φ_s(currentSeg)○l^(k)(其中, ○表示字符串的拼接函数);

   (c)   每当有线程v执行操作rel(u, l)时, 假设该操作当前所在的段为currentSeg, 该操作的序号ID为k, 则令φ_s(currentSeg): =φ_s(currentSeg)○l^(k).

以表 1中的程序运行轨迹为例, 按照上述定义得到的锁增广分段图如图 2所示.

显然, 锁增广分段图中的每个段对应一个线程的若干操作.若图中的两个段s₁和s₂满足$({s_1}, {s_2}) \in SegR_\sigma ^ + $(其中, ⁺表示关系的闭包运算), 则仅当s₁中的操作全部执行完毕后方能执行s₂中的操作, 记此种关系为s_{1$ \triangleright$}s₂.

图 2中, 2$ \triangleright$6与5$ \triangleright$6成立, 意味着仅当2号段与5号段中操作执行完毕后方能执行6号段中的操作; 6$ \triangleright$7与7$ \triangleright$6均不成立, 这意味着, 6号段与7号段之间的操作不存在执行次序上的先后依赖关系, 此时认为这两组操作可以并发.

2.3 时序增广锁图

本节在扩展锁图的基础上添加语句的执行时序信息, 以区分循环中不同轮次的锁获取操作; 同时, 在图中标注每个操作在运行轨迹中的操作序号ID(据此定位操作在分段图中的位置), 由此提出时序增广锁图的概念.

以表 2中的程序运行轨迹为例, 拟构造的时序增广锁图如图 3所示.其中, 2号弧的标记信息由扩展锁图图 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〉⁽¹¹⁾.在扩展锁图中标记相同、无法区分的2号弧和5号弧, 在图 3的时序增广锁图中有了不同的标记.

经上述处理后, 一方面可以保证同一个锁授权语句在循环中的多次执行能区分开来; 另一方面, 可根据各条弧所对应操作在运行轨迹中的序号ID确定其在锁增广分段图中的位置, 从而为后续死锁检测提供方便.下面给出时序增广锁图的形式化定义与构造规则.

定义4(时序增广锁图). 给定一个多线程程序的运行轨迹σ=e₁e₂e₃...e_n, 其对应的时序增广锁图LockG_ Order_σ是满足如下条件的二元组(V_σ, R_σ).

(1)    V_σ为顶点集, 每个顶点对应σ中出现的一个锁对象;

(2)    R_σ⊆V_σ×Γ×V_σ为关系集, Γ是图中各关系所对应之有向弧的标签集合;

(3)    每当σ中有一个线程t在持有锁lock₁的前提下获取锁lock₂时, 假设该操作的序号ID为k, 则为此操作添加一个关系(lock₁, γ, lock₂)∈R_σ, 其中的γ形如:

$ {\left\langle {se{g_{\rm{1}}}ID,(t, lockSet ),m,se{g_{\rm{2}}}ID} \right\rangle ^{(k)}}, $

其中, seg₁ID是线程t获取锁lock₁时所在的段号, seg₂ID是线程t获取锁对象lock₂时所在的段号, lockSet是线程t获取锁lock₂前持有的锁集, m记录线程t的当前操作是其第几次获取锁lock₂;

(4)    是满足上述条件的最小有向图.

以表 2中的程序运行轨迹为例, 按照上述定义得到的时序增广锁图如图 3所示.

显然, 时序增广锁图中任意两点间若存在有向环, 则它对应着一组锁对象的循环持有和等待.例如, 图 3中共有4组有向弧对{2, 7}, {5, 7}, {8, 12}, {11, 15}构成有向环.传统的基于锁图以及基于分段图和扩展锁图的死锁检测方法会判定这4组有向环均导致死锁.实际上, 如第1节所述, 它们当中只有两个是真实死锁, 而另两个是误报.基于本文提出的时序增广锁图和锁增广分段图可以排除上述误报.下节给出具体方法.

3 基于锁增广分段图与时序增广锁图的死锁检测

传统的基于分段图和扩展锁图的死锁检测方法通过如下规则识别死锁: (1) 锁图中多个锁的申请操作构成一条有向环; (2) 锁申请操作分属于不同的线程; (3) 记任意两个锁操作所在的段为s₁和s₂, 则分段图中s₁和s₂之间不存在有向路相连, 意即这些操作在执行顺序的先后上无因果依赖关系; (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$ \triangleright$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₁₁= {m⁽²¹⁾, q⁽²⁴⁾}.根据前述规则, 需访问的标签依次为q⁽²⁴⁾, n⁽²³⁾, n⁽²²⁾, m⁽²¹⁾, 由此可得lockSet_OnceHeld₁₁={q⁽²⁴⁾, n⁽²²⁾, m⁽²¹⁾}.类似地, 对图 3中ID为15的弧, 它对应线程threadC段4中的一个操作, 操作执行时的持有锁集lockSet₁₅= {n⁽³²⁾, p⁽³⁵⁾}, 需访问的标签依次为p⁽³⁵⁾, m⁽³⁴⁾, m⁽³³⁾, n⁽³²⁾, 由此可得lockSet_OnceHeld₁₅={p⁽³⁵⁾, m⁽³³⁾, n⁽³²⁾}.

显然, lockSet_OnceHeld₁₁$ \cap $lockSet₁₅={n}, lockSet_OnceHeld₁₅$ \cap $lockSet₁₁={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} \subseteq V_{c} \times 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})$ \cap $lockSet(e_{k_j})且u≠v, 记线程u获取历史持有锁o的各个操作构成的集合为E_OnceHeld(e_{k_i}, o), 线程v最后一次获取持

有锁o的操作为${e'_{k\_j}}$, 则:

   (1.1) 对应线程v最后一次获取持有锁o的操作${e'_{k\_j}}$, 向V_C中添加一个ID为(v, o^(y))的操作, 其中, y为操作${e'_{k\_j}}$在程序运行轨迹中的序号ID;

   (1.2) 对应线程u每一个获取历史持有锁o的操作${e'_{k\_i}} \in E\_OnceHeld({e_{k\_i}}, o)$, 向V_C中添加一个ID为(u, o^(x))的操作, 其中, x为操作${e'_{k\_i}}$在程序运行轨迹中的序号ID; 与此同时, 向Rc中添加一条由顶点(u, o^(x))指向顶点(v, o^(y))的有向边;

(2)    对Vc中任意两顶点(u, p⁽ⁱ⁾)与(v, q^(j)), 若u=v$ \wedge $i < j, 则向Rc中添加一条由顶点(u, p⁽ⁱ⁾)指向顶点(v, q^(j))的有向边.

不难发现: 定义5中的规则(1.2)添加的有向边用以刻画第1节给出的“历史持有锁-持有锁”耦合因果依赖关系, 规则(2)添加的有向边用以刻画第1节给出的线程内因果依赖关系.若要使得环路c对应一个真实死锁, 则这些关系应该同时得到满足.而这些因果同时得到满足的一个必要条件就是“历史持有锁-持有锁”耦合因果关系图中不存在有向环, 因此, 对于时序增广锁图中的任意一条有向环路c而言, 若其对应的“历史持有锁-持有锁”耦合因果关系图中存在有向环, 则c对应的潜在死锁是一个误报.

以图 3时序增广锁图中有向弧11与15构成的有向环路为例, 它们对应的操作分别为e₂₆=28:acq(threadB, p)和e₃₆=36:acq(threadC, q).不难发现, lockSet_OnceHeld(e₂₆)={m, n, q}, lockSet(e₃₆)={n, p}.显然, threadB与theadC是两个不同的线程, 且存在锁对象n∈lockSet_OnceHeld(e₂₆)$ \cap $lockSet(e₃₆), 规则(1)的条件满足; 接下来, 根据规则(1.1), 应向DependG_POrder_c中添加ID为(threadC, n⁽³²⁾)的顶点, 它对应threadC最后一次获取持有锁n的操作; 根据规则(1.2), 向DependG_POrder_c中添加ID为(threadB, n⁽²²⁾)的顶点, 它对应threadB获取历史持有锁n的操作; 再根据规则(1.2)添加一条由(threadB, n⁽²²⁾)指向(threadC, n⁽³²⁾)的有向边.类似可见, m∈lockSet_ OnceHeld(e₂₆)$ \cap $lockSet(e₃₆), 根据规则(1), 应向DependG_Lock_c添加顶点(threadC, m⁽³³⁾), (threadB, m⁽²¹⁾)以及两者之间的一条有向边.再根据规则(2), 应根据线程内因果关系添加由(threadB, m⁽²¹⁾)指向(threadB, n⁽²²⁾)以及由(threadC, n⁽³²⁾)指向(threadC, m⁽³³⁾)的两条有向边, 最终可得图 4中的“历史持有锁-持有锁”耦合因果关系图.

显然, 图 4所示“历史持有锁-持有锁”耦合因果关系图存在有向环, 这意味着图中各操作之间的线程内因果依赖关系与“历史持有锁-持有锁”耦合因果依赖关系无法同时满足, 从而意味着“ID为11的弧对应的锁获取操作”与“ID为15的弧对应的锁获取操作”无法并发, 故弧{11, 15}构成之有向环路对应的潜在死锁非真实死锁.

基于上述分析, 可得基于锁增广分段图和时序增广锁图的死锁检测算法如下, 检测本质是如下5条规则.

(1)    时序增广锁图中多个锁申请操作构成一条有向环路(对应算法第1步);

(2)    环路中的锁申请操作分属于的不同的线程(对应算法第3步);

(3)    环路中任意两个锁申请操作无线程间因果依赖和“锁-start”耦合因果依赖, 即, 在锁增广分段图中无路径相连(对应算法第17步);

(4)    环路中的任意两个锁申请操作对应的持有锁集互不相交(对应算法第28步);

(5)    环路对应的“历史持有锁-持有锁”耦合因果关系图不存在有向环(对应算法第30步).

算法1. 基于锁增广分段图和时序增广锁图的死锁检测.

输入: 锁增广分段图SegG_Order_σ, 时序增广锁图LockG_Order_σ及其中的环路集合Cycles(LockG_Order_σ);

输出: LG_Order_σ中与潜在死锁对应的环路的集合DeadlockCycles(LockG_Order_σ).

步骤:

1. FOR EACH (c∈Cycles(LockG_Order_σ)){

2.   记c中的有向弧集合为$ \varepsilon $={$ \varepsilon $₁, $ \varepsilon $₂, $ \varepsilon $₃, ..., $ \varepsilon $_n};

3.   IF ($ \varepsilon $中各条弧对应的操作都属于不同的线程){

4.   SegDepFLAG: =0;  //SegDepFLAG用以标记$ \varepsilon $中各操作在锁增广分段图中是否具有因果依赖关系

5. FOR EACH ($ \varepsilon $_i∈$ \varepsilon $){

6.       FOR EACH ($ \varepsilon $_j∈$ \varepsilon $){

7.         IF (i≠j){

8.           记$ \varepsilon $_i和$ \varepsilon $_j对应的操作在段图中所属段的段号为s_i和s_j;

9.              IF ((s_i$ \triangleright$s_j)$ \vee $(s_j$ \triangleright$s_j)){   //在锁增广段图中两个操作存在执行顺序上的先后依赖关系

10.              SegDepFLAG: =1;    //SegDepFLAG为1, 意味着两个操作在分段图中存在因果依赖

11.             BREAK;

12.             }  //IF

13.            }  //IF

14.         }  //FORE ACH

15.       IF (SegDepFLAG ==1) BREAK;

16.         }  //FOR EACH

17.         IF (SegDepFLAG==0){    //环路中任意两个操作在锁增广段图中均不存在执行因果依赖

18.        LockExclusiveFlag=0;  //用以标记环路中的锁操作是否存在锁集互斥关系

19.       FOR EACH ($ \varepsilon $_i∈$ \varepsilon $){

20.         FOR EACH ($ \varepsilon $_j∈$ \varepsilon $){

21.           IF $(i \ne j, \& \& (lockSe{t_{{\varepsilon _i}}} \cap lockSe{t_{{\varepsilon _j}}} \ne \emptyset ))$ {

22.            LockExclusiveFlag=1;  //表示任意两个操作对应的持有锁集的交集不为空

23.          BREAK

24.          }  //IF

25.         }  //FOR EACH

26.       IF (LockExclusiveFlag==1) break;

27.          }  //FOR EACH

28.          IF (LockExclusiveFlag==0){  //环路中的操作相互之间均不存在锁集互斥关系

29.           根据定义4构造环路c对应的“历史持有锁-持有锁”耦合因果关系图DependG_Lock_c;

30.         IF (DependG_Lock_c不存在有向环)

31.          将c加入集合DeadlockCycles(LockG_Order_σ);  //得到一个潜在死锁

32.            }  //IF

33.          }  //IF

34.         }  //IF

35.     }  //IF

36.   }  //FOR EACH

37. RETURN DeadlockCycles(LockG_Order_σ).

相比传统方法基于分段图和扩展锁图进行的死锁检测, 算法1的规则(3)基于锁增广分段图进行的段间因果依赖的判定更加准确, 第5条规则能排除“历史持有锁-持有锁”耦合因果依赖关系导致的误报.如此一来, 对于图 3中4组有向弧对{2, 7}, {5, 7}, {8, 12}, {11, 15}构成的有向环路, 算法1能准确地识别出其中{5, 7}和{8, 12}对应的环路会导致死锁, 而{2, 7}和{11, 15}对应的环路不会导致死锁, 从而避免了它们给传统方法带来的死锁误报.

4 相关工作对比与实验评估 4.1 相关工作对比

基于锁图、环锁依赖链、分段图与分段锁图以及本文方法对表 2中的程序运行轨迹进行分析, 所得死锁检测结果见表 3.除本文方法之外, 其余3类方法会将锁图中的每条环路都认定为一个死锁.第1行对应的死锁误报, 是因为它们无法识别“锁-start”耦合因果依赖关系; 第4行对应的死锁误报, 是因为它们未处理“历史持有锁-持有锁”耦合因果依赖关系.而实际上, 这两类关系都可能导致环路中的某些操作无法并发.本文方法通过对传统锁图和分段图的改进弥补了上述不足, 并借助锁增广分段图和“历史持有锁-持有锁”耦合因果关系图对上述情形进行了识别, 从而能避免了传统方法中存在的上述死锁误报现象.

需要进一步指出的是: 动态分析方法从程序运行轨迹中捕获的程序行为信息始终有限, 丢失的信息既可能导致检测出的潜在死锁不是真实死锁, 还可能导致原本不存在死锁的程序被误定为存在死锁.针对这种情况, 在死锁分析领域, 除上述提到的死锁检测方法外, 有学者开始研究潜在死锁的重演.所谓死锁重演, 就是针对检测到的潜在死锁, 通过对程序执行的主动干预和调度, 使潜在死锁在为真实死锁的情况下会被尽可能地触发, 重演成功的潜在死锁必是真实死锁.例如, 对本文提出的“历史持有锁-持有锁”耦合因果依赖导致的死锁误报, 文献[21]中曾有一个程序实例.但文献[21]中采用的死锁检测算法ConLock+并不能排除该误报, 文中是通过死锁重演来排除这一误报的.相比而言, 本文提出的死锁检测算法无需重演, 在检测阶段即可将该误报排除.不过, 即便如此, 由于程序轨迹中不可避免地会丢失一些程序行为信息, 即使本文方法也存在某些类似的误报现象, 所以死锁的重演也是本文后续研究的重点方向之一.

在死锁重演方面, 文献[20, 22]首次提出一种面向缺陷重演的随机调度方法, 通过不同调度方案下程序的大量运行, 来尽量触发死锁等并发缺陷.该方法面向缺陷重演的调度是盲目的、完全随机的, 考虑到死锁通常是低概率事件, 这导致该方法在效率和可靠性方面的不足.相比而言, 文献[14, 18, 21, 23-25]先进行潜在死锁的检测, 之后有针对性地设计程序调度方案, 以此提高真实死锁重演成功的概率.具体地说, 文献[14, 18, 23]面向潜在死锁提出一种启发式调度策略, 在线程到达潜在的死锁点时挂起线程, 以此增加死锁触发的概率.不过, 这种方法本质上仍是随机的, 真实死锁通常需多次运行才能重演成功, 而且它们不能提供系统的、完整的覆盖.考虑到死锁的触发应同时考虑死锁的发生位置和该位置之前一些相关的锁授权操作, 文献[24]提出一种基于屏障的死锁重演调度算法ASN, 将程序调度的干预时机进行了优化.类似地, 文献[21, 25]针对潜在死锁生成一组程序调度的约束集, 当程序的运行不符合生成的约束时, 挂起线程的执行.上述方法提高了真实死锁重演成功的概率, 不过, 其面向死锁重演生成的程序调度方案不够直观, 而且同前述潜在死锁的检测方法一样, 均对同一个锁授权语句的多次执行不加区分, 这也为死锁重演带来了困难.

本文所提出的死锁检测工具, 一方面能对循环中同一个锁授权语句的多次执行加以区分; 另一方面, 锁增广分段图中既对不同线程中的各个操作根据执行顺序上的依赖关系进行了刻画, 还完整记录了锁的获取和释放操作.基于它们, 有望为死锁的重演生成一种更为直观可行的重演方案, 篇幅所限, 具体方法将在以后展开.

4.2 原型系统与实验评估 4.2.1 原型系统

作者基于开源的Java多线程程序主动调试平台CalFuzzer^[26]开发了相应的死锁检测工具.基于该工具, 用户只需要输入一个多线程程序, 通过分析CalFuzzer产生的程序运行事件流, 工具便能自动生成相应的时序增广锁图和锁增广分段图, 并给出死锁检测的结果.所开发工具的架构和运行界面如图 5、图 6所示.

原型系统架构分为3层: 最底层为用户输入层, 需要用户输入一个多线程程序, 然后运用Calfuzzer挖掘出程序的运行轨迹; 中间层为处理层, 处理层接收到运行轨迹, 进行模型挖掘, 构建时序增广锁图和锁增广分段图, 并基于算法1的检测规则识别潜在死锁; 界面层向用户展示挖掘得到的锁增广分段图、时序增广锁图, 在显示模型的同时给出死锁检测的结果(如图 5所示).

工具运行界面截图中, 位于左侧的是锁增广分段图, 在锁增广分段图中, 同一颜色的段号代表属于同一个线程, 其中段中所记录的锁获取释放信息可设置为对隐藏或显示; 位于右上的是时序增广锁图; 位于右下的是用本文方法检测到的潜在死锁信息.图中给出的是对论文中程序实例Program 1的死锁检测结果(如图 6所示).

4.2.2 实验评估

第1节结合多线程程序Program 1, 从原理上说明了本文方法相比iGoodlock等经典死锁分析方法的优势.本节结合表 4中更多的Java多线程程序实例进行实验评估, 表中前8个样例来自于CalFuzzer开源项目中提供的程序样例; pingpong, cyclicDemo来自于文献[27]; ConLockDemo为文献[21]设计的程序实例, 其中包含本文要解决的“历史持有锁-持有锁”耦合因果依赖导致的死锁误报, 文中通过重演的方法排除误报, 检测阶段无法排除; PetriDeadLockDemo包含“锁-start”耦合因果依赖关系导致的传统方法的死锁误报, 文中通过Petri网行为分析排除误报, 效率较低; OnceHeldLockDemo是在本文Program 1基础上添加延时等操作后得到的完整程序实例, 它既包含“锁-start”耦合因果依赖导致的死锁误报, 也包含“历史持有锁-持有锁”耦合因果依赖导致的误报.以上程序实例仅涉及两个线程导致的死锁.为进行更一般化的验证, MulThreadDeadlockDemo是专门设计的一个多线程死锁的程序实例, 其中包含一个3线程导致的真死锁和4线程导致的死锁误报.

具体实验结果见表 4.下面从死锁检测准确性、时间和内存开销这3个方面进行实验对比, 对比结果优势明显的项目用加粗显示.对照的死锁检测基准程序为CalFuzzer自身集成的死锁动态分析工具iGoodlock.实验环境中, CPU为Intel(R) Core(TM)i5-6300HQ CPU@2.30GHz, 内存为8.00GB, 操作系统为Ubuntu 18.10.

就死锁检测的准确性而言, iGoodlock仅消除了单线程环和门锁环导致的误报, 而本文方法进一步消除了线程间因果依赖关系、“锁-start”耦合因果依赖关系以及“历史持有锁-持有锁”耦合因果关系导致的误报.就死锁检测的时间性能而言, 当程序中存在潜在死锁时, 本文方法的时间性能要优于iGoodlock.一个主要原因是: 本文基于文献[28]所提出的图矩阵化方法计算锁增广分段图中的环路, 其时间复杂度是多项式级的, 而iGoodlock基于图的遍历完成环路检测, 其时间复杂度是指数级的.当程序中不存在潜在死锁时, 矩阵化方法检测环路与遍历法检测环路的时间开销接近, 此时, 因本文需要构造的锁增广分段图和时序增广锁图相比iGoodlock要构造的环锁依赖链含有更多的信息, 同时, 本文方法还需构建“历史持有锁-持有锁”耦合因果图并要判断其中是否包含环路, 故本文方法的时间性能此时会稍差.就空间性能而言, 本文方法比iGoodlock消耗更多的内存: 一方面, 本文需要构建的锁增广分段图和时序增广锁图相比iGoodlock构建的环锁依赖链包含了锁的获取和释放以及操作时序等额外信息, 这会占用更多的内存; 另一方面, 本文检测死锁过程中构造的“历史持有锁-持有锁”耦合因果关系图也是iGoodlock等传统方法中不曾有的, 它也会引起更大的内存开销.

5 总结与展望

围绕多线程程序的死锁检测问题, 通过对传统动态死锁分析方法所存误报现象的分析, 本文对锁图、分段图等传统的死锁分析模型进行改进: 一方面, 在扩展锁图的基础上添加语句的执行时序信息来区分同一循环中不同轮次的锁获取操作, 据此提出了时序增广锁图的概念; 另一方面, 在分段图的基础上扩充锁的获取和释放信息, 并对段进行更细粒度的划分以刻画锁对象的释放和获取操作导致的因果依赖关系, 据此提出了锁增广分段图的概念.最终, 在上述两个模型的基础上提出了一种新的死锁检测方法, 它不仅可以消除单线程环、门锁环、多线程间由于线程的start和join操作而引起的因果关系导致的死锁误报, 还能消除由于“锁-start”耦合因果依赖导致的死锁误报, 而且能排除“历史持有锁-持有锁”耦合因果依赖导致的误报, 由此减少了死锁的误报, 提高了死锁检测的准确率.然而, 本文方法也存在一定不足: 一方面, 本文仅考虑了线程的start/stop/join以及锁对象的释放和获取等并发原语, 而实际上, 线程的wait/notify/notifyAll等并发原语和其他一些程序的条件控制结构等操作也会对死锁产生影响, 要进行更为准确的死锁检测, 需要考虑更多的可能影响死锁的程序原语; 另一方面, 程序自动修复也是当前的研究热点之一^[29], 而如何基于本文的模型开展上述研究值得探究; 最后, 死锁同样存在于MPI并行程序^[30]、柔性制造系统^{[31, 32]}、软件定义网络^[33]等多种领域, 如何将本文方法像更多的领域推广也是后续重点需要研究的工作.