使用鎖分配圖動態檢測混合死鎖

禹 振 蘇小紅 邱 景

(哈爾濱工業大學計算機科學與技術學院 哈爾濱 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