使用锁分配图动态检测混合死锁

禹 振 苏小红 邱 景

(哈尔滨工业大学计算机科学与技术学院 哈尔滨 150001)



使用锁分配图动态检测混合死锁

禹 振 苏小红 邱 景

(哈尔滨工业大学计算机科学与技术学院 哈尔滨 150001)

(yuzhen_3301@aliyun.com)

死锁难以暴露、重演和调试.一旦发生，将导致多线程程序响应时间增长、吞吐量下降甚至宕机崩溃.现有死锁检测技术每次只能检测一个互斥锁死锁.为一次性检测由多个线程和多个互斥锁或读写锁造成的所有类型死锁，首先提出混合锁分配图的概念和构建方法，然后提出一种利用混合锁分配图动态检测混合死锁的方法.通过劫持所有互斥锁和读写锁的加锁解锁操作，以动态构建和实时更新一个反映目标程序同步状态的混合锁分配图.通过在锁分配图上检测环并判定该环是否为死锁环来检测死锁.当检测到死锁时，输出死锁信息来辅助调试.死锁检测实验、性能影响实验和可扩展性实验结果表明：该方法成功检测出所有13个共5种类型的死锁缺陷，检测能力强；给openldap-2.2.20带来至多10.15%的性能下降幅度，对目标程序造成的性能影响较小；性能开销随线程数目指数级增大而平缓增长，扩展性良好.

动态分析；软件测试；并发缺陷检测；死锁检测；环检测

多线程程序中，一个线程集合中的每一个线程都在各自等待另一个线程占据的互斥性资源，由此导致的循环等待即为死锁.在所有并发缺陷中[1]，死锁是其中最常见和最重要的一种：多方统计调查显示[2-4]，死锁缺陷占所有并发缺陷的30%以上.死锁一旦发生，将可能导致多线程程序响应时间增长、吞吐量下降甚至宕机崩溃，严重威胁并发程序的可用性与可靠性.与其他并发缺陷一样，死锁具有难以暴露、重演和调试的特点[1]，因此死锁动态检测技术应在死锁缺陷发生时立即将其检测出来，并同时输出关于缺陷的相关信息以辅助调试.

现有的死锁检测技术可以分为静态分析和动态分析2大类，其中静态分析又可以分为类型与效应分析和数据流分析2类，而动态分析则可以再分为在线和离线2类，如表1所示：

Table 1 Categories and Summaries of Deadlock Detection Techniques表1 死锁检测技术分类与概述

类型与效应分析需要用户在源码中为变量或函数添加类型注释才能对程序进行类型推理和类型检查，故其人工干预度高、扩展性较差.另外该类技术没有考虑读写锁的语义，只能检查程序是否是免于互斥锁死锁的和检测是否存在互斥锁死锁.

数据流分析直接分析程序源码，综合使用调用图分析、上下文分析、指向分析和逃逸分析等静态分析技术，计算静态锁占用约束或锁占用顺序图，使用约束求解和环检测算法在其上检测环，将环作为可能的死锁报告出来.数据流分析缺乏精确的运行时信息，一般对变量值作保守估计，因此其误检率较高.同时该类技术的检测能力有限，有些技术如Jade[7]只能检测2线程互斥锁死锁，有些技术如SDD[8]虽能检测多线程互斥锁死锁，但不能检测读写锁死锁和由互斥锁和读写锁造成的混合死锁.

动态分析是目前死锁检测的主流技术，一般分为离线和在线2类.在线方法监视程序运行，实时获取感兴趣的信息，建立和更新目标程序同步状态的抽象表示，并在其上检测死锁.离线方法先对程序源码静态插桩，然后执行程序并获取执行轨迹，最后分析轨迹，建立锁占用顺序图，将其上检测到的环作为死锁报告出来.在线方法(GoodLock[15-16]和Sherlock[17]除外，它们可以在线预测可疑死锁)一般只能检测到本次执行中实际出现的死锁，而离线方法则还能“预测”在其他执行中可能出现的死锁.例如MagicFuzzer[18]和MagicLock[21]根据本次执行中预测到的死锁信息，在程序的下一次执行中，控制线程调度，试图使死锁暴露出来.相对于在线方法，离线方法误报率较高，需要存储执行轨迹，对长时间运行的并发程序不适用.在线分析不需要人工干预，扩展性好，没有误报，但其漏报率较高.尽管各有其优缺点，但它们都忽略了读写锁可能造成的死锁，只能检测互斥锁死锁.

Fig. 1 Dynamic detection algorithm to detect multiple types of deadlocks based on MLAGs图1 基于锁分配图的混合死锁动态检测方法

针对现有方法检测能力有限的问题，为提高现有方法的死锁检测能力，以便一次性检测由多个线程和多个互斥锁或读写锁造成的所有类型死锁，本文提出一种基于锁分配图的混合死锁动态检测方法，如图1所示.该方法主要由监视模块Monitor和检测模块Linter两部分组成.监视模块Monitor负责劫持所有互斥锁和读写锁的加锁解锁操作，根据劫持到的信息生成相应事件并将事件插入到线程的事件队列中.可能生成的事件共有5种：锁互斥请求事件、锁互斥占据事件、锁共享请求事件、锁共享占据事件和锁释放事件.检测模块读取并根据这些事件构建和更新混合锁分配图(multiple-type lock allocation graph, MLAG)，在其上使用强连通分量(strong connected component, SCC)算法检测环；如果有死锁环存在，则输出所有的环以及每个环中的所有线程ID和锁ID，并发送SIGSEGV信号以中止目标程序.操作系统将为该目标程序生成转储文件，程序员可以根据得到的死锁环信息和转储文件，使用GDB进行源码级别调试，快速理解和定位死锁的发生原因和位置.

我们提出的混合死锁检测方法有多重应用场景：在测试环境中，它可以配合死锁暴露技术来检测和验证死锁；在生产环境中，死锁规避技术可以使用它检测更多类型和更多数量的死锁，从而得到关于这些死锁的特征信息，以指导规避逻辑规避更多类型和更多数量的死锁.

1 检测对象与死锁环判定算法

多线程程序中，pthread库中2种同步设施互斥锁和读写锁的使用频率都很高.程序员通常使用互斥锁来保护只允许读写操作互斥执行的共享变量，而对于允许多个读操作同时执行但写操作互斥执行的同步场景，为提高性能程序员往往使用读写锁而不是互斥锁.因此本文试图检测由互斥锁和读写锁造成的5类死锁：互斥锁造成的死锁、读写锁造成的死锁、互斥锁和读写锁造成的混合死锁混合死锁、互斥锁自锁和读写锁自锁，如图2所示：

Fig. 2 Five deadlock scenarios caused by mutex and rwlock图2 互斥锁和读写锁造成的5种死锁场景

互斥锁与读写锁的区别是：互斥锁在任何时刻只能被至多一个线程占据，因此任何线程对互斥锁的占据和请求都是互斥占据和互斥请求；读写锁在任何时刻可被多个线程同时读占据，但只能被至多一个线程写占据，因此对读写锁的占据和请求各自分为2类，即共享占据与互斥占据和共享请求与互斥请求.本文将对锁(不论互斥锁还是读写锁)的互斥占据和互斥请求称为写占据和写请求，将对锁的共享占据和共享请求称为读占据和读请求.图2中用不同的线型和标签标示这4种操作.

本文定义混合锁分配图MLAG以表征多线程程序相对于互斥锁和读写锁的同步状态，并在此基础上给出5类死锁的严格定义.

定义1. 混合锁分配图.混合锁分配图G是一个动态的简单图(V(t),E(t))，其中：

1)V(t)和E(t)分别表示在时刻t的顶点和边的集合.

2)V(t)中的顶点分成3类：代表线程的顶点集合T(t)、代表互斥锁的顶点的集合M(t)和代表读写锁的顶点集合RW(t)，显然3个顶点集合中任2个交集为空.

3)E(t)中的每一条边e是一个三元组(v,thd,tp1)或者(thd,v,tp2)，其中v∈M(t)∪RW(t)，thd∈T(t)，tp1∈{wr_held,rd_held}，tp2∈{wr_request,rd_request}.(v,thd,tp1)表示同步设施v正被线程thd以tp1方式占据，(thd,v,tp2)表示线程thd正以tp2方式请求同步设施v.tp1和tp2的取值依规则而定：①若v∈M(t)，则tp1取值wr_held，tp2取值wr_request；②若v∈RW(t)，则tp1取值wr_held当且仅当不存在(v,thr,rd_held)和(v,thr,wr_held)，tp1取值rd_held当且仅当不存在(v,thr,wr_held)，其中thr∈T(t)，tp2取值wr_request或者rd_request.

混合锁分配图根据多线程程序执行的加锁解锁操作而实时更新，当图上出现环时，可以根据环中顶点的类型和边的类型判断其是否代表死锁以及是哪种死锁.假设G中存在一个环p=v1e1v2e2v3…vkekv1，其中1≤k≤min(|V(t)|,|E(t)|)，v1∈(M(t)∪RW(t))，记tp(e)为边e到其类型值的映射.根据G的定义，k必定是偶数.

定义2. 互斥锁死锁.环p代表一个互斥锁死锁当且仅当同时满足3个条件：1)k≥4；2)如果i是奇数，则vi∈M(t)，tp(ei)=wr_held；3)如果i是偶数，则vi∈T(t)，tp(ei)=wr_request.其中1≤i≤k.

定义3. 读写锁死锁.环p代表一个读写锁死锁当且仅当同时满足3个条件：1)k≥4；2)如果i是奇数，令e0为ek，则vi∈RW(t)，且(tp(ei-1)≠rd_request‖tp(ei)≠rd_held)成立；3)如果i是偶数，则vi∈T(t).其中1≤i≤k.条件2要求读写锁顶点的入边和出边不能同时是读类型的边.

定义4. 混合死锁.环p代表一个混合死锁当且仅当同时满足4个条件：1)k≥4；2)存在奇数i和j，使得vi∈M(t)，vj∈RW(t)；3)如果i是奇数，令e0为ek，则(tp(ei-1)≠rd_request‖tp(ei)≠rd_held)成立；4)如果i是偶数，则vi∈T(t).其中1≤i≤k,1≤j≤k.

定义5. 互斥锁自锁.环p代表一个互斥锁自锁当且仅当同时满足3个条件：1)k=2；2)v1∈M(t)，v2∈T(t)；3)tp(e1)=wr_held且tp(e2)=wr_request.

定义6. 读写锁自锁.环p代表一个读写锁自锁当且仅当同时满足3个条件：1)k=2；2)v1∈RW(t)，v2∈T(t)；3)(tp(e2)≠rd_request‖tp(e1)≠rd_held)成立.

2 加锁解锁劫持算法

监视模块Monitor劫持所有互斥锁和读写锁加锁解锁操作，如表2所示，并根据劫持到的操作信息生成相应的事件.

Table 2 LockUnlock Operations on Mutexes and Rwlocks表2 读写锁和互斥锁加锁解锁操作

Table 2 LockUnlock Operations on Mutexes and Rwlocks表2 读写锁和互斥锁加锁解锁操作

LockTypeLock∕UnlockOperationMutexintpthread_mutex_lock(pthread_mutex_t*);intpthread_mutex_trylock(pthread_mutex_t*);intpthread_mutex_timedlock(pthread_mutex_t*,conststructtimespec*);intpthread_mutex_unlock(pthread_mutex_t*);Rwlockintpthread_rwlock_rdlock(pthread_rwlock_t*);intpthread_rwlock_tryrdlock(pthread_rwlock_t*);intpthread_rwlock_wrlock(pthread_rwlock_t*);intpthread_rwlock_trywrlock(pthread_rwlock_t*);intpthread_rwlock_timedrdlock(pthread_rwlock_t*,conststructtimespec*);intpthread_rwlock_timedwrlock(pthread_rwlock_t*,conststructtimespec*);intpthread_rwlock_unlock(pthread_rwlock_t*);

2.1 互斥锁加锁解锁劫持算法

pthread中互斥锁有3种类型：NORMAL，ERRORCHECK，RECURSIVE.不同类型互斥锁的区别在于“未解锁时再次加锁”的执行结果不同：NORMAL互斥锁将使当前线程陷入死锁，ERRORCHECK互斥锁将返回错误代码以指示当前线程已经占据该互斥锁，而RECURSIVE互斥锁则在增加其锁计数后返回成功值.

Monitor在劫持互斥锁的加锁解锁操作时，需要知道正被加锁或者解锁的互斥锁的类型，以根据不同的类型作出不同的反应.然而在pthread中，互斥锁的类型一旦被设置后就无法仅仅从该互斥锁获知其是何种类型.为绕开这个限制，我们参考了互斥锁的内部定义，并依据定义取互斥锁的第4个域的值为互斥锁的类型.这种方法在Linux系统上是可行的，然而可能不具有可移植性.我们建议在其下一版中，pthread应增加一个获取已初始化的互斥锁的类型属性的函数.

互斥锁lock操作的劫持算法分别如算法1所示，其中“gettype”负责如前所述的检索互斥锁类型.

算法1. 互斥锁加锁操作lock劫持算法.

输入: 互斥锁标识符v和线程标识符t；

输出: 整型值，指示t是否成功获取v.

① 设t为当前线程标识符；

② 设v为当前互斥锁标识符；

③typegettype(v)；

④ ift当前持有v{

⑤ iftypeis RECURSIVE{

⑥v.lock_count++；

⑦ return 0；}

⑧ else iftypeis ERRORCHECK{

⑨ returnnative_mutex_lock(v)；}}

⑩ 向t.eq插入事件(t,v,WR_REQUEST)；

而如果线程t当前已经占据v，则劫持算法根据v的类型进行下一步动作(行④～⑩)：1)如果type是RECURSIVE，则将v的锁计数增加1，然后返回0以指示目标程序的加锁调用执行成功(行⑤～⑦)；2)如果type是ERRORCHECK，则返回一个合适的错误代码以指示目标程序的加锁调用执行失败，这通过调用真正加锁操作并返回其结果值来实现(行⑧～⑨)；3)如果type是NORMAL，则线程t将陷入互斥锁自锁状态，故Monitor向t.eq添加WR_REQUEST事件(行⑩)，以便检测模块Linter在将来检测到该自锁.

互斥锁unlock操作的劫持算法分别如算法2所示，其中“gettype”同样负责检索互斥锁类型.

算法2. 互斥锁解锁操作unlock劫持算法.

输入: 互斥锁标识符v和线程标识符t；

输出: 整型值，指示t是否成功释放v.

① 设t为当前线程标识符；

② 设v为当前互斥锁标识符；

③typegettype(v)；

④ ift当前持有v{

⑤ iftypeis RECURSIVE{

⑥v.lock_count--；

⑦ ifv.lock_count≠0 {

⑧ return 0；}}

⑨ 向t.eq插入事件(t,v,RELEASE)；

⑩ returnnative_mutex_unlock(v)；}

Monitor对互斥锁trylock和timedlock操作的劫持算法与算法1类似，为简洁起见不再赘述.

2.2 读写锁加锁解锁劫持算法

pthread中读写锁没有类型之分，因此对读写锁加锁解锁的劫持算法比对互斥锁加锁解锁的劫持算法更简单.读写锁wrlock，rdlock，unlock操作的劫持算法分别如算法3、算法4和算法5所示.

算法3. 读写锁互斥加锁操作wrlock劫持算法.

输入: 读写锁标识符v和线程标识符t；

输出: 整型值，指示t是否成功互斥占据v.

① 设t为当前线程标识符；

② 设v为当前互斥锁标识符；

③ 向t.eq插入事件(t,v,WR_REQUEST)；

④retnative_rwlock_wrlock(v)；

⑤ ifret=0 {

⑥ 向t.eq插入事件(t,v,WR_HELD)；}

⑦ returnret.

算法4. 读写锁共享加锁操作rdlock劫持算法.

输入: 读写锁标识符v和线程标识符t；

输出: 整型值，指示t是否成功共享占据v.

① 设t为当前线程标识符；

② 设v为当前互斥锁标识符；

③ 向t.eq插入事件(t,v,RD_REQUEST)；

④retnative_rwlock_rdlock(v)；

⑤ ifret=0 {

⑥ 向t.eq插入事件(t,v,RD_HELD)；}

⑦ returnret.

算法5. 读写锁解锁操作unlock劫持算法.

输入: 读写锁标识符v和线程标识符t；

输出: 整型值，指示t是否成功释放v.

① 设t为当前线程标识符；

② 设v为当前互斥锁标识符；

③retnative_rwlock_unlock(v)；

④ ifret=0 {

⑤ 向t.eq插入事件(t,v,RELEASE)；}

⑥ returnret.

读写锁互斥加锁操作的劫持算法(算法3)首先向当前线程t的事件队列插入t对当前读写锁v的写请求事件，然后对v调用真正的读写锁互斥加锁操作，只有当其成功执行时才将一个写占据事件插入到t.eq，最后向目标程序返回其返回值.

读写锁共享加锁操作的劫持算法(算法4)与对互斥加锁操作的劫持算法类似，只是将插入事件队列t.eq的写请求和写占据事件改为读请求和读占据事件.而读写锁释放操作的劫持算法(算法5)直接在锁释放成功后向t.eq插入一个锁释放事件.

另外，Monitor对读写锁trywrlock和timedwrlock操作的劫持算法与算法3类似，对读写锁tryrdlock和timedrdlock的劫持算法与算法4类似，不再赘述.

3 混合锁分配图构建和环检测算法

检测模块Linter动态构建和更新混合锁分配图，并负责检测其上是否有死锁环.实际上，检测模块被实现为一个驻留在目标程序进程空间的独立线程，它周期性地(比如0.1 s)休眠和苏醒，以减少对目标程序不必要的干扰.当Linter苏醒时，它从每一个在其休眠期间执行过加锁解锁操作的线程的事件队列中读取事件，并根据这些事件更新MLAG.算法6给出了Linter处理事件和更新MLAG的整体过程.

算法6. 混合锁分配图构建和环检测算法.

输入: 各个线程队列中的事件；

输出: 环集合.

① 设mlag为全局混合锁分配图；

② 令thrs为在Linter休眠期间进行过lockunlock操作的所有线程构成的集合；

③ 令reqthrs为在Linter休眠期间发出过加锁请求但到目前为止仍没有占据相应锁的线程的集合；

④ foreachtinthrs{

⑤ 令num为当前t.eq的长度；

⑥ whilenum≠0 {

⑦num--；

⑧event=dequeue(t.eq)；

⑨ switchevent.type{

⑩ case WR_REQUEST：

在算法6中，对于一个在其休眠期间执行过加锁解锁操作的线程t，Linter首先从t.eq中读取num个事件.这个数字是在Linter正要读取t的事件时确定的(行⑤).由于t.eq是无锁队列①，因此它可能同时被线程t和线程Linter访问和修改.例如当Linter正从t.eq的队尾读取事件时，t可能正将一个新事件添加到t.eq的队头.因此为避免冲突，不管线程t是否向t.eq添加事件，Linter只从队尾读取num个事件.如果t.eq中还有其他事件，Linter会在下一次苏醒期间处理它们.

若已判定完所有环且检测到有死锁环存在，则Linter向目标程序发送SIGSEGV信号并输出所有的死锁环以及每个环中的线程ID和锁ID.程序员可以根据这些信息和操作系统为目标程序生成的转储文件，使用GDB对死锁进行源码级别调试.

4 实验与分析

根据本文提出的检测方法，我们在Linux-3.2.0上开发了一个原型工具Docklinter(实际上是一个动态链接库)，以检测用pthread库编写的多线程CC++程序中的混合死锁.为评估Docklinter的死锁检测能力、对目标程序造成的性能影响和可扩展性，本节通过实验回答3个问题：

1) Docklinter的检测能力如何，即能否准确检测所有互斥锁和读写锁造成的死锁.

2) Docklinter的性能影响如何，即是否会给目标程序造成较大的性能下降.

3) Docklinter的可扩展性如何，即能否在线程数目指数级增长的情况下，其检测开销保持平稳增长.4.1 基准死锁程序集

为回答这些问题，本节使用如表3所示的基准死锁程序集：由作者编写的5个含有不同类型死锁的程序和在死锁检测和死锁规避领域[12-13,22-24]广泛使用的8个死锁程序构成.由于死锁缺陷在正常情况下难以暴露，我们在这10个程序的关键代码点插入usleep语句，以影响程序的线程调度和执行路径，使得死锁以几乎100%的概率暴露出来.

表3列出所有死锁缺陷、相应死锁的程序、死锁缺陷的具体类型(见第1节所述的5类死锁)以及死锁缺陷中包含的死锁环的数量、互斥锁的数量和读写锁的数量.deadlock-mutex-1，deadlock-mutex-2，deadlock-mrwlock-1，deadlock-mrwlock-2，deadlock-mrwlock-3是作者自己编写的死锁程序，分别包含一个互斥锁死锁、一个互斥锁自锁、一个混合死锁、一个读写锁死锁和一个读写锁自锁.bank-transaction，dining-philosophers，sqlite-3.3.3③，hawknl-1.6b3各自包含一个互斥锁死锁缺陷bug#6，bug#7，bug#10，bug#11，其中bug#6中的互斥锁是RECURSIVE类型锁.tgrep和mysql-6.0.4-alpha④则各自包含一个读写锁死锁缺陷.sshfs-fuse-2.2和openldap-2.2.20⑤各自包含一个混合死锁缺陷.注意bug#1，bug#3，bug#4，bug#9都包含多个能够同时存在的死锁环，传统检测方法不能一次性检测到所有死锁环.除bug#10～bug#13外，所有死锁缺陷都可以通过直接运行相应程序进行触发.对bug#10～bug#13，我们编写相应触发用例触发它们.

4.2 实验环境

所有评测和对比实验在下列环境下进行：4核Intel Core 2 Q8200 2.33 GHz CPU、2 GB内存、Ubuntu 12.04操作系统(内核Linux-3.2.0)、GCC 4.6.3编译器.Linter的睡眠周期为0.1 s.

4.3 检测能力评测与对比

为比较Docklinter与已有死锁检测工具的死锁检测能力，我们使用Docklinter和Dimmunix检测在表3中列出的13个死锁缺陷，并对它们的检测能力进行对比.对任何一个死锁，我们对其分别使用Docklinter和Dimmunix检测30次.只要有一次某个工具没有或者没有完全检测到某个死锁的所有死锁环，则我们认为该工具不能检测到该死锁.

为比较Docklinter与已有死锁预测工具的死锁检测能力，我们根据文献[16]重新实现了GoodLock，用它来监视程序执行，劫持线程创建、线程汇合、互斥锁加锁解锁和读写锁加锁解锁共4类操作，并根据收集到的信息建立锁占用图(lock graph)，最后在锁占用图上检测有效环(valid cycle).GoodLock检测到的环就是它预测到的可疑死锁.为让GoodLock顺利监视目标程序运行，我们删除相应缺陷程序中的usleep语句，使得它们的每次运行都不会触发死锁缺陷.如果不这样做，GoodLock可能收集不到足够的信息以进行死锁预测.

Table 3 The Deadlock Program Benchmark Suite表3 基准死锁程序集

DN: # of deadlock cycles, MN: # of mutexes, RWN: # of rwlocks.

死锁检测结果如表4所示，其中√或×后面的数字(mnl)分别表示相应死锁缺陷中的全部死锁环数目m、检测工具检测到的死锁环数目n和检测结果经人工检查确认为真的死锁环数目l.从表4可以看出，Docklinter能成功检测到所有13个不同类型的死锁，包括多个死锁环同时出现的死锁bug#1，bug#3，bug#4，bug#9.Dimmunix不能检测互斥锁自锁(bug#2)、读写锁死锁(bug#4，bug#8，bug#13)、读写锁自锁(bug#5)和混合死锁(bug#3，bug#9，bug#12)，且只能检测到部分互斥锁死锁如bug#6，bug#10，bug#11.Dimmunix不能检测到互斥锁自锁bug#2，是因为它的环检测算法无法检测自环.Dimmunix不能检测读写锁死锁、读写锁自锁和混合死锁，是因为它没有劫持相关读写锁操作，没有能够建立关于程序相对于互斥锁和读写锁的同步状态的抽象表示，也没有在此种抽象表示上检测相应死锁环的算法.

尽管bug#1和bug#7与bug#6，bug#10，bug#11一样都是互斥锁死锁，但Dimmunix无法检测到它们.对于含有2个死锁环的bug#1，Dimmunix只检测出其中的一个死锁环，因此我们认为它不能检测到bug#1.对于单环死锁bug#7，Dimmunix有时能检测到它而有时检测不到它.为查明出现这种现象的原因，我们仔细检查了Dimmunix的源码，发现Dimmunix对用于存储事件的无锁队列的实现存在数据竞争错误.在这种情况下，当多个线程同时读取和修改无锁队列时，一些加锁解锁事件会由于数据竞争而丢失，从而根据无锁队列中的事件构造出来的锁分配图会因缺少或者多出某些边而不能反映目标程序的真实同步状态，这样Dimmunix就可能检测不到某些已经发生的死锁.

Table 4 Deadlock Detection Results of Docklinter,Dimmunix, GoodLock表4 Docklinter，Dimmunix，GoodLock的死锁检测结果

Notes: DR: Detection Results; √: yes; ×: no;mnl: # of totaldetectedconfirmed cycles in a deadlock bug.

Dimmunix的检测模块检测不到bug#1～bug#5，bug#7～bug#9，bug#12，bug#13，从而无法为这些死锁生成特征签名，这导致Dimmunix的规避模块也不能规避这些死锁缺陷.我们修改Dimmunix源码，令其监视表2中列出的所有读写锁加锁解锁操作，建立并更新混合锁分配图MLAG，然后使用本文提出的混合死锁检测方法检测死锁，这样Dimmunix就能检测到表3中列出的所有死锁并生成关于它们的特征签名.根据这些签名，Dimmunix就能够规避除bug#2和bug#5外的其他11个死锁缺陷了.对于互斥锁自锁bug#2和读写锁自锁bug#5，由于它们的发生是在单个线程内进行的，与线程间调度执行顺序没有关系，因此基于线程调度的Dimmunix无法规避它们.

从表4可以看出，GoodLock能根据相应目标程序的一次无死锁执行而预测出除bug#2和bug#5外的所有死锁缺陷.GoodLock不能预测bug#2和bug#5也是因为其环检测算法无法检测自环.GoodLock能预测到包括读写锁死锁和混合死锁在内的其他11个死锁缺陷，令人出乎意料.实际上它并未区分互斥锁和读写锁的不同语义，而是将读写锁等同于互斥锁，将所有对读写锁的共享请求(即rdlock)和互斥请求(即wrlock)都视为互斥请求，这种简单处理反而导致它能检测到bug#3，bug#4，bug#8，bug#9，bug#12，bug#13等读写锁死锁和混合死锁.

然而，不对共享请求和互斥请求进行区分会导致GoodLock报告虚假死锁环信息，例如对bug#3所在的程序deadlock-mrwlock-1，GoodLock报告检测到6个可疑死锁环，然而经分析确认后，只有3个死锁环会真正造成死锁，其他3个死锁环并不会真正导致死锁.图3(a)给出了deadlock-mrwlock-1中一对线程t1和t2的伪代码，当这2个线程按照先t1后t2的顺序执行后，GoodLock会为它们生成如图3(b)所示的锁图，并在其上检测有效环[23]，得到2个死锁环：cycle1=〈(rw1,t1,mtx1),(mtx1,t2,rw1)〉和cycle2=〈(mtx1,t1,mtx2),(mtx2,t2,mtx1)〉.其中cycle1对应的执行场景是：t2先执行L07和L08，然后t1执行L01和L02，最后t2执行L09.对于此执行场景，Docklinter会为其生成如图3(c)所示的混合锁分配图，显然其上存在一个环，然而由于环中读写锁顶点rw1的出边和入边都是rd类型的边，故该环不是死锁环，从而cycle1对应的执行场景不会发生死锁，也即cycle1是虚假死锁环.

Fig. 3 A false deadlock cycle reported by GoodLock图3 GoodLock报告的一个虚假死锁环

另外，即使GoodLock能够意外地预测到读写锁死锁和混合死锁，如果没有Docklinter这样的多类型死锁检测方法，GoodLock也无法确认预测到的死锁到底是否是真正的死锁.因此我们提出的检测死锁方法与GoodLock等预测死锁方法在应用场景上是互补的.

4.4 性能影响评测与分析

为评估Docklinter对目标程序性能的影响，我们选择openldap-2.2.20作为目标程序，编写2个测试用例addent和delent，并分别在对openldap-2.2.20使用和不使用Docklinter的情况下运行这2个测试用例.所有测试用例的运行都不会令openldap-2.2.20的守护进程slapd陷入死锁：虽然openldap-2.2.20中存在并发缺陷bug#12，但我们特意让测试用例按序向slapd发送不同类型的请求，从而有意识地避开了该死锁.

在实验中，我们先运行addent以向slapd发送num个INSERT请求，然后运行delent向slapd发送同等数量同样内容的DELETE请求.我们称addent和delent每次发送的请求数量num为工作量，其可以从2 310变化到111 210，如表5所示.我们为每一个工作量按照如上所述运行addent和delent 30次，统计它们完成工作量所需的平均CPU时间，如表5所示.其中Original表示未使用Docklinter监视运行的原始slapd，Docklinted表示在Docklinter监视下运行的slapd.

Table 5 The Performance Overhead Incurred by Docklinter for openldap-2.2.20表5 Docklinter对openldap-2.2.20造成的性能开销

从表5可以看出，当slapd在Docklinter监视下运行时，addent和delent一般需要更多时间(相对于slapd单独运行时)才能完成某一工作量.但是Docklinter对目标程序的性能影响是可接受的：实验结果表明delent的最大性能下降是10.15%，而addent的最大性能下降仅为8.04%.另外，Docklinter对目标程序的性能影响也不会随着目标程序工作量的增大而单调增长.这是因为Docklinter以异步方式来检测死锁环，而且仅仅为那些发出加锁请求且还没有占据互斥锁的线程检测死锁.只有当大量线程频繁地发出加锁请求而没有占据锁时，Docklinter才会导致较大的开销.

4.5 可扩展性评测与分析

为评估Docklinter的可扩展性，我们仍选择openldap-2.2.20作为目标程序，编写一个测试用例searchent，并分别在对openldap-2.2.20使用和不使用Docklinter的情况下运行这个测试用例.searchent只向slapd发送检索请求，不会触发openldap-2.2.20中的bug#12.

在实验中，我们运行searchent以模拟num_client个客户端向slapd发送20 480个SEARCH请求的应用场景.每个客户端发送请求的数量为20 480num_client.这里一个客户端用一个线程表示，该线程会像独立的客户端一样，通过单独的连接与slapd通信.我们针对每个num_client的取值，运行searchent 30次，统计其平均运行时间，结果如表6所示:

Table 6 The Scalability Results of Docklinter on openldap-2.2.20表6 Docklinter在openldap-2.2.20上的可扩展性实验结果

根据表6，我们可知Docklinter的扩展性良好：Docklinter对目标程序的性能影响随客户端数目的增多而增大，但是增速十分平缓.实验结果表明当2个客户端发送请求时，Docklinter带来31.61%的性能下降，而当客户端数目是32时，Docklinter才导致42.49%的性能下降，甚至当num_client增长到1 002时，Docklinter带来的性能下降也仅仅是125.49%.

5 结 论

本文提出混合锁分配图的概念和构建方法，提出混合锁分配图上的死锁环判定算法，并提出一种基于锁分配图的混合死锁动态检测算法，在此基础上开发了一个原型工具Docklinter，以在混合死锁发生时一次性检测由多个线程和多个互斥锁或者读写锁造成的所有类型死锁.针对13个5种类型的死锁缺陷的死锁缺陷检测结果实验以及在openldap-2.2.20进行的性能影响评估实验和可扩展性测试实验结果表明：Docklinter死锁检测能力强，对目标程序的性能影响较小且扩展性良好.

[1]Su Xiaohong, Yu Zhen, Wang Tiantian, et al. A survey on exposing, detecting and avoiding concurrency bugs[J]. Chinese Journal of Computers, 2015, 38(11): 2215-2233 (in Chinese)(苏小红, 禹振, 王甜甜, 等. 并发缺陷暴露、检测与规避研究综述[J]. 计算机学报, 2015, 38(11): 2215-2233)

[2]Shimomura T, Ikeda K. Two types of deadlock detection: Cyclic and acyclic[J]. Intelligent Systems for Science and Information, 2014, 54(2): 233-259

[3]Fonseca P, Li Cheng, Singhal V, et al. A study of the internal and external effects of concurrency bugs[C]Proc of the 2010 IEEEIFIP Int Conf on Dependable Systems and Networks. Piscataway, NJ: IEEE, 2010: 221-230

[4]Lu Shan, Park S, Seo E, et al. Learning from mistakes: A comprehensive study on real world concurrency bug characteristics[J]. ACM SIGARCH Computer Architecture News, 2008, 36(1): 329-339

[5]Boyapati C, Lee R, Rinard M. Ownership types for safe programming: Preventing data races and deadlocks[J]. ACM SIGPLAN Notices, 2002: 37(11): 211-230

[6]Gordon C S, Ernst M D, Grossman D. Static lock capabilities for deadlock freedom[C]Proc of the 8th ACM SIGPLAN Workshop on Types in Language Design and Implementation. New York: ACM, 2012: 67-78

[7]Naik M, Park C S, Sen K, et al. Effective static deadlock detection[C]Proc of the 31st Int Conf on Software Engineering. New York: ACM, 2009: 386-396

[8]Williams A, Thies W, Ernst M D. Static deadlock detection for Java libraries[C]Proc of the 19th European Conf on Object Oriented Programming. New York: ACM, 2005: 602-629

[9]Engler D, Ashcraft K. RacerX: Efficient, static detection of race conditions and deadlocks[J]. ACM SIGOPS Operating Systems Review, 2005, 37(5): 237-252

[10]Pradel M, Gross T R. Fully automatic and precise detection of thread safety violations[J]. ACM SIGPLAN Notices, 2012, 47(6): 521-530

[11]Joshi P, Park C S, Sen K, et al. A randomized dynamic program analysis technique for detecting real deadlocks[C]Proc of the 2009 ACM SIGPLAN Conf on Programming Language Design and Implementation. New York: ACM, 2009: 110-120

[12]Jula H, Tralamazza D, Zamfir C, et al. Deadlock immunity: Enabling systems to defend against deadlocks[C]Proc of the 8th USENIX Symp on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2008: 295-308

[13]Yu Zhen, Su Xiaohong, Wang Tiantian, et al. Mocklinter: Linting mutual exclusive deadlocks with lock allocation graphs[J]. International Journal of Hybrid Information Technology, 2016, 9(3): 355-374

[14]Koskinen E, Herlihy M. Dreadlocks: Efficient deadlock detection[C]Proc of the 20th Annual Symp on Parallelism in Algorithms and Architectures. New York: ACM, 2008: 297-303

[15]Havelund K. Using runtime analysis to guide model checking of Java programs[C]Proc of 7th Int SPIN Workshop on Model Checking of Software. Berlin: Springer, 2000: 245-264

[16]Bensalem S, Havelund K. Dynamic deadlock analysis of multi-threaded programs[C]Proc of the 1st Int Haifa Verification Conf on Hardware and Software Verification and Testing. Berlin: Springer, 2005: 208-223

[17]Eslamimehr, M, Palsberg, J. Sherlock: Scalable deadlock detection for concurrent programs[C]Proc of the 22nd ACM SIGSOFT Int Symp on Foundations of Software Engineering. New York: ACM, 2014: 353-365

[18]Cai Yan, Chan W K. MagicFuzzer: Scalable deadlock detection for large-scale applications[C]Proc of the 2012 Int Conf on Software Engineering. New York: ACM, 2012: 606-616

[19]Bensalem S, Havelund K. Scalable dynamic deadlock analysis of multi-threaded programs[C]Proc of the 3rd Int Workshop on Parallel and Distributed Systems: Testing and Debugging. New York: ACM, 2005: 1-16

[20]Luo Zhida, Das R, Qi Yao. MulticoreSDK: A practical and efficient deadlock detector for real-world applications[C]Proc of the 4th Int Conf on Software Testing, Verification and Validation. Piscataway, NJ: IEEE, 2011: 309-318

[21]Cai Yan, Chan Wing Kwong. Magiclock: Scalable detection of potential deadlocks in large-scale multithreaded programs[J]. IEEE Trans on Software Engineering, 2014, 40(3): 266-281

[22]Gerakios P, Papaspyrou N, Sagonas K. A type and effect system for deadlock avoidance in low-level languages[C]Proc of the 7th ACM SIGPLAN Workshop on Types in Language Design and Implementation. New York: ACM, 2011: 15-28

[23]Wang Yin, Kelly T, Kudlur M, ea al. Gadara: Dynamic deadlock avoidance for multithreaded programs[C]Proc of the 8th USENIX Symp on Operating Systems Design and

Implementation. Berkeley, CA: USENIX Association, 2008: 281-294

[24]Yu Zhen, Su Xiaohong, Ma Peijun. Scrider: Using single critical sections to avoid deadlocks[C]Proc of the 4th IEEE Int Conf on Instrumentation and Measurement, Computer, Communication and Control. Piscataway, NJ: IEEE, 2014: 1000-1005

Yu Zhen, born in 1987. PhD candidate in the School of Computer Sience and Technology at Harbin Institute of Technology. Student member of CCF. His main research interests include software static or dynamic analysis, implicit rules mining from large-scale software and concurrency bug (including deadlock, data race and atomicity violation) detection and avoidance.

Su Xiaohong, born in 1966. Professor and PhD supervisor in the School of Computer Science and Technology at Harbin Institute of Technology. Senior member of CCF. Her main research interests include software engineering, information fusion, image processing and computer graphics.

Dynamically Detecting Multiple Types of Deadlocks Using Lock Allocation Graphs

Yu Zhen, Su Xiaohong, and Qiu Jing

(SchoolofComputerScienceandTechnology,HarbinInstituteofTechnology,Harbin150001)

Deadlock bugs are hard to expose, reproduce and diagnose. Once happening, they will cause increasing response time, decreasing throughput, or even crash to the target multithreaded programs. However, current deadlock detection techniques can detect only one mutex-caused deadlock at a time. In order to detect all possible deadlocks one time caused by multiple threads and multiple mutexes or rwlocks, this paper proposes the concept of multiple-type lock allocation graph (MLAG) and its construction method. Then a MLAG-based dynamic detection algorithm to detect multiple types of deadlocks is proposed. By instrumenting all lockunlock operations on mutexes and rwlocks, our method dynamically constructs and real-time updates a MLAG which reflects the synchronization state of the target program. Our method detects deadlock bugs by detecting cycles on the MALG and checking whether or not a cycle is a deadlock cycle. When a deadlock is detected, the method outputs information about that bug to assist debugging. The experimental results on benchmarks show that our method is strong in deadlock detection for successfully detecting all 13 deadlock bugs with 5 types, and has a slight impact on target programs for incurring at most 10.15% slowdown to openldap-2.2.20’s performance, and is scalable because the overhead increase gently along with an exponentially increasing number of threads.

dynamic analysis; software testing; concurrency bug detection; deadlock detection; cycle detection

born in 1982.

his PhD degree from Harbin Institute of Technology in 2015. His main research interests include binary code analysis and binary code de-obfuscation.

2016-05-25；

2017-02-06

国家自然科学基金项目(61173021,61672191) This work was supported by the National Natural Science Foundation of China (61173021, 61672191).

苏小红(sxh@hit.edu.cn)

TP311