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

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

distinguish different executions of one lock acquisition statement in a loop structure. The lock set used in extended lock graphs cannot
capture those locks which were once held and then released. A segmentation graph cannot model the inter-segment dependencies caused
by the coupling of lock release/acquisition operation and thread start operation. The above problems have led to a variety of false
positives. To address this issue, existing lock graph and segment graph models are improved. Specifically, a lock graph is extended with
statement execution order information. A segmentation graph is expanded with lock acquisition and release information. Furthermore,
segments in a segmentation graph are more finely divided in the improved model to capture the inter-segment dependencies caused by
lock objects. Eventually, based on the improved models, a new deadlock detection method is proposed. It can eliminate the
aforementioned false alarms effectively and improve deadlock detection accuracy. A corresponding prototype system is developed for
experimental evaluation. The validity of the proposed method is verified through experiments.
Key words: program verification; deadlock detection; lock graph; segmentation graph; dynamic deadlock analysis

为提高软件系统的运行效率,并行编程技术得到广泛应用.与此同时,随着软件规模和复杂度的不断扩大,
加之并行程序在程序调度等方面的不确定性,死锁、数据竞争和原子性违背等并发缺陷日益显现 [1,2] .死锁是最
具代表性的并发缺陷之一,死锁的发生会导致程序无法正常运行甚至是系统崩溃,由此带来不必要的损失.而且
[3]
统计显示,约 30%的并发缺陷与死锁有关 .因此,死锁检测成为提高软件可靠性和安全性亟需解决的问题.
文献[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、当前持有的锁集、段号等信息提出了扩展锁图的概念;最终,综合分段图和
扩展锁图提出一种新型的死锁检测方法,可以排除单线程环、门锁环和多线程间具有因果关系的锁授权操作环