使用鎖分配圖動態(tài)檢測混合死鎖

禹 振 蘇小紅 邱 景

(哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 哈爾濱 150001)

?

使用鎖分配圖動態(tài)檢測混合死鎖

禹 振 蘇小紅 邱 景

(哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 哈爾濱 150001)

(yuzhen_3301@aliyun.com)

死鎖難以暴露、重演和調(diào)試.一旦發(fā)生，將導(dǎo)致多線程程序響應(yīng)時間增長、吞吐量下降甚至宕機(jī)崩潰.現(xiàn)有死鎖檢測技術(shù)每次只能檢測一個互斥鎖死鎖.為一次性檢測由多個線程和多個互斥鎖或讀寫鎖造成的所有類型死鎖，首先提出混合鎖分配圖的概念和構(gòu)建方法，然后提出一種利用混合鎖分配圖動態(tài)檢測混合死鎖的方法.通過劫持所有互斥鎖和讀寫鎖的加鎖解鎖操作，以動態(tài)構(gòu)建和實時更新一個反映目標(biāo)程序同步狀態(tài)的混合鎖分配圖.通過在鎖分配圖上檢測環(huán)并判定該環(huán)是否為死鎖環(huán)來檢測死鎖.當(dāng)檢測到死鎖時，輸出死鎖信息來輔助調(diào)試.死鎖檢測實驗、性能影響實驗和可擴(kuò)展性實驗結(jié)果表明：該方法成功檢測出所有13個共5種類型的死鎖缺陷，檢測能力強(qiáng)；給openldap-2.2.20帶來至多10.15%的性能下降幅度，對目標(biāo)程序造成的性能影響較小；性能開銷隨線程數(shù)目指數(shù)級增大而平緩增長，擴(kuò)展性良好.

動態(tài)分析；軟件測試；并發(fā)缺陷檢測；死鎖檢測；環(huán)檢測

多線程程序中，一個線程集合中的每一個線程都在各自等待另一個線程占據(jù)的互斥性資源，由此導(dǎo)致的循環(huán)等待即為死鎖.在所有并發(fā)缺陷中[1]，死鎖是其中最常見和最重要的一種：多方統(tǒng)計調(diào)查顯示[2-4]，死鎖缺陷占所有并發(fā)缺陷的30%以上.死鎖一旦發(fā)生，將可能導(dǎo)致多線程程序響應(yīng)時間增長、吞吐量下降甚至宕機(jī)崩潰，嚴(yán)重威脅并發(fā)程序的可用性與可靠性.與其他并發(fā)缺陷一樣，死鎖具有難以暴露、重演和調(diào)試的特點[1]，因此死鎖動態(tài)檢測技術(shù)應(yīng)在死鎖缺陷發(fā)生時立即將其檢測出來，并同時輸出關(guān)于缺陷的相關(guān)信息以輔助調(diào)試.

現(xiàn)有的死鎖檢測技術(shù)可以分為靜態(tài)分析和動態(tài)分析2大類，其中靜態(tài)分析又可以分為類型與效應(yīng)分析和數(shù)據(jù)流分析2類，而動態(tài)分析則可以再分為在線和離線2類，如表1所示：

Table 1 Categories and Summaries of Deadlock Detection Techniques表1 死鎖檢測技術(shù)分類與概述

類型與效應(yīng)分析需要用戶在源碼中為變量或函數(shù)添加類型注釋才能對程序進(jìn)行類型推理和類型檢查，故其人工干預(yù)度高、擴(kuò)展性較差.另外該類技術(shù)沒有考慮讀寫鎖的語義，只能檢查程序是否是免于互斥鎖死鎖的和檢測是否存在互斥鎖死鎖.

數(shù)據(jù)流分析直接分析程序源碼，綜合使用調(diào)用圖分析、上下文分析、指向分析和逃逸分析等靜態(tài)分析技術(shù)，計算靜態(tài)鎖占用約束或鎖占用順序圖，使用約束求解和環(huán)檢測算法在其上檢測環(huán)，將環(huán)作為可能的死鎖報告出來.數(shù)據(jù)流分析缺乏精確的運行時信息，一般對變量值作保守估計，因此其誤檢率較高.同時該類技術(shù)的檢測能力有限，有些技術(shù)如Jade[7]只能檢測2線程互斥鎖死鎖，有些技術(shù)如SDD[8]雖能檢測多線程互斥鎖死鎖，但不能檢測讀寫鎖死鎖和由互斥鎖和讀寫鎖造成的混合死鎖.

動態(tài)分析是目前死鎖檢測的主流技術(shù)，一般分為離線和在線2類.在線方法監(jiān)視程序運行，實時獲取感興趣的信息，建立和更新目標(biāo)程序同步狀態(tài)的抽象表示，并在其上檢測死鎖.離線方法先對程序源碼靜態(tài)插樁，然后執(zhí)行程序并獲取執(zhí)行軌跡，最后分析軌跡，建立鎖占用順序圖，將其上檢測到的環(huán)作為死鎖報告出來.在線方法(GoodLock[15-16]和Sherlock[17]除外，它們可以在線預(yù)測可疑死鎖)一般只能檢測到本次執(zhí)行中實際出現(xiàn)的死鎖，而離線方法則還能“預(yù)測”在其他執(zhí)行中可能出現(xiàn)的死鎖.例如MagicFuzzer[18]和MagicLock[21]根據(jù)本次執(zhí)行中預(yù)測到的死鎖信息，在程序的下一次執(zhí)行中，控制線程調(diào)度，試圖使死鎖暴露出來.相對于在線方法，離線方法誤報率較高，需要存儲執(zhí)行軌跡，對長時間運行的并發(fā)程序不適用.在線分析不需要人工干預(yù)，擴(kuò)展性好，沒有誤報，但其漏報率較高.盡管各有其優(yōu)缺點，但它們都忽略了讀寫鎖可能造成的死鎖，只能檢測互斥鎖死鎖.

Fig. 1 Dynamic detection algorithm to detect multiple types of deadlocks based on MLAGs圖1 基于鎖分配圖的混合死鎖動態(tài)檢測方法

針對現(xiàn)有方法檢測能力有限的問題，為提高現(xiàn)有方法的死鎖檢測能力，以便一次性檢測由多個線程和多個互斥鎖或讀寫鎖造成的所有類型死鎖，本文提出一種基于鎖分配圖的混合死鎖動態(tài)檢測方法，如圖1所示.該方法主要由監(jiān)視模塊Monitor和檢測模塊Linter兩部分組成.監(jiān)視模塊Monitor負(fù)責(zé)劫持所有互斥鎖和讀寫鎖的加鎖解鎖操作，根據(jù)劫持到的信息生成相應(yīng)事件并將事件插入到線程的事件隊列中.可能生成的事件共有5種：鎖互斥請求事件、鎖互斥占據(jù)事件、鎖共享請求事件、鎖共享占據(jù)事件和鎖釋放事件.檢測模塊讀取并根據(jù)這些事件構(gòu)建和更新混合鎖分配圖(multiple-type lock allocation graph, MLAG)，在其上使用強(qiáng)連通分量(strong connected component, SCC)算法檢測環(huán)；如果有死鎖環(huán)存在，則輸出所有的環(huán)以及每個環(huán)中的所有線程ID和鎖ID，并發(fā)送SIGSEGV信號以中止目標(biāo)程序.操作系統(tǒng)將為該目標(biāo)程序生成轉(zhuǎn)儲文件，程序員可以根據(jù)得到的死鎖環(huán)信息和轉(zhuǎn)儲文件，使用GDB進(jìn)行源碼級別調(diào)試，快速理解和定位死鎖的發(fā)生原因和位置.

我們提出的混合死鎖檢測方法有多重應(yīng)用場景：在測試環(huán)境中，它可以配合死鎖暴露技術(shù)來檢測和驗證死鎖；在生產(chǎn)環(huán)境中，死鎖規(guī)避技術(shù)可以使用它檢測更多類型和更多數(shù)量的死鎖，從而得到關(guān)于這些死鎖的特征信息，以指導(dǎo)規(guī)避邏輯規(guī)避更多類型和更多數(shù)量的死鎖.

1 檢測對象與死鎖環(huán)判定算法

多線程程序中，pthread庫中2種同步設(shè)施互斥鎖和讀寫鎖的使用頻率都很高.程序員通常使用互斥鎖來保護(hù)只允許讀寫操作互斥執(zhí)行的共享變量，而對于允許多個讀操作同時執(zhí)行但寫操作互斥執(zhí)行的同步場景，為提高性能程序員往往使用讀寫鎖而不是互斥鎖.因此本文試圖檢測由互斥鎖和讀寫鎖造成的5類死鎖：互斥鎖造成的死鎖、讀寫鎖造成的死鎖、互斥鎖和讀寫鎖造成的混合死鎖混合死鎖、互斥鎖自鎖和讀寫鎖自鎖，如圖2所示：

Fig. 2 Five deadlock scenarios caused by mutex and rwlock圖2 互斥鎖和讀寫鎖造成的5種死鎖場景

互斥鎖與讀寫鎖的區(qū)別是：互斥鎖在任何時刻只能被至多一個線程占據(jù)，因此任何線程對互斥鎖的占據(jù)和請求都是互斥占據(jù)和互斥請求；讀寫鎖在任何時刻可被多個線程同時讀占據(jù)，但只能被至多一個線程寫占據(jù)，因此對讀寫鎖的占據(jù)和請求各自分為2類，即共享占據(jù)與互斥占據(jù)和共享請求與互斥請求.本文將對鎖(不論互斥鎖還是讀寫鎖)的互斥占據(jù)和互斥請求稱為寫占據(jù)和寫請求，將對鎖的共享占據(jù)和共享請求稱為讀占據(jù)和讀請求.圖2中用不同的線型和標(biāo)簽標(biāo)示這4種操作.

本文定義混合鎖分配圖MLAG以表征多線程程序相對于互斥鎖和讀寫鎖的同步狀態(tài)，并在此基礎(chǔ)上給出5類死鎖的嚴(yán)格定義.

定義1. 混合鎖分配圖.混合鎖分配圖G是一個動態(tài)的簡單圖(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)表示同步設(shè)施v正被線程thd以tp1方式占據(jù)，(thd,v,tp2)表示線程thd正以tp2方式請求同步設(shè)施v.tp1和tp2的取值依規(guī)則而定：①若v∈M(t)，則tp1取值wr_held，tp2取值wr_request；②若v∈RW(t)，則tp1取值wr_held當(dāng)且僅當(dāng)不存在(v,thr,rd_held)和(v,thr,wr_held)，tp1取值rd_held當(dāng)且僅當(dāng)不存在(v,thr,wr_held)，其中thr∈T(t)，tp2取值wr_request或者rd_request.

混合鎖分配圖根據(jù)多線程程序執(zhí)行的加鎖解鎖操作而實時更新，當(dāng)圖上出現(xiàn)環(huán)時，可以根據(jù)環(huán)中頂點的類型和邊的類型判斷其是否代表死鎖以及是哪種死鎖.假設(shè)G中存在一個環(huán)p=v1e1v2e2v3…vkekv1，其中1≤k≤min(|V(t)|,|E(t)|)，v1∈(M(t)∪RW(t))，記tp(e)為邊e到其類型值的映射.根據(jù)G的定義，k必定是偶數(shù).

定義2. 互斥鎖死鎖.環(huán)p代表一個互斥鎖死鎖當(dāng)且僅當(dāng)同時滿足3個條件：1)k≥4；2)如果i是奇數(shù)，則vi∈M(t)，tp(ei)=wr_held；3)如果i是偶數(shù)，則vi∈T(t)，tp(ei)=wr_request.其中1≤i≤k.

定義3. 讀寫鎖死鎖.環(huán)p代表一個讀寫鎖死鎖當(dāng)且僅當(dāng)同時滿足3個條件：1)k≥4；2)如果i是奇數(shù)，令e0為ek，則vi∈RW(t)，且(tp(ei-1)≠rd_request‖tp(ei)≠rd_held)成立；3)如果i是偶數(shù)，則vi∈T(t).其中1≤i≤k.條件2要求讀寫鎖頂點的入邊和出邊不能同時是讀類型的邊.

定義4. 混合死鎖.環(huán)p代表一個混合死鎖當(dāng)且僅當(dāng)同時滿足4個條件：1)k≥4；2)存在奇數(shù)i和j，使得vi∈M(t)，vj∈RW(t)；3)如果i是奇數(shù)，令e0為ek，則(tp(ei-1)≠rd_request‖tp(ei)≠rd_held)成立；4)如果i是偶數(shù)，則vi∈T(t).其中1≤i≤k,1≤j≤k.

定義5. 互斥鎖自鎖.環(huán)p代表一個互斥鎖自鎖當(dāng)且僅當(dāng)同時滿足3個條件：1)k=2；2)v1∈M(t)，v2∈T(t)；3)tp(e1)=wr_held且tp(e2)=wr_request.

定義6. 讀寫鎖自鎖.環(huán)p代表一個讀寫鎖自鎖當(dāng)且僅當(dāng)同時滿足3個條件：1)k=2；2)v1∈RW(t)，v2∈T(t)；3)(tp(e2)≠rd_request‖tp(e1)≠rd_held)成立.

2 加鎖解鎖劫持算法

監(jiān)視模塊Monitor劫持所有互斥鎖和讀寫鎖加鎖解鎖操作，如表2所示，并根據(jù)劫持到的操作信息生成相應(yīng)的事件.

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.不同類型互斥鎖的區(qū)別在于“未解鎖時再次加鎖”的執(zhí)行結(jié)果不同：NORMAL互斥鎖將使當(dāng)前線程陷入死鎖，ERRORCHECK互斥鎖將返回錯誤代碼以指示當(dāng)前線程已經(jīng)占據(jù)該互斥鎖，而RECURSIVE互斥鎖則在增加其鎖計數(shù)后返回成功值.

Monitor在劫持互斥鎖的加鎖解鎖操作時，需要知道正被加鎖或者解鎖的互斥鎖的類型，以根據(jù)不同的類型作出不同的反應(yīng).然而在pthread中，互斥鎖的類型一旦被設(shè)置后就無法僅僅從該互斥鎖獲知其是何種類型.為繞開這個限制，我們參考了互斥鎖的內(nèi)部定義，并依據(jù)定義取互斥鎖的第4個域的值為互斥鎖的類型.這種方法在Linux系統(tǒng)上是可行的，然而可能不具有可移植性.我們建議在其下一版中，pthread應(yīng)增加一個獲取已初始化的互斥鎖的類型屬性的函數(shù).

互斥鎖lock操作的劫持算法分別如算法1所示，其中“gettype”負(fù)責(zé)如前所述的檢索互斥鎖類型.

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

輸入: 互斥鎖標(biāo)識符v和線程標(biāo)識符t；

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

① 設(shè)t為當(dāng)前線程標(biāo)識符；

② 設(shè)v為當(dāng)前互斥鎖標(biāo)識符；

③typegettype(v)；

④ ift當(dāng)前持有v{

⑤ iftypeis RECURSIVE{

⑥v.lock_count++；

⑦ return 0；}

⑧ else iftypeis ERRORCHECK{

⑨ returnnative_mutex_lock(v)；}}

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

而如果線程t當(dāng)前已經(jīng)占據(jù)v，則劫持算法根據(jù)v的類型進(jìn)行下一步動作(行④～⑩)：1)如果type是RECURSIVE，則將v的鎖計數(shù)增加1，然后返回0以指示目標(biāo)程序的加鎖調(diào)用執(zhí)行成功(行⑤～⑦)；2)如果type是ERRORCHECK，則返回一個合適的錯誤代碼以指示目標(biāo)程序的加鎖調(diào)用執(zhí)行失敗，這通過調(diào)用真正加鎖操作并返回其結(jié)果值來實現(xiàn)(行⑧～⑨)；3)如果type是NORMAL，則線程t將陷入互斥鎖自鎖狀態(tài)，故Monitor向t.eq添加WR_REQUEST事件(行⑩)，以便檢測模塊Linter在將來檢測到該自鎖.

互斥鎖unlock操作的劫持算法分別如算法2所示，其中“gettype”同樣負(fù)責(zé)檢索互斥鎖類型.

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

輸入: 互斥鎖標(biāo)識符v和線程標(biāo)識符t；

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

① 設(shè)t為當(dāng)前線程標(biāo)識符；

② 設(shè)v為當(dāng)前互斥鎖標(biāo)識符；

③typegettype(v)；

④ ift當(dāng)前持有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劫持算法.

輸入: 讀寫鎖標(biāo)識符v和線程標(biāo)識符t；

輸出: 整型值，指示t是否成功互斥占據(jù)v.

① 設(shè)t為當(dāng)前線程標(biāo)識符；

② 設(shè)v為當(dāng)前互斥鎖標(biāo)識符；

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

④retnative_rwlock_wrlock(v)；

⑤ ifret=0 {

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

⑦ returnret.

算法4. 讀寫鎖共享加鎖操作rdlock劫持算法.

輸入: 讀寫鎖標(biāo)識符v和線程標(biāo)識符t；

輸出: 整型值，指示t是否成功共享占據(jù)v.

① 設(shè)t為當(dāng)前線程標(biāo)識符；

② 設(shè)v為當(dāng)前互斥鎖標(biāo)識符；

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

④retnative_rwlock_rdlock(v)；

⑤ ifret=0 {

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

⑦ returnret.

算法5. 讀寫鎖解鎖操作unlock劫持算法.

輸入: 讀寫鎖標(biāo)識符v和線程標(biāo)識符t；

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

① 設(shè)t為當(dāng)前線程標(biāo)識符；

② 設(shè)v為當(dāng)前互斥鎖標(biāo)識符；

③retnative_rwlock_unlock(v)；

④ ifret=0 {

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

⑥ returnret.

讀寫鎖互斥加鎖操作的劫持算法(算法3)首先向當(dāng)前線程t的事件隊列插入t對當(dāng)前讀寫鎖v的寫請求事件，然后對v調(diào)用真正的讀寫鎖互斥加鎖操作，只有當(dāng)其成功執(zhí)行時才將一個寫占據(jù)事件插入到t.eq，最后向目標(biāo)程序返回其返回值.

讀寫鎖共享加鎖操作的劫持算法(算法4)與對互斥加鎖操作的劫持算法類似，只是將插入事件隊列t.eq的寫請求和寫占據(jù)事件改為讀請求和讀占據(jù)事件.而讀寫鎖釋放操作的劫持算法(算法5)直接在鎖釋放成功后向t.eq插入一個鎖釋放事件.

另外，Monitor對讀寫鎖trywrlock和timedwrlock操作的劫持算法與算法3類似，對讀寫鎖tryrdlock和timedrdlock的劫持算法與算法4類似，不再贅述.

3 混合鎖分配圖構(gòu)建和環(huán)檢測算法

檢測模塊Linter動態(tài)構(gòu)建和更新混合鎖分配圖，并負(fù)責(zé)檢測其上是否有死鎖環(huán).實際上，檢測模塊被實現(xiàn)為一個駐留在目標(biāo)程序進(jìn)程空間的獨立線程，它周期性地(比如0.1 s)休眠和蘇醒，以減少對目標(biāo)程序不必要的干擾.當(dāng)Linter蘇醒時，它從每一個在其休眠期間執(zhí)行過加鎖解鎖操作的線程的事件隊列中讀取事件，并根據(jù)這些事件更新MLAG.算法6給出了Linter處理事件和更新MLAG的整體過程.

算法6. 混合鎖分配圖構(gòu)建和環(huán)檢測算法.

輸入: 各個線程隊列中的事件；

輸出: 環(huán)集合.

① 設(shè)mlag為全局混合鎖分配圖；

② 令thrs為在Linter休眠期間進(jìn)行過lockunlock操作的所有線程構(gòu)成的集合；

③ 令reqthrs為在Linter休眠期間發(fā)出過加鎖請求但到目前為止仍沒有占據(jù)相應(yīng)鎖的線程的集合；

④ foreachtinthrs{

⑤ 令num為當(dāng)前t.eq的長度；

⑥ whilenum≠0 {

⑦num--；

⑧event=dequeue(t.eq)；

⑨ switchevent.type{

⑩ case WR_REQUEST：

在算法6中，對于一個在其休眠期間執(zhí)行過加鎖解鎖操作的線程t，Linter首先從t.eq中讀取num個事件.這個數(shù)字是在Linter正要讀取t的事件時確定的(行⑤).由于t.eq是無鎖隊列①，因此它可能同時被線程t和線程Linter訪問和修改.例如當(dāng)Linter正從t.eq的隊尾讀取事件時，t可能正將一個新事件添加到t.eq的隊頭.因此為避免沖突，不管線程t是否向t.eq添加事件，Linter只從隊尾讀取num個事件.如果t.eq中還有其他事件，Linter會在下一次蘇醒期間處理它們.

若已判定完所有環(huán)且檢測到有死鎖環(huán)存在，則Linter向目標(biāo)程序發(fā)送SIGSEGV信號并輸出所有的死鎖環(huán)以及每個環(huán)中的線程ID和鎖ID.程序員可以根據(jù)這些信息和操作系統(tǒng)為目標(biāo)程序生成的轉(zhuǎn)儲文件，使用GDB對死鎖進(jìn)行源碼級別調(diào)試.

4 實驗與分析

根據(jù)本文提出的檢測方法，我們在Linux-3.2.0上開發(fā)了一個原型工具Docklinter(實際上是一個動態(tài)鏈接庫)，以檢測用pthread庫編寫的多線程CC++程序中的混合死鎖.為評估Docklinter的死鎖檢測能力、對目標(biāo)程序造成的性能影響和可擴(kuò)展性，本節(jié)通過實驗回答3個問題：

1) Docklinter的檢測能力如何，即能否準(zhǔn)確檢測所有互斥鎖和讀寫鎖造成的死鎖.

2) Docklinter的性能影響如何，即是否會給目標(biāo)程序造成較大的性能下降.

3) Docklinter的可擴(kuò)展性如何，即能否在線程數(shù)目指數(shù)級增長的情況下，其檢測開銷保持平穩(wěn)增長.4.1 基準(zhǔn)死鎖程序集

為回答這些問題，本節(jié)使用如表3所示的基準(zhǔn)死鎖程序集：由作者編寫的5個含有不同類型死鎖的程序和在死鎖檢測和死鎖規(guī)避領(lǐng)域[12-13,22-24]廣泛使用的8個死鎖程序構(gòu)成.由于死鎖缺陷在正常情況下難以暴露，我們在這10個程序的關(guān)鍵代碼點插入usleep語句，以影響程序的線程調(diào)度和執(zhí)行路徑，使得死鎖以幾乎100%的概率暴露出來.

表3列出所有死鎖缺陷、相應(yīng)死鎖的程序、死鎖缺陷的具體類型(見第1節(jié)所述的5類死鎖)以及死鎖缺陷中包含的死鎖環(huán)的數(shù)量、互斥鎖的數(shù)量和讀寫鎖的數(shù)量.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都包含多個能夠同時存在的死鎖環(huán)，傳統(tǒng)檢測方法不能一次性檢測到所有死鎖環(huán).除bug#10～bug#13外，所有死鎖缺陷都可以通過直接運行相應(yīng)程序進(jìn)行觸發(fā).對bug#10～bug#13，我們編寫相應(yīng)觸發(fā)用例觸發(fā)它們.

4.2 實驗環(huán)境

所有評測和對比實驗在下列環(huán)境下進(jìn)行：4核Intel Core 2 Q8200 2.33 GHz CPU、2 GB內(nèi)存、Ubuntu 12.04操作系統(tǒng)(內(nèi)核Linux-3.2.0)、GCC 4.6.3編譯器.Linter的睡眠周期為0.1 s.

4.3 檢測能力評測與對比

為比較Docklinter與已有死鎖檢測工具的死鎖檢測能力，我們使用Docklinter和Dimmunix檢測在表3中列出的13個死鎖缺陷，并對它們的檢測能力進(jìn)行對比.對任何一個死鎖，我們對其分別使用Docklinter和Dimmunix檢測30次.只要有一次某個工具沒有或者沒有完全檢測到某個死鎖的所有死鎖環(huán)，則我們認(rèn)為該工具不能檢測到該死鎖.

為比較Docklinter與已有死鎖預(yù)測工具的死鎖檢測能力，我們根據(jù)文獻(xiàn)[16]重新實現(xiàn)了GoodLock，用它來監(jiān)視程序執(zhí)行，劫持線程創(chuàng)建、線程匯合、互斥鎖加鎖解鎖和讀寫鎖加鎖解鎖共4類操作，并根據(jù)收集到的信息建立鎖占用圖(lock graph)，最后在鎖占用圖上檢測有效環(huán)(valid cycle).GoodLock檢測到的環(huán)就是它預(yù)測到的可疑死鎖.為讓GoodLock順利監(jiān)視目標(biāo)程序運行，我們刪除相應(yīng)缺陷程序中的usleep語句，使得它們的每次運行都不會觸發(fā)死鎖缺陷.如果不這樣做，GoodLock可能收集不到足夠的信息以進(jìn)行死鎖預(yù)測.

Table 3 The Deadlock Program Benchmark Suite表3 基準(zhǔn)死鎖程序集

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

死鎖檢測結(jié)果如表4所示，其中√或×后面的數(shù)字(mnl)分別表示相應(yīng)死鎖缺陷中的全部死鎖環(huán)數(shù)目m、檢測工具檢測到的死鎖環(huán)數(shù)目n和檢測結(jié)果經(jīng)人工檢查確認(rèn)為真的死鎖環(huán)數(shù)目l.從表4可以看出，Docklinter能成功檢測到所有13個不同類型的死鎖，包括多個死鎖環(huán)同時出現(xiàn)的死鎖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，是因為它的環(huán)檢測算法無法檢測自環(huán).Dimmunix不能檢測讀寫鎖死鎖、讀寫鎖自鎖和混合死鎖，是因為它沒有劫持相關(guān)讀寫鎖操作，沒有能夠建立關(guān)于程序相對于互斥鎖和讀寫鎖的同步狀態(tài)的抽象表示，也沒有在此種抽象表示上檢測相應(yīng)死鎖環(huán)的算法.

盡管bug#1和bug#7與bug#6，bug#10，bug#11一樣都是互斥鎖死鎖，但Dimmunix無法檢測到它們.對于含有2個死鎖環(huán)的bug#1，Dimmunix只檢測出其中的一個死鎖環(huán)，因此我們認(rèn)為它不能檢測到bug#1.對于單環(huán)死鎖bug#7，Dimmunix有時能檢測到它而有時檢測不到它.為查明出現(xiàn)這種現(xiàn)象的原因，我們仔細(xì)檢查了Dimmunix的源碼，發(fā)現(xiàn)Dimmunix對用于存儲事件的無鎖隊列的實現(xiàn)存在數(shù)據(jù)競爭錯誤.在這種情況下，當(dāng)多個線程同時讀取和修改無鎖隊列時，一些加鎖解鎖事件會由于數(shù)據(jù)競爭而丟失，從而根據(jù)無鎖隊列中的事件構(gòu)造出來的鎖分配圖會因缺少或者多出某些邊而不能反映目標(biāo)程序的真實同步狀態(tài)，這樣Dimmunix就可能檢測不到某些已經(jīng)發(fā)生的死鎖.

Table 4 Deadlock Detection Results of Docklinter,Dimmunix, GoodLock表4 Docklinter，Dimmunix，GoodLock的死鎖檢測結(jié)果

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，從而無法為這些死鎖生成特征簽名，這導(dǎo)致Dimmunix的規(guī)避模塊也不能規(guī)避這些死鎖缺陷.我們修改Dimmunix源碼，令其監(jiān)視表2中列出的所有讀寫鎖加鎖解鎖操作，建立并更新混合鎖分配圖MLAG，然后使用本文提出的混合死鎖檢測方法檢測死鎖，這樣Dimmunix就能檢測到表3中列出的所有死鎖并生成關(guān)于它們的特征簽名.根據(jù)這些簽名，Dimmunix就能夠規(guī)避除bug#2和bug#5外的其他11個死鎖缺陷了.對于互斥鎖自鎖bug#2和讀寫鎖自鎖bug#5，由于它們的發(fā)生是在單個線程內(nèi)進(jìn)行的，與線程間調(diào)度執(zhí)行順序沒有關(guān)系，因此基于線程調(diào)度的Dimmunix無法規(guī)避它們.

從表4可以看出，GoodLock能根據(jù)相應(yīng)目標(biāo)程序的一次無死鎖執(zhí)行而預(yù)測出除bug#2和bug#5外的所有死鎖缺陷.GoodLock不能預(yù)測bug#2和bug#5也是因為其環(huán)檢測算法無法檢測自環(huán).GoodLock能預(yù)測到包括讀寫鎖死鎖和混合死鎖在內(nèi)的其他11個死鎖缺陷，令人出乎意料.實際上它并未區(qū)分互斥鎖和讀寫鎖的不同語義，而是將讀寫鎖等同于互斥鎖，將所有對讀寫鎖的共享請求(即rdlock)和互斥請求(即wrlock)都視為互斥請求，這種簡單處理反而導(dǎo)致它能檢測到bug#3，bug#4，bug#8，bug#9，bug#12，bug#13等讀寫鎖死鎖和混合死鎖.

然而，不對共享請求和互斥請求進(jìn)行區(qū)分會導(dǎo)致GoodLock報告虛假死鎖環(huán)信息，例如對bug#3所在的程序deadlock-mrwlock-1，GoodLock報告檢測到6個可疑死鎖環(huán)，然而經(jīng)分析確認(rèn)后，只有3個死鎖環(huán)會真正造成死鎖，其他3個死鎖環(huán)并不會真正導(dǎo)致死鎖.圖3(a)給出了deadlock-mrwlock-1中一對線程t1和t2的偽代碼，當(dāng)這2個線程按照先t1后t2的順序執(zhí)行后，GoodLock會為它們生成如圖3(b)所示的鎖圖，并在其上檢測有效環(huán)[23]，得到2個死鎖環(huán)：cycle1=〈(rw1,t1,mtx1),(mtx1,t2,rw1)〉和cycle2=〈(mtx1,t1,mtx2),(mtx2,t2,mtx1)〉.其中cycle1對應(yīng)的執(zhí)行場景是：t2先執(zhí)行L07和L08，然后t1執(zhí)行L01和L02，最后t2執(zhí)行L09.對于此執(zhí)行場景，Docklinter會為其生成如圖3(c)所示的混合鎖分配圖，顯然其上存在一個環(huán)，然而由于環(huán)中讀寫鎖頂點rw1的出邊和入邊都是rd類型的邊，故該環(huán)不是死鎖環(huán)，從而cycle1對應(yīng)的執(zhí)行場景不會發(fā)生死鎖，也即cycle1是虛假死鎖環(huán).

Fig. 3 A false deadlock cycle reported by GoodLock圖3 GoodLock報告的一個虛假死鎖環(huán)

另外，即使GoodLock能夠意外地預(yù)測到讀寫鎖死鎖和混合死鎖，如果沒有Docklinter這樣的多類型死鎖檢測方法，GoodLock也無法確認(rèn)預(yù)測到的死鎖到底是否是真正的死鎖.因此我們提出的檢測死鎖方法與GoodLock等預(yù)測死鎖方法在應(yīng)用場景上是互補(bǔ)的.

4.4 性能影響評測與分析

為評估Docklinter對目標(biāo)程序性能的影響，我們選擇openldap-2.2.20作為目標(biāo)程序，編寫2個測試用例addent和delent，并分別在對openldap-2.2.20使用和不使用Docklinter的情況下運行這2個測試用例.所有測試用例的運行都不會令openldap-2.2.20的守護(hù)進(jìn)程slapd陷入死鎖：雖然openldap-2.2.20中存在并發(fā)缺陷bug#12，但我們特意讓測試用例按序向slapd發(fā)送不同類型的請求，從而有意識地避開了該死鎖.

在實驗中，我們先運行addent以向slapd發(fā)送num個INSERT請求，然后運行delent向slapd發(fā)送同等數(shù)量同樣內(nèi)容的DELETE請求.我們稱addent和delent每次發(fā)送的請求數(shù)量num為工作量，其可以從2 310變化到111 210，如表5所示.我們?yōu)槊恳粋€工作量按照如上所述運行addent和delent 30次，統(tǒng)計它們完成工作量所需的平均CPU時間，如表5所示.其中Original表示未使用Docklinter監(jiān)視運行的原始slapd，Docklinted表示在Docklinter監(jiān)視下運行的slapd.

Table 5 The Performance Overhead Incurred by Docklinter for openldap-2.2.20表5 Docklinter對openldap-2.2.20造成的性能開銷

從表5可以看出，當(dāng)slapd在Docklinter監(jiān)視下運行時，addent和delent一般需要更多時間(相對于slapd單獨運行時)才能完成某一工作量.但是Docklinter對目標(biāo)程序的性能影響是可接受的：實驗結(jié)果表明delent的最大性能下降是10.15%，而addent的最大性能下降僅為8.04%.另外，Docklinter對目標(biāo)程序的性能影響也不會隨著目標(biāo)程序工作量的增大而單調(diào)增長.這是因為Docklinter以異步方式來檢測死鎖環(huán)，而且僅僅為那些發(fā)出加鎖請求且還沒有占據(jù)互斥鎖的線程檢測死鎖.只有當(dāng)大量線程頻繁地發(fā)出加鎖請求而沒有占據(jù)鎖時，Docklinter才會導(dǎo)致較大的開銷.

4.5 可擴(kuò)展性評測與分析

為評估Docklinter的可擴(kuò)展性，我們?nèi)赃x擇openldap-2.2.20作為目標(biāo)程序，編寫一個測試用例searchent，并分別在對openldap-2.2.20使用和不使用Docklinter的情況下運行這個測試用例.searchent只向slapd發(fā)送檢索請求，不會觸發(fā)openldap-2.2.20中的bug#12.

在實驗中，我們運行searchent以模擬num_client個客戶端向slapd發(fā)送20 480個SEARCH請求的應(yīng)用場景.每個客戶端發(fā)送請求的數(shù)量為20 480num_client.這里一個客戶端用一個線程表示，該線程會像獨立的客戶端一樣，通過單獨的連接與slapd通信.我們針對每個num_client的取值，運行searchent 30次，統(tǒng)計其平均運行時間，結(jié)果如表6所示:

Table 6 The Scalability Results of Docklinter on openldap-2.2.20表6 Docklinter在openldap-2.2.20上的可擴(kuò)展性實驗結(jié)果

根據(jù)表6，我們可知Docklinter的擴(kuò)展性良好：Docklinter對目標(biāo)程序的性能影響隨客戶端數(shù)目的增多而增大，但是增速十分平緩.實驗結(jié)果表明當(dāng)2個客戶端發(fā)送請求時，Docklinter帶來31.61%的性能下降，而當(dāng)客戶端數(shù)目是32時，Docklinter才導(dǎo)致42.49%的性能下降，甚至當(dāng)num_client增長到1 002時，Docklinter帶來的性能下降也僅僅是125.49%.

5 結(jié) 論

本文提出混合鎖分配圖的概念和構(gòu)建方法，提出混合鎖分配圖上的死鎖環(huán)判定算法，并提出一種基于鎖分配圖的混合死鎖動態(tài)檢測算法，在此基礎(chǔ)上開發(fā)了一個原型工具Docklinter，以在混合死鎖發(fā)生時一次性檢測由多個線程和多個互斥鎖或者讀寫鎖造成的所有類型死鎖.針對13個5種類型的死鎖缺陷的死鎖缺陷檢測結(jié)果實驗以及在openldap-2.2.20進(jìn)行的性能影響評估實驗和可擴(kuò)展性測試實驗結(jié)果表明：Docklinter死鎖檢測能力強(qiáng)，對目標(biāo)程序的性能影響較小且擴(kuò)展性良好.

[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)(蘇小紅, 禹振, 王甜甜, 等. 并發(fā)缺陷暴露、檢測與規(guī)避研究綜述[J]. 計算機(jī)學(xué)報, 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

國家自然科學(xué)基金項目(61173021,61672191) This work was supported by the National Natural Science Foundation of China (61173021, 61672191).

蘇小紅(sxh@hit.edu.cn)

TP311