基于未來鎖集的死鎖規(guī)避

禹 振 蘇小紅 齊 鵬 馬培軍

(哈爾濱工業(yè)大學計算機科學與技術(shù)學院 哈爾濱 150001) (yuzhen_3301@aliyun.com)

基于未來鎖集的死鎖規(guī)避

禹 振 蘇小紅 齊 鵬 馬培軍

(哈爾濱工業(yè)大學計算機科學與技術(shù)學院 哈爾濱 150001) (yuzhen_3301@aliyun.com)

針對現(xiàn)有動態(tài)死鎖規(guī)避方法存在能力有限、被動盲目、開銷較大和影響目標程序正確性等問題，提出一種基于未來鎖集的動靜結(jié)合死鎖規(guī)避方案Flider.基本思想是，對于一個加鎖操作，若其未來鎖集中的所有鎖都是空閑的，則執(zhí)行該加鎖操作不會導致死鎖.一個加鎖操作的未來鎖集包括當前要加鎖的鎖和從該加鎖操作到與之相對應的解鎖操作過程中遇到的所有加鎖操作所要加的鎖.通過靜態(tài)分析，計算鎖效應信息并插樁到相應的加鎖操作和函數(shù)調(diào)用操作前后.通過動態(tài)分析，劫持加鎖操作，根據(jù)其鎖效應信息為之計算未來鎖集，只有當未來鎖集中的所有鎖都未被鎖定才執(zhí)行該加鎖操作，否則等待.測評實驗和對比實驗表明Flider能智能主動地規(guī)避多種類型死鎖，開銷較小，擴展性好，不影響程序正確性.

并發(fā)缺陷；并發(fā)測試；死鎖；死鎖檢測；死鎖規(guī)避；未來鎖集

多線程程序中，如果某線程集合中的每一個線程都在等待另一個線程占據(jù)的互斥性資源，或者等待一個不可能發(fā)生的信號，則由此導致的循環(huán)等待或者無限等待即為死鎖.死鎖一般由互斥鎖、讀寫鎖、條件變量、信號量甚至線程柵欄造成[1-2].互斥鎖和讀寫鎖通常導致有環(huán)死鎖，而條件變量、信號量和線程柵欄則能夠?qū)е聼o環(huán)死鎖[3].本文只研究有環(huán)死鎖.

多方統(tǒng)計調(diào)查顯示[3-5]，死鎖缺陷占所有并發(fā)缺陷的30%以上，嚴重威脅并發(fā)程序的可用性和可靠性.與其他并發(fā)缺陷一樣，死鎖具有難以檢測、難以調(diào)試和難以修復的特點[6]，且其經(jīng)常在多個線程按照相反的順序請求某些資源或者等待某個信號的罕見執(zhí)行交錯下發(fā)生.死鎖難以檢測、調(diào)試和修復而又僅在罕見的執(zhí)行交錯下才暴露出來，因此如果合理安排線程請求資源或者等待信號的順序，避開那些包含死鎖的執(zhí)行交錯，則即使多線程程序中存在死鎖，也不會被觸發(fā)進而影響程序執(zhí)行正確性，此即死鎖規(guī)避.通常使用執(zhí)行控制方法在目標程序運行時動態(tài)規(guī)避死鎖.

目前研究者們已提出多種方法規(guī)避死鎖，較為著名和代表較新水平的有Dimmunix[7]，Glock[8]，Sammati[9]，Grace[10]，F(xiàn)lock[11]和Scrider[12]等.Dimmunix先檢測死鎖，并記錄導致死鎖的線程的棧幀作為死鎖的簽名，然后在并發(fā)程序下次運行時，有意識地控制線程調(diào)度，阻止相關(guān)線程再次進入相應的棧幀，避免已遇到的死鎖再次發(fā)生.Dimmunix離線規(guī)避死鎖，而Glock在線規(guī)避死鎖.Glock檢測潛在的死鎖環(huán)并在該死鎖環(huán)對應的代碼段前添加門鎖，使這些代碼段互斥執(zhí)行以規(guī)避死鎖.Sammati和Grace都使用基于軟件事務內(nèi)存的回滾重新執(zhí)行技術(shù)規(guī)避死鎖，但：1)事務粒度不同，Sammati以關(guān)鍵區(qū)為粒度，而Grace以2個線程交互操作(如線程開始線程創(chuàng)建、線程開始線程結(jié)束和線程開始信號發(fā)送等)之間的代碼段為粒度；2)規(guī)避方式不同，Sammati保持互斥鎖語義，在對互斥鎖加鎖時檢測是否有死鎖環(huán)存在，如果存在，則在死鎖環(huán)中尋找導致當前加鎖操作死鎖的鎖，將當前線程的執(zhí)行回退到對該鎖的最早加鎖操作前，并丟棄所有與該最早加鎖操作相關(guān)的內(nèi)存更新，重新執(zhí)行；Grace則置所有加鎖解鎖操作為空操作，純粹以事務內(nèi)存機制來解決內(nèi)存沖突，當一個事務執(zhí)行完畢將要提交時，檢查它是否與已經(jīng)提交的事務存在沖突(即檢查它是否讀取過時內(nèi)存)，當存在沖突時丟棄該事務從開始到目前為止的所有內(nèi)存更新，回滾到開始點并重新執(zhí)行.Flock動靜結(jié)合地計算一個即將執(zhí)行的加鎖操作的未來鎖集，僅當其中的所有鎖都未被占據(jù)的情況下才允許該加鎖操作執(zhí)行.Scrider動態(tài)地將多線程程序的指令序列劃分為關(guān)鍵區(qū)和非關(guān)鍵區(qū)2類區(qū)域，并保證在任何時刻只有一個線程執(zhí)行關(guān)鍵區(qū)中的指令.

現(xiàn)有死鎖規(guī)避方法存在4個缺點：1)能力有限，大部分方法(除Grace和Scrider外)只能規(guī)避由互斥鎖造成的死鎖；2)被動盲目，Dimmunix，Sammati，Glock需要檢測到死鎖環(huán)后才能規(guī)避死鎖，而Scrider使所有關(guān)鍵區(qū)，包括沒有可能造成死鎖的關(guān)鍵區(qū)，串行執(zhí)行；3)開銷較大，在線規(guī)避方法如Glock，Grace，Scrider等的時間開銷都超過10%，Scrider更超過30%，離線規(guī)避死鎖方法Dimmunix，需要重新執(zhí)行目標程序；4)影響目標程序執(zhí)行正確性，Grace和Sammati不能回滾IO操作，因此可能在規(guī)避死鎖時導致程序輸入輸出錯誤，Scrider不能處理條件變量，可能導致沒有死鎖的程序發(fā)生死鎖或者活鎖.

本文的研究目標是“智能、主動、高效地規(guī)避多種類型死鎖，不影響程序正確性”，而Flock基于未來鎖集技術(shù)，通過動靜結(jié)合分析能在“不影響程序正確性”的前提下，“智能、主動、高效地規(guī)避互斥鎖死鎖”.受Flock基本思想啟發(fā)，本文提出一種動靜分析結(jié)合的基于未來鎖集的死鎖規(guī)避方案Flider (future lockset based deadlock avoider)，如圖1所示，使之從死鎖規(guī)避能力方面改進Flock，不僅能處理互斥鎖還能處理讀寫鎖，以規(guī)避由互斥鎖和讀寫鎖造成的多種類型死鎖，而不僅僅是互斥鎖死鎖.在圖1中，F(xiàn)lider首先使用Clang對源碼進行詞法語法分析，生成語法樹并建立過程內(nèi)控制流圖.然后在過程內(nèi)控制流圖上進行路徑敏感分析，計算和插樁鎖效應信息，使得加鎖操作和函數(shù)調(diào)用能夠“提前知道”將來要進行哪些加鎖解鎖操作，為動態(tài)分析階段的“智能、主動、高效”規(guī)避提供基礎(chǔ).最后通過動態(tài)分析，劫持加鎖操作，根據(jù)靜態(tài)插樁的鎖效應信息計算未來鎖集，并根據(jù)未來鎖集執(zhí)行規(guī)避邏輯動態(tài)規(guī)避死鎖.

在Flider中，動態(tài)階段的死鎖規(guī)避由于有靜態(tài)階段的信息輔助，只會使可能存在死鎖的2個關(guān)鍵區(qū)串行執(zhí)行，而不影響非關(guān)鍵區(qū)和不可能產(chǎn)生死鎖的關(guān)鍵區(qū)的并行執(zhí)行.Flider主動規(guī)避死鎖，死鎖不可能發(fā)生，故無需遇到死鎖時回滾目標程序并重新執(zhí)行，從而不會導致程序輸入輸出錯誤.

Fig. 1 Scheme of deadlock avoiding based on future lockset圖1 基于未來鎖集的死鎖規(guī)避方案

1 規(guī)避對象

Flider與Flock的死鎖規(guī)避能力不同，F(xiàn)lock只能規(guī)避由互斥鎖導致的死鎖，而Flider則試圖規(guī)避由pthread庫中2種同步設(shè)施，即互斥鎖和讀寫鎖，造成的5類死鎖：互斥鎖造成的死鎖、讀寫鎖造成的死鎖、互斥鎖與讀寫鎖造成的混合死鎖、互斥鎖自鎖和讀寫鎖自鎖，如圖2所示:

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

實際多線程程序中，互斥鎖和讀寫鎖的使用頻率都很高.程序員通常使用互斥鎖來保護只允許讀寫操作互斥執(zhí)行的共享變量，而對于允許多個讀操作同時執(zhí)行而寫操作互斥執(zhí)行的同步場景，程序員為提高性能往往使用讀寫鎖而不是互斥鎖來保護共享變量.Flock不能規(guī)避由讀寫鎖造成的死鎖，以及讀寫鎖和互斥鎖造成的混合死鎖，因此Flider在死鎖規(guī)避能力上對Flock的擴展具有重要意義和實際應用價值.

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

本節(jié)定義混合鎖分配圖(multiple-type lock allocation graph, MLAG)以表征多線程程序相對于互斥鎖和讀寫鎖的同步狀態(tài)，并在此基礎(chǔ)上給出5類死鎖的嚴格定義.

定義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是一個3元組(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當且僅當不存在(v,thr,rd_held)和(v,thr,wr_held)，tp1=rd_held當且僅當不存在(v,thr,wr_held)，其中thr∈T(t)；tp2取值wr_request或者rd_request.

混合鎖分配圖根據(jù)多線程程序執(zhí)行的加鎖解鎖操作而實時更新，當圖上出現(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代表一個互斥鎖死鎖當且僅當同時滿足下列條件：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代表一個讀寫鎖死鎖當且僅當同時滿足下列條件：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代表一個混合死鎖當且僅當同時滿足下列條件：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代表一個互斥鎖自鎖當且僅當同時滿足下列條件：1)k=2；2)v1∈M(t)，v2∈T(t)；3)e1=wr_held且e2=wr_request.

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

2 鎖效應與未來鎖集

Flider與Flock的基本思想相同，即若一個加鎖操作的未來鎖集中的所有鎖都未被鎖定，則執(zhí)行該加鎖操作是安全的，不會導致死鎖.一個加鎖操作的未來鎖集可能分布在多個函數(shù)內(nèi)，因此Flider似乎需要進行過程間分析以計算未來鎖集.但利用鎖效應概念和函數(shù)調(diào)用機制，F(xiàn)lider只需在靜態(tài)階段進行過程內(nèi)分析以為加鎖操作和函數(shù)調(diào)用操作計算鎖效應信息，而為加鎖操作計算跨過程分布的未來鎖集則推遲到動態(tài)階段.

Flock最早針對互斥鎖提出鎖效應和未來鎖集的概念，但未給出形式化定義.本節(jié)針對互斥鎖和讀寫鎖給出這些概念的嚴格定義與實例，第3節(jié)給出死鎖規(guī)避邏輯并展示基于未來鎖集的死鎖規(guī)避過程.

假設(shè)一條非空路徑path由n個指令按順序構(gòu)成，即path=ins1,ins2,…,insn，其中n≥2，insn表示結(jié)束指令.令x表示一個互斥鎖或讀寫鎖，lock(x)表示對互斥鎖或讀寫鎖x的(任意)加鎖操作，unlock(x)表示對x的解鎖操作.記type(x)表示鎖x的類型，取值MTX或RWLOCK.

關(guān)鍵區(qū)既可局限在一個函數(shù)內(nèi)，也可跨越函數(shù)而存在.對關(guān)鍵區(qū)的定義考慮到了可遞歸互斥鎖的語義.圖3給出了一個線程可能執(zhí)行的5條路徑，其中x和z是互斥鎖，y是讀寫鎖.在path1中，ins2,ins3,ins4,ins5,ins1,ins2,ins3,ins4,ins5,ins6都是關(guān)鍵區(qū)，而ins1,ins2,ins3,ins2,ins3,ins4,ins5,ins1,ins2,ins3,ins4,ins5都不是關(guān)鍵區(qū)，因為ins2,ins3,ins4,ins2,ins3,ins4都不是關(guān)鍵區(qū).在path2中，ins1,ins2,ins3,ins4,ins5和ins2,ins3,ins4,ins5,ins6都是關(guān)鍵區(qū).

Fig. 3 Five paths possibly taken by a single thread圖3 單個線程可能執(zhí)行的5條路徑

定義8. 鎖效應.假設(shè)path是非空函數(shù)f()的一條路徑，insn表示函數(shù)結(jié)束指令.記effect(ins)為指令ins的鎖效應信息.如果ins不是加鎖操作或函數(shù)調(diào)用操作，則effect(ins)為空.

2) 若存在指令insu=lock(x)，1≤u≤n，但不存在insv=unlock(x)，u

3) 若存在指令insu為自定義函數(shù)調(diào)用操作，1≤u≤n，則effect(insu)的計算過程與2)相同(除判斷任意鎖y是否等于x外，因為這里沒有特定鎖x).

鎖效應的概念和定義只局限在單個函數(shù)范圍內(nèi).只為加鎖操作和自定義函數(shù)調(diào)用操作計算鎖效應信息.對于某函數(shù)內(nèi)一條路徑上的加鎖操作，其鎖效應是從該加鎖操作到與之相對應的解鎖操作或者函數(shù)結(jié)束點的過程中遇到的所有非冗余加鎖解鎖信息.函數(shù)調(diào)用操作的鎖效應信息與之類似.在圖3的path3中，effect(ins1)，effect(ins2)，effect(ins3)都為{(x,-,MTX)};path4中，effect(ins2)為{(x,+,MTX),(x,-,MTX),(z,+,MTX),(y,-,RWLOCK)}，effect(ins1)為{(y,+,RWLOCK),(z,+,MTX),(y,-,RWLOCK)}；path5中，effect(ins5)為{(z,+,MTX),(x,-,MTX)}，effect(ins1)為{(y,+,RWLOCK),(z,-,MTX),(y,-,RWLOCK)}.

定義9. 未來鎖集.假設(shè)path為非空線程thd的一條路徑，insn表示當前thd將要執(zhí)行的指令.記flset(ins)為指令ins的未來鎖集.如果ins不是加鎖操作，則flset(ins)為空.記stack為線程thd專用的一個棧，在thd被創(chuàng)建時為空.

1) 若指令insn是自定義函數(shù)調(diào)用操作callf()，將鎖效應effect(insn)中的元素逆序入棧stack.

2) 若指令insn是自定義函數(shù)返回操作retf()，假設(shè)與之相對應的自定義函數(shù)調(diào)用操作是insu=callf()，1≤u≤n，則從棧stack中正序彈出鎖效應effect(insu).

3) 若指令insn是加鎖操作lock(x)，則首先將x從尾部插入flset(insn)，并將effect(insn)逆序入棧stack，然后從棧頂向棧底查找(x,-,type(x))，在查找過程中一旦遇到 (y,+,type(y))且y≠x，就將(y,type(y))從尾部插入flset(insn).不論成功找到或者直到棧底都沒有找到(x,-,type(x))，都從棧stack中逆序彈出effect(insn).

未來鎖集的概念與定義只局限在單個線程范圍內(nèi).只為加鎖操作計算未來鎖集.對于某線程內(nèi)一個路徑上的加鎖操作，其未來鎖集包括該加鎖操作所要加的鎖和從該加鎖操作到與之相對應的解鎖操作或線程結(jié)束點的過程中遇到的所有非冗余加鎖操作所要加的鎖.在圖3的path3中，flset(ins1)，flset(ins2)，flset(ins3)都為{(x,MTX)};path4中，flset(ins2)為{(y,RWLOCK),(x,MTX),(z,MTX)};path5中，flset(ins6)為{(z,MTX),(y,RWLOCK)}.

3 規(guī)避邏輯

假設(shè)一個多線程程序有thd1,thd2,…,thdm共m個線程，m≥1，線程thdi到目前為止的執(zhí)行路徑是pathi，1≤i≤m.pathi由指令insi,1,insi,2,…,insi,len(i)構(gòu)成，其中l(wèi)en(i)表示當前路徑pathi的長度.

定理1. 對于線程thdi，若當前路徑pathi的當前指令insi,len(i)=lock(x)，且其未來鎖集flset(insi,len(i))={l1,l2,…,ls}，其中x是一個互斥鎖或者讀寫鎖，l1=x,s≥1，那么下列命題成立：若任意lj都沒有被占據(jù)，1≤j≤s，則thdi執(zhí)行insi,len(i)會成功獲取鎖x且不會導致死鎖.

證明. 1)因為任意鎖lj(包括x)都沒有被鎖定，1≤j≤s，所以執(zhí)行insi,len(i)必定能成功獲取鎖x；2)若成功獲取鎖x導致線程thdi在將來執(zhí)行與insi,len(i)對應的釋放鎖x操作之前的某個時刻參與到某個死鎖環(huán)，則說明當thdi執(zhí)行insi,len(i)時，某個線程thdh已占據(jù){l1,l2,…,ls}中的某個鎖，1≤h≤m，否則根據(jù)混合鎖分配圖(定義1)的定義，thdi不可能參與構(gòu)成死鎖環(huán)，但根據(jù)命題前提可知，這不可能發(fā)生，因此thdi不會陷入死鎖.

證畢.

定理1指出,只有在加鎖操作的未來鎖集中所有鎖都未被占據(jù)的情況下，線程執(zhí)行加鎖操作才不會導致死鎖，但沒有說明若未來鎖集中存在某些鎖被占據(jù)的情況下，線程應執(zhí)行何種動作.實際上，在這種情況下，F(xiàn)lider讓線程延遲執(zhí)行加鎖操作直到該加鎖操作的未來鎖集中所有鎖都空閑.定理1也沒有考慮到加鎖操作的未來鎖集中的鎖已被當前線程所占據(jù)的情況.在實現(xiàn)時，當線程thd執(zhí)行加鎖操作lock(x)，若發(fā)現(xiàn)x已被自身占據(jù)，則將該加鎖操作和相應的解鎖操作視為空操作而執(zhí)行，若發(fā)現(xiàn)該加鎖操作的未來鎖集中某個非x的其他鎖已被自身占據(jù)，則仍然執(zhí)行該加鎖操作而不等待(當然需要檢查x是否已被自身占據(jù)).這樣Flider就能夠規(guī)避互斥鎖自鎖與讀寫鎖自鎖(4.5節(jié)).

定理2. 對于線程thdi，若當前路徑pathi的當前指令insi,len(i)=lock(x)，且其未來鎖集flset(insi,len(i))={l1,l2,…,ls}，其中x是一個互斥鎖或者讀寫鎖，l1=x,s≥1，那么下列命題不成立：若insi,len(i)是寫請求加鎖，則若任意lj,1≤j≤s，都沒有被(寫或讀)占據(jù)，則thdi執(zhí)行insi,len(i)不會導致死鎖；若insi,len(i)是讀請求加鎖，則若任意lj都沒有被寫占據(jù)，則thdi執(zhí)行insi,len(i)不會導致死鎖.

證明. 若要證明定理2成立，只需構(gòu)造一個例子使得其中的命題不成立.假設(shè)圖4中多線程代碼的執(zhí)行順序是ins1,1，ins2,1，ins1,2，ins2,2，x和y是讀寫鎖.

Fig. 4 A deadlock example caused by rwlocks圖4 一個讀寫鎖死鎖例子

圖4中的指令根據(jù)定理2中命題的規(guī)則執(zhí)行.當線程thd1執(zhí)行ins1,1時，由于ins1,1是讀請求加鎖且flset(ins1,1)={(x,RWLOCK),(y,RWLOCK)}中的所有鎖都未被寫占據(jù)，則thd1執(zhí)行ins1,1成功地讀占據(jù)x.然后當thd2執(zhí)行ins2,1時，由于ins2,1也是讀請求加鎖且flset(ins1,1)={(y,RWLOCK),(x,RWLOCK)}中的所有鎖都未被寫占據(jù)，則thd2執(zhí)行ins2,1成功地讀占據(jù)y.當thd1執(zhí)行ins1,2時，由于ins1,2是寫請求加鎖且flset(ins1,2)={(y,RWLOCK)}中的y已被線程thd2讀占據(jù)，所以thd1不執(zhí)行ins1,2而等待thd2釋放y.當thd2執(zhí)行ins2,2時，由于ins2,2是寫請求加鎖且flset(ins2,2)={(x,RWLOCK)}中的x已被線程thd1讀占據(jù)，所以thd2不執(zhí)行ins2,2而等待thd1釋放x.這樣就造成了thd1和thd2之間的相互循環(huán)等待，也即死鎖，因此定理2成立.

證畢.

定理2指出比定理1更細粒度的規(guī)避邏輯是不可行的.即對于一個讀請求加鎖操作，即使其未來鎖集中的鎖都被讀占據(jù)，F(xiàn)lider也不會允許其執(zhí)行，因為根據(jù)定理2，允許此讀請求加鎖操作執(zhí)行可能導致程序在將來遭遇死鎖.在定理1和定理2中，檢查未來鎖集中的鎖是否已被占據(jù)是通過搜索混合鎖分配圖來完成的.在目標程序運行時，F(xiàn)lider通過劫持加鎖解鎖操作以建立和更新混合鎖分配圖.

Flider進行過程內(nèi)分析，為每條執(zhí)行路徑上的加鎖操作和自定義函數(shù)調(diào)用操作計算鎖效應信息(定義8)并插樁到相應操作執(zhí)行前后.而在動態(tài)分析時利用插樁的鎖效應信息為加鎖操作計算未來鎖集(定義9).最后根據(jù)未來鎖集中的鎖是否空閑(定義1)執(zhí)行規(guī)避邏輯(定理1)以控制線程調(diào)度規(guī)避死鎖.基于定理1，F(xiàn)lider只使可能發(fā)生死鎖的關(guān)鍵區(qū)串行，而不會影響不可能發(fā)生死鎖的關(guān)鍵區(qū)和非關(guān)鍵區(qū)的并行執(zhí)行，從而達到“智能、高效”的規(guī)避目標.我們用圖5展示整個基于未來鎖集的死鎖規(guī)避過程.

Fig. 5 Demonstration of deadlock avoiding mechanism based on future lockset圖5 基于未來鎖集的死鎖規(guī)避示例

在圖5中，首先靜態(tài)分析源碼，針對過程內(nèi)的單個路徑為加鎖操作和自定義函數(shù)調(diào)用操作計算鎖效應信息，這里我們省略鎖效應信息中的鎖類型信息，例如g_T1()內(nèi)lock(x)的鎖效應信息為{y+,y-}，f_T2()內(nèi)g_T2()的鎖效應信息是{y-}；然后按照圖中標示的順序執(zhí)行代碼.在T1調(diào)用g_T1()時，將鎖效應信息effect(f_T1:g_T1())入棧stack#T1，在執(zhí)行g(shù)_T1()內(nèi)lock(x)時，先將鎖x加入未來鎖集flset(g_T1:lock(x))，并將鎖效應effect(g_T1:lock(x))入棧，然后在棧中查找x-，將查找過程中遇到的y+中的y從尾部插入flset(g_T1:lock(x))，于是得到g_T1內(nèi)lock(x)的未來鎖集是{x,y}.由于這2個鎖都沒有被鎖定，因此Flider允許T1執(zhí)行l(wèi)ock(x)以成功占據(jù)鎖x.線程T1占據(jù)鎖x后，操作系統(tǒng)調(diào)度T2執(zhí)行.在T2調(diào)用g_T2()時，將鎖效應信息effect(f_T2:g_T2())入棧stack#T2，在執(zhí)行g(shù)_T2()內(nèi)lock(y)時，先將鎖y加入未來鎖集flset(g_T2:lock(y))，并將鎖效應effect(g_T2:lock(y))入棧，然后在棧中查找y-，將查找過程中遇到的x+中的x從尾部插入flset(g_T2:lock(y))，于是得到g_T2內(nèi)lock(y)的未來鎖集是{y,x}.由于{y,x}中的一個鎖x已被T1占據(jù)，因此Flider不允許T2執(zhí)行l(wèi)ock(y)而是等待直到y(tǒng)和x都變得空閑.此時操作系統(tǒng)掛起T2而去重新執(zhí)行T1.在T1執(zhí)行g(shù)_T1()內(nèi)lock(y)，先計算出flset(g_T1:lock(y))為{y}.由于y未被占據(jù)，則Flider允許T2執(zhí)行l(wèi)ock(y)以成功獲取鎖y.在g_T1()返回時，將effect(f_T1:g_T1())從棧中彈出.T1執(zhí)行unlock(x)和unlock(y)時，F(xiàn)lider會更新混合鎖分配圖，從而T2能夠通過搜索混合鎖分配圖知道x和y已被釋放，進而執(zhí)行g(shù)_T2()內(nèi)lock(y).至此，F(xiàn)lider成功規(guī)避了圖5中多線程代碼在執(zhí)行時可能發(fā)生的死鎖.

4 Flider實現(xiàn)

我們在Ubuntu 14.04(內(nèi)核:Linux-3.13.0)上實現(xiàn)了Flider.如圖1所示，F(xiàn)lider主要包括預處理、靜態(tài)分析和動態(tài)分析三大模塊，分別負責完成過程內(nèi)控制流圖建立、鎖效應計算與插樁以及未來鎖集計算與規(guī)避邏輯執(zhí)行等功能.與Flock不同，F(xiàn)lider使用Clang而不是CIL[13]進行預處理和鎖效應插樁；另外Flider使用路徑敏感分析技術(shù)而不是類型推理計算鎖效應.前者使得Flider更通用，能處理比Flock更多類型的源程序;而后者使得Flider的鎖效應計算更簡潔和易于理解.

4.1 過程內(nèi)控制流圖建立

使用Clang對多線程程序源碼進行詞法語法分析，建立抽象語法樹并在此基礎(chǔ)上建立過程內(nèi)控制流圖.Clang建立的控制流圖是一個由基本塊組成的有向圖，利用該圖可以方便地判斷程序結(jié)構(gòu)，了解程序中各語句之間的先后執(zhí)行順序，獲得程序的執(zhí)行路徑.基本塊代表一個可順序執(zhí)行的語句序列，其中包括塊號、語句體、分支條件和前驅(qū)后繼.如圖6(a)是函數(shù)foo()的源碼，圖6(b)是Clang為之生成的控制流圖.

圖6(b)中的每個節(jié)點都代表一個基本塊，從B0到B10共11個基本塊，其中B10和B0分別是f()的入口塊和出口塊，這2個塊對每個函數(shù)都有且只有一個；B5，B4，B3構(gòu)成了一個環(huán)，對應圖6(a)中的while循環(huán)；B3是只有前驅(qū)和后繼信息的空塊，用于清晰地表示循環(huán)結(jié)構(gòu)，每個while循環(huán)都至少有一個空塊；非空塊中的帶標號文本為塊中語句或表達式，與源碼中的語句或表達式相對應；帶有T的塊表示分支塊，表示源碼中的分支結(jié)構(gòu)，T后的文本表示分支塊的分支條件；有向邊表示塊之間的前驅(qū)后繼關(guān)系，分支塊的出邊帶有標簽true或false，分別指向條件為真或為假時的后繼塊.

4.2 過程內(nèi)控制流圖路徑分析

Flider針對過程內(nèi)每條路徑為加鎖操作和自定義函數(shù)調(diào)用操作計算鎖效應(定義8)，因此在計算鎖效應之前需要在過程內(nèi)控制流圖上進行路徑分析，獲取從入口塊到出口塊的所有可能路徑.

簡單的深度或者廣度優(yōu)先遍歷，只能分析有向圖中2個節(jié)點的可達性，但不能計算出這2個節(jié)點之間的所有互異可達路徑，因此我們提出算法1所示的路徑分析算法求取從入口塊到出口塊的所有可能路徑.路徑分析算法不適用于帶環(huán)的有向圖，故在進行路徑分析之前，需要先對過程內(nèi)控制流圖進行去環(huán)處理，即將循環(huán)結(jié)構(gòu)改為循環(huán)體只執(zhí)行一次的分支結(jié)構(gòu).圖7展示了圖6中控制流圖的去環(huán)過程，其中控制流圖的基本塊節(jié)點以塊號表示.可以看到圖7(a)中基本塊B5，B4，B3構(gòu)成一個環(huán)，去環(huán)過程中，我們將鏈接B4和B5的空塊B3去除，將B4的后繼指向B5的后繼B2，從而得到圖7(b)所示的無環(huán)控制流圖.

Fig. 7 Cycle removing on CFG of function foo()圖7 對函數(shù)foo()的控制流圖進行去環(huán)處理

算法1以鄰接矩陣Arcs[N][N]為輸入，它表示經(jīng)過去環(huán)處理的控制流圖，N是所有節(jié)點的個數(shù).算法1深度優(yōu)先遍歷控制流圖，每個節(jié)點可能被多次遍歷，使用棧nstack存儲遍歷過程中找到的可能構(gòu)成路徑的節(jié)點，使用VertexStatus[N]和ArcStatus[N][N]這2個數(shù)據(jù)結(jié)構(gòu)控制節(jié)點的入棧和出棧.對于0≤i≤N，VertexStatus[i]=0表示i號節(jié)點未進棧或者已出棧，否則VertexStatus[i]為1.對于0≤i,j≤N，ArcStatus[i][j]=0當且僅當節(jié)點i和節(jié)點j都在棧外，否則ArcStatus[i][j]=1.算法1中，Traverse(nstack)遍歷棧nstack，將從棧底到棧頂?shù)膲K號按序排列組成一條所求路徑.UpdateArcStatus(VertexStatus,ArcStatus)根據(jù)VertexStatus更新ArcStatus，使得所有2個頂點都不在棧內(nèi)的邊的狀態(tài)為0.

算法1. 過程內(nèi)控制流圖上路徑分析算法.

輸入：過程內(nèi)控制流圖鄰接矩陣形式Arcs[N][N]；

輸出：過程內(nèi)控制流圖上從基本塊N到基本塊0的所有路徑集合paths.

算法1首先將起始塊N入棧nstack，并置VertexStatus[N]為1表示塊N已入棧(行④～⑤)，然后檢查棧是否為空，當棧不為空且棧頂元素是塊0時，則棧中從棧底到棧頂?shù)膲K號序列構(gòu)成一條所求路徑，生成路徑并加入到路徑集合中，將塊0從棧頂彈出，并相應更新VertexStatus和ArcStatus，使得塊0的入棧狀態(tài)為0和以塊0為其中一個頂點的2個頂點都不在棧中的邊的入棧狀態(tài)為0(行⑦～)，如果棧不為空且棧頂元素不是塊0時，則尋找序號最大的的塊i，該塊不在棧中(條件C1)且棧頂塊elem與塊i形成的邊(如果有邊的話，條件C3)也不在棧中(條件C2)，將塊i入棧，置邊(elem,i)的入棧狀態(tài)為1(行～)，如果不存在這樣的塊i，則說明在當前情況下，塊elem的所有出邊已被訪問過，此時向上回溯，將塊elem彈出并相應地更新VertexStatus和ArcStatus(行～).最后，算法返回所有合法路徑(行).

需要注意的一點是，為保證正確性和深度優(yōu)先遍歷特性，算法1僅在彈出棧頂元素時調(diào)用UpdateArcStatus(VertexStatus,ArcStatus).在圖7(b)上運行算法1，得到所有可能執(zhí)行路徑：

path1:B10→B9→B7→B6→B5→B2→B1→B0，

path2:B10→B9→B7→B6→B5→B4→B2→B1→B0，

path3:B10→B9→B7→B6→B1→B0，

path4:B10→B9→B7→B1→B0，

path5:B10→B9→B8→B1→B0，

其中→表示直接可達.

4.3 鎖效應計算與插樁

針對函數(shù)f()的控制流圖中的一條路徑path，F(xiàn)lider按照定義8為其上加鎖操作或者自定義函數(shù)調(diào)用操作計算鎖效應.計算出鎖效應后，根據(jù)path是否含有分支塊，按照不同的插樁規(guī)則將鎖效應信息插樁到相應操作前后，以便傳遞到動態(tài)分析模塊供計算未來鎖集之用.假設(shè)函數(shù)f()在線程thd中，針對鎖效應中的一個元素(x,+,MTX)，則在相應操作之前和之后的插樁語句分別是stack#thd.push(x,1)和stack#thd.pop(x,1)，針對元素(y,-,RWLOCK)，在相應操作之前和之后的插樁語句是stack#thd.push(y,0)和stack#thd.pop(y,0).這里有2點需要注意：1)由于鎖的類型信息在未來鎖集計算和規(guī)避邏輯執(zhí)行時無用(定理1和定理2)，我們省略對其的插樁，不將其傳遞到動態(tài)分析模塊；2)由于靜態(tài)分析階段無法確定線程的標識，線程專用的棧stack#thd是動態(tài)階段通過映射動態(tài)創(chuàng)建和查找的，我們靜態(tài)插樁能夠自動完成這種映射的代碼.

如果path不含有任何分支塊，則f()是不包含任何分支語句的順序結(jié)構(gòu)函數(shù)，將鎖效應信息直接插樁到相應操作的前后.圖8展示了對圖5中線程T1執(zhí)行的2個順序結(jié)構(gòu)函數(shù)f_T1()和g_T1()的插樁結(jié)果.函數(shù)g_T1()中需要插樁的語句有l(wèi)ock(x)和lock(y)，根據(jù)它們的鎖效應信息，在lock(x)前后插樁語句stub3，stub4和stub5，stub6，在lock(y)前后插樁語句stub7和stub8.函數(shù)f_T1()中需要插樁的語句是自定義函數(shù)調(diào)用g_T1()，在其前后插樁語句stub1和stub2.

Fig. 8 Lock effect instrumentation for functions with sequential structures圖8 順序結(jié)構(gòu)函數(shù)的鎖效應插樁

順序結(jié)構(gòu)函數(shù)只含有一條路徑，對其鎖效應插樁較簡單.但若函數(shù)f()含有條件分支語句(循環(huán)控制語句是條件分支語句的一種)，則其控制流圖必定具有多條路徑，且每條路徑都至少包含一個分支塊.對分支結(jié)構(gòu)函數(shù)的鎖效應插樁較復雜.

對于路徑path=BN→Bb1→Bb2→…→Bbn→B0，若Bbi是分支塊，則令Cbi表示Bbi的分支條件，其中b1,b2,…,bn∈{0,1,2,…,N}，n≥0，N≥1.令Bp→+Bq表示Bp經(jīng)過至少一個塊可達Bq，0≤p,q≤N.假設(shè)path內(nèi)的所有分支塊Bv1,Bv2,…,Bvr構(gòu)成Bv1→+Bv2…→+Bvr，Cv1,Cv2,…,Cvr分別是各自塊的分支條件，其中v1,v2,…,vr∈{b1,b2,…,bn}，r≥0.Flider按下列規(guī)則為路徑path上的加鎖操作和自定義函數(shù)調(diào)用操作計算和插樁鎖效應信息：

1) 按照定義8計算鎖效應.

2) 若某個加鎖操作與相應的解鎖操作(這2個指令與它們之間的指令構(gòu)成一個關(guān)鍵區(qū))都在一個塊內(nèi)，則直接在該加鎖操作前后插入相應的push和pop語句.

3) 設(shè)存在u∈{b1,b2,…,bn}，使得Bu不是分支塊且Bu→+Bv1→+Bv2…→+Bvr.若加鎖操作指令insl在Bu內(nèi)，且其相應的解鎖指令不在Bu而在Bv1或者Bu與Bv1之間的非分支塊中，則直接在insl前后插入相應插樁語句.若insl的相應解鎖指令不在Bu而在Bvs，2≤s≤r，則插樁在insl前后的push和pop語句集各自位于條件語句if(Cv1&&Cv2&&…&&Cvs-1)中.若insl的相應解鎖指令不在Bu而在Bvs與Bvs+1(規(guī)定Bvr+1為出口塊)之間的某個非分支塊中，2≤s≤r，則插樁在insl前后的push和pop語句集各自位于條件語句if(Cv1&&Cv2&&…&&Cvs)中.若自定義函數(shù)調(diào)用指令insf在Bu內(nèi)，則插樁在insf前后的push和pop語句集各自位于條件語句if(Cv1&&Cv2&&…&&Cvr)中.

4) 設(shè)存在u∈{b1,b2,…,bn}，使得Bu不是分支塊且Bv1→+Bv2…→+Bvr→+Bu.若insl和insf分別是Bu中的加鎖指令和自定義函數(shù)調(diào)用指令，則直接將鎖效應信息插樁到相應指令前后.

5) 對于分支塊Bvw或位于Bvw-1(規(guī)定Bv0為入口塊)與Bvw之間的非分支塊Bu，u∈{b1,b2,…,bn}，1≤w≤r，若insl是Bvw或Bu中的加鎖指令，且其相應解鎖指令在Bvs+1或者Bvs與Bvs+1之間的非分支塊中，則插樁在insl前后的push和pop語句集各自位于條件語句if(Cvw&&Cvw+1&&…&&Cvs)中.若insf是Bvw或Bu中的自定義函數(shù)調(diào)用指令，則插樁在insf前后的push和pop語句集各自位于條件語句if(Cvw&&Cvw+1&&…&&Cvr)中.

圖9展示了使用上述規(guī)則對分支結(jié)構(gòu)函數(shù)的鎖效應插樁結(jié)果.圖9控制流圖上存在2條路徑path1:B5→B4→B3→B1→B0和path2:B5→B4→B2→B1→B0，B4是分支塊.對path1和path2中B4的加鎖指令lock(mtx1)運用規(guī)則5插樁鎖效應，對B3和B2運用規(guī)則2插樁鎖效應，得到插樁后基本塊.

插樁規(guī)則3～5對于在分支塊或者在位于分支塊之前的非分支塊中的加鎖操作和自定義函數(shù)調(diào)用操作進行鎖效應插樁時，會將相應分支條件提前計算，以保證插樁的鎖效應是針對當前路徑的.但是有時分支條件不能提前計算，如分支條件中包含加鎖操作，分支條件中使用的變量在加鎖操作或自定義函數(shù)調(diào)用操作之后被定義或修改(圖10).在這種情況下，F(xiàn)lider使用路徑不敏感分析方法插樁鎖效應，即將從加鎖操作或自定義函數(shù)調(diào)用操作到函數(shù)結(jié)束的所有語句視為一條路徑上的語句，使用針對不含有分支塊的路徑的鎖效應插樁方法插樁.這種方法可能會串行化一些不必要串行的關(guān)鍵區(qū)，也可能會引入活鎖.

Fig. 9 Lock effect instrumentation for functions with conditional structures圖9 分支結(jié)構(gòu)函數(shù)的鎖效應插樁

Fig. 10 Examples of buggy instrumentation圖10 錯誤插樁的例子

對于循環(huán)結(jié)構(gòu)，由于其已在控制流上轉(zhuǎn)化成分支結(jié)構(gòu)，因此對循環(huán)結(jié)構(gòu)的鎖效應插樁自動按照對分支結(jié)構(gòu)的插樁方法處理.

插樁完成后，F(xiàn)lider利用Clang的代碼重寫器讀取已插樁的控制流圖，生成插樁過鎖效應的源碼.

4.4 加鎖解鎖操作劫持

我們將Flider的動態(tài)分析模塊實現(xiàn)為一個動態(tài)鏈接庫.在插樁過鎖效應信息的目標程序執(zhí)行時，該動態(tài)庫以預加載機制作為第一個被加載的動態(tài)庫加載到目標程序的進程空間內(nèi).通過使用Linux提供的預加載機制LD_PRELOAD，F(xiàn)lider劫持表1中所有作用于互斥鎖和讀寫鎖的加鎖解鎖操作，以便構(gòu)建和更新全局混合鎖分配圖G(定義1)、為加鎖操作計算未來鎖集(定義9)、根據(jù)未來鎖集執(zhí)行規(guī)避邏輯(定理1).

混合鎖分配圖根據(jù)加鎖解鎖操作的執(zhí)行效果而實時更新.若線程T執(zhí)行加鎖操作lock(x)請求加鎖x但目前還沒有成功占據(jù)x，則建立從T到x的(讀寫)請求關(guān)系；若線程T執(zhí)行加鎖操作lock(x)成功，則刪除從T到x的(讀寫)請求關(guān)系并建立從x到T的(讀寫)占據(jù)關(guān)系；若線程T執(zhí)行解鎖操作unlock(x)成功，則刪除從x到T的(讀寫)占據(jù)關(guān)系.在Flider中，混合鎖分配圖以映射數(shù)組的形式實現(xiàn).

4.5 規(guī)避邏輯的原子執(zhí)行

由于有鎖效應信息的輔助，加鎖操作的未來鎖集計算直接按照定義9進行即可.而規(guī)避邏輯檢查未來鎖集中的鎖的狀態(tài)，只有當所有鎖都未被占據(jù)時，才允許當前加鎖操作執(zhí)行.其中2個動作，即檢查鎖狀態(tài)和決定加鎖操作是否執(zhí)行，必須原子性執(zhí)行，否則規(guī)避邏輯不能正確運行.假設(shè)線程T1在執(zhí)行加鎖操作lock(x)前，F(xiàn)lider計算出該加鎖操作的未來鎖集是{x,y}，然后Flider檢查發(fā)現(xiàn)x和y都未被占據(jù)，在它進一步?jīng)Q定允許T1執(zhí)行l(wèi)ock(x)時，操作系統(tǒng)調(diào)度T2執(zhí)行l(wèi)ock(y)，假設(shè)lock(y)的未來鎖集也是{x,y}，則T2會被運行執(zhí)行l(wèi)ock(y)并成功獲取鎖y.當T1再次執(zhí)行時，它仍然認為x和y都是空閑的，從而執(zhí)行l(wèi)ock(x)以獲取x.這種規(guī)避邏輯可能不能規(guī)避死鎖.因此為保證正確性，規(guī)避邏輯必須原子性執(zhí)行.為此，我們?yōu)樗械囊?guī)避邏輯加上全局同一鎖保護，使得所有的規(guī)避邏輯串行執(zhí)行.具體地，鎖狀態(tài)檢查在全局鎖的保護下進行，如果發(fā)現(xiàn)未來鎖集中的鎖不是全都空閑，則釋放全局鎖，等待一段時間，然后重新獲取全局鎖，檢查鎖狀態(tài).若在全局鎖的保護下，發(fā)現(xiàn)未來鎖集中的鎖都未被占據(jù)，則執(zhí)行加鎖操作，然后釋放全局鎖.這樣就保證了規(guī)避邏輯的正確性.此外，為規(guī)避互斥鎖自鎖和讀寫鎖自鎖，當Flider檢查發(fā)現(xiàn)未來鎖集中的鎖已被當前線程占據(jù)時，就將當前加鎖操作和后續(xù)執(zhí)行中的相應解鎖操作視為空操作.

Table 1 LockUnlock Operations on Mutual Exclusive Locks and ReadWrite Locks表1 讀寫鎖和互斥鎖加鎖解鎖操作

Table 1 LockUnlock Operations on Mutual Exclusive Locks and ReadWrite Locks表1 讀寫鎖和互斥鎖加鎖解鎖操作

LockTypeLock∕UnlockOperationspthread_mutex_tintpthread_mutex_lock(pthread_mutex_t*);intpthread_mutex_trylock(pthread_mutex_t*);intpthread_mutex_timedlock(pthread_mutex_t*,conststructtimespec*);intpthread_mutex_unlock(pthread_mutex_t*).pthread_rwlock_tintpthread_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*).

5 實驗與分析

本節(jié)使用表2和表3列出的2個基準程序集和引言部分介紹的Dimmunix[7]，Grace[10]，F(xiàn)lock[11]，Scrider[12]這4個具有代表性的死鎖規(guī)避工具，實驗回答以下問題.

Table 2 The Deadlock Benchmark Composed of Ten May-Deadlock Programs表2 由10個死鎖程序構(gòu)成的死鎖基準程序集

Table 3 The Deadlock-Free Benchmark Composed of Four Kernel Programs from SPLASH-2表3 由4個SPLASH-2核心程序組成的基準非死鎖程序集

問題1. Flider的規(guī)避能力如何，即能否主動地規(guī)避多種類型的死鎖.

問題2. Flider的規(guī)避效率如何，即能否高效智能地規(guī)避死鎖.

問題3. Flider的可擴展性如何，即能否在線程數(shù)目指數(shù)級增長情況下，其規(guī)避開銷保持平穩(wěn)增長.

5.1 死鎖基準程序集和非死鎖基準程序集

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

表2列出死鎖程序的規(guī)模、死鎖程序中包含的死鎖缺陷、死鎖缺陷的具體類型和死鎖缺陷的發(fā)生原因或觸發(fā)場景.Deadlock-Mutex和Deadlock-Mrwlock是作者自己編寫的死鎖程序，分別包含2個和3個不同種類的死鎖缺陷；Bank-Transaction，SQLite-3.3.3，Dining-Philosophers，HawkNL-1.6b3各自包含一個互斥鎖死鎖缺陷；Tgrep和MySQL-6.0.4-kernel則各自包含一個讀寫鎖死鎖缺陷；Openldap-2.2.20-kernel和Sshfs-fuse-2.2各自包含一個混合死鎖缺陷.我們使用Bug#12和Bug#13模擬真實死鎖缺陷MySQL#37080①http://bugs.mysql.com/bug.php?id=37080和OpenLDAP#3494②http://www.openldap.org/lists/openldap-bugs/200501/msg00101.html，故包含這2個缺陷的程序MySQL-6.0.4-kernel和Openldap-2.2.20-kernel程序規(guī)模較小.

為回答問題2和3，本節(jié)使用的非死鎖基準程序集由4個SPLASH-2③http://www.capsl.udel.edu/splash/,http://kbarr.net/splash2核心程序構(gòu)成.表3給出各個程序的簡要描述和在實驗中使用的參數(shù)設(shè)置.

5.2 實驗環(huán)境與死鎖規(guī)避工具

所有評測和對比實驗在下列實驗環(huán)境下進行：Intel Core i5 M430 2.27 GHz CPU，6 GB內(nèi)存，Ubuntu 14.04 32位操作系統(tǒng)，Clang-3.6和Gcc-4.9.1編譯器.

為評價Flider的死鎖規(guī)避能力、死鎖規(guī)避效率和可擴展性，使用表4中死鎖規(guī)避工具監(jiān)視表2和表3中程序運行.之所以選用Dimmunix，Grace，F(xiàn)lock，Slider這4個死鎖規(guī)避工具，是因為它們代表了死鎖規(guī)避領(lǐng)域的最新水平，且源碼開放，能在我們的實驗環(huán)境下編譯運行.Sammati[9]源碼開放，但只能在64位操作系統(tǒng)下編譯運行，我們的實驗環(huán)境不支持.雖然沒有使用Sammati做對比實驗，但根據(jù)文獻[9]可知，Sammati只能規(guī)避互斥鎖死鎖.

Table 4 Deadlock Avoidance Tools Used in Our Experiments表4 實驗中使用的死鎖規(guī)避工具

5.3 問題1：Flider死鎖規(guī)避能力

為評價Flider的死鎖規(guī)避能力，按如下步驟進行實驗：1)分別在Flider，Scrider，Dimmunix，Grace，F(xiàn)lock下運行表2中的各個死鎖程序，每個死鎖程序在每個規(guī)避工具下運行30次；2)針對一個死鎖缺陷，如果某個工具在30次運行中只要有一次沒有成功規(guī)避該缺陷，則認為該工具不能規(guī)避該缺陷；3)統(tǒng)計每個工具對每個死鎖缺陷的規(guī)避結(jié)果.

實驗結(jié)果如表5所示，其中√表示規(guī)避成功，×表示規(guī)避失敗，*表示規(guī)避成功但輸出錯誤.針對所有13個不同類型的死鎖缺陷，F(xiàn)lider，Scrider，Grace各自成功規(guī)避其中11個，F(xiàn)lock成功規(guī)避5個，Dimmunix只成功規(guī)避了4個.

Table 5 Deadlock Avoiding Results of Five Avoidance Tools

Note: √,Succeed;×,Fail;*,Wrongly Output

各個死鎖規(guī)避工具的規(guī)避結(jié)果基本符合預期.Scrider成功規(guī)避了除互斥鎖自鎖(Bug#2)和讀寫鎖自鎖(Bug#5)的所有類型死鎖.Dimmunix和Flock只能規(guī)避互斥鎖死鎖(Bug#1，Bug#6，Bug#7，Bug#10，Bug#11)，其他類型死鎖都不能規(guī)避.但令人驚奇的是，與文獻[7]相悖，Dimmunix沒有能夠規(guī)避互斥鎖死鎖缺陷Bug#7.Bug#7是程序Dining-Philosophers中的一個簡單互斥鎖死鎖，當5個哲學家不停地進餐思考，并在進餐時每個哲學家(用線程模擬)都先拿到左手邊筷子(用互斥鎖模擬)再去拿右手邊筷子時，Bug#7就會發(fā)生.Bug#7涉及5個線程和5個互斥鎖，每個線程都占據(jù)一個互斥鎖并請求另一個線程占據(jù)的互斥鎖.我們仔細檢查了Dimmunix的源碼，發(fā)現(xiàn)其用于存儲加鎖解鎖事件的無鎖隊列實現(xiàn)錯誤，這一錯誤可能導致某些加鎖解鎖事件丟失，從而Dimmunix不能察覺到構(gòu)成死鎖的條件正在一個個發(fā)生，更不能控制線程調(diào)度以規(guī)避將要發(fā)生的死鎖.

Flider成功規(guī)避了除Bug#11和Bug#13外的所有死鎖，其規(guī)避能力與Scrider相當.Flider不能規(guī)避這2個缺陷是因為不精確的過程內(nèi)鎖效應計算和插樁會導致Flider“看不到”某些本來應該屬于未來鎖集中的鎖.例如，Bug#11和Bug#13可以抽象為如圖11所示的代碼，由于靜態(tài)階段沒有進行過程間分析，F(xiàn)lider為f1()的lock(x)計算出的鎖效應是{x-}，實際上，線程T1在執(zhí)行l(wèi)ock(x)后還會調(diào)用g1()進而執(zhí)行l(wèi)ock(y).對于f2()中的lock(y)也存在這樣的情況.由于鎖效應信息不準確，F(xiàn)lider為加鎖操作計算出的未來鎖集也不準確.當T1執(zhí)行l(wèi)ock(x)時，F(xiàn)lider為其計算的未來鎖集是{x}，x此時未被占用，故Flider允許T1執(zhí)行l(wèi)ock(x)并占據(jù)x.當T2執(zhí)行l(wèi)ock(y)時，F(xiàn)lider也允許其執(zhí)行并占據(jù)y.這樣當程序繼續(xù)執(zhí)行時，死鎖必定會發(fā)生，而且不能被Flider規(guī)避掉.

Fig. 11 A deadlock example that Flider fails to avoid圖11 一個Flider不能規(guī)避的死鎖例子

雖然存在以上不足，但從死鎖規(guī)避數(shù)量、死鎖規(guī)避類型方面評價，F(xiàn)lider的死鎖規(guī)避能力在5個規(guī)避工具中是最高的.Flider能規(guī)避所有5種類型的死鎖缺陷，而Scrider和Flock分別只能規(guī)避3種和1種類型的死鎖缺陷.Flider主動規(guī)避死鎖，在Flider的規(guī)避邏輯下，死鎖不可能發(fā)生，而Dimmunix則只有在死鎖發(fā)生后才能規(guī)避死鎖.Flider允許執(zhí)行的每個加鎖操作都是安全的，因此無需回滾程序執(zhí)行，也就不會造成輸出錯誤.只要目標程序不包含如圖11所示的死鎖缺陷，則Flider不會對目標程序正確性造成影響.

5.4 問題2：Flider死鎖規(guī)避效率

為評價Flider的死鎖規(guī)避效率，對比分析多個規(guī)避工具在死鎖程序集和非死鎖程序集上的規(guī)避開銷.

1) Flider和Flock在死鎖程序集上的靜態(tài)分析效率對比

由于Flider和Flock在進行動態(tài)規(guī)避之前，需要先進行源碼分析以計算鎖效應信息和插樁代碼將鎖效應信息傳遞給動態(tài)規(guī)避邏輯，因此在對比分析規(guī)避工具的動態(tài)規(guī)避開銷之前，使用Flider和Flock對死鎖程序集中的每個程序分別進行10次靜態(tài)分析(即鎖效應計算和代碼插樁)，統(tǒng)計得到平均分析時間，如表6所示：

Table 6 Comparison in Static Analysis Efficiency of Flider and Flock on Ten Deadlock Programs

表6 Flider和Flock在死鎖程序集上靜態(tài)分析效率 s

在表6中，由于只對SQLite-3.3.3和HawkNL-1.6b3中涉及到死鎖的文件進行靜態(tài)分析，因此Flider和Flock對這2個程序很快完成了鎖效應計算和插樁.Flider和Flock對Tgrep和Sshfs-fuse-2.2的靜態(tài)分析耗費時間較長，是由于其中存在具有大量條件分支語句的函數(shù)，而路徑敏感的算法1在這種情況下會逐條遍歷每條路徑，導致靜態(tài)分析速度變慢.另外，從表6中還可以看出，對于只含有互斥鎖死鎖的程序，如SQLite-3.3.3等，F(xiàn)lider和Flock的靜態(tài)分析時間相同，而對于含有讀寫鎖死鎖或者混合死鎖的程序，如Tgrep，F(xiàn)lider的分析時間一般較Flock長，因為針對這些程序，F(xiàn)lider不僅要為互斥鎖加鎖操作計算鎖效應和插樁，也要為讀寫鎖加鎖操作進行鎖效應分析.根據(jù)表6，只要并發(fā)程序中的函數(shù)不具有過分巨大的條件分支，如一個函數(shù)中含有50個以上的分支條件，則Flider會在合理時間內(nèi)完成靜態(tài)分析.

2) 多個規(guī)避工具在死鎖程序集上的規(guī)避效率

統(tǒng)計Flider，Scrider，Grace在規(guī)避Bug#1，Bug#3，Bug#4，Bug#6，Bug#9，Bug#10，Bug#12時，包含這些死鎖缺陷的程序Deadlock-Mutex，Deadlock-Mrwlock，Bank-Transaction，Sshfs-fuse-2.2，SQLite-3.3.3，Openldap-2.2.20-kernel的運行時間.我們沒有選用Dimmunix和Flock是因為Dimmunix不能在線規(guī)避死鎖，規(guī)避效率較差，且Dimmunix和Flock規(guī)避死鎖數(shù)量和類型都較少.另外，我們修改Deadlock-Mutex以保證其執(zhí)行時Bug#2不會發(fā)生，對Deadlock-Mrwlock也做了類似修改.

用箱式圖統(tǒng)計分析各個工具在各個程序上的規(guī)避時間，如圖12所示.對所有6個程序中的4個，即Deadlock-Mrwlock，Deadlock-Mutex，SQLite-3.3.3，Openldap-2.2.20-kernel，F(xiàn)lider的規(guī)避時間都比Scrider小，其中對Deadlock-Mrwlock，Scrider的平均規(guī)避時間甚至達到了Flider的53倍.Grace的規(guī)避開銷較小，對所有6個程序中的3個，即SQLite-3.3.3，Deadlock-Mutex，Openldap-2.2.20-kernel，Grace的規(guī)避時間是3個工具中最小的，但Grace在規(guī)避過程中造成6個程序中的5個，即Deadlock-Mutex，Deadlock-Mrwlock，SQLite-3.3.3，Bank-Transaction，Openldap-2.2.20-kernel，輸出錯誤.

Fig. 12 Comparison in avoiding efficiency of three toolson six deadlock programs圖12 3個規(guī)避工具在6個死鎖程序上的規(guī)避效率對比

另外，對所有6個程序中的4個，即Deadlock-Mrwlock，Bank-Transaction，Sshfs-fuse-2.2，Openldap-2.2.20-kernel，F(xiàn)lider的規(guī)避開銷與Grace相近，平均約是Grace的0.85倍.圖12還直觀地反映出3個工具的穩(wěn)定性：Grace的穩(wěn)定性較好，F(xiàn)lider穩(wěn)定性一般，Scrider穩(wěn)定性較差.

根據(jù)表5可知，F(xiàn)lider和Flock都能規(guī)避的死鎖缺陷是Bug#1，Bug#6，Bug#7，Bug#10.我們對比Flider和Flock對包含這些死鎖缺陷的并發(fā)程序的規(guī)避開銷，如表7所示.從表7中可以看出，F(xiàn)lider和Flock對這4個死鎖缺陷的平均、最大和最小規(guī)避開銷在數(shù)值上幾乎相同，而在百分比上平均規(guī)避開銷差異在-9.1%～6%之間，最大規(guī)避開銷差異在0～12.5%之間，最小規(guī)避開銷在0.2%～14.3%之間.Flider和Flock對這4個死鎖缺陷的規(guī)避開銷相差很小，是因為這4個死鎖都是互斥鎖死鎖，而且包含這4個死鎖缺陷的并發(fā)程序只調(diào)用互斥鎖函數(shù)進行加鎖解鎖操作，這就使得Flider和Flock進行的靜態(tài)分析(包括鎖效應計算和代碼插樁)完全一樣，進而導致并發(fā)程序執(zhí)行的規(guī)避邏輯完全一樣.這樣，F(xiàn)lider和Flock對每個死鎖缺陷的規(guī)避開銷就幾乎相同.

Table 7 Comparison in Avoiding Efficiency of Flider and Flock on Four Deadlock Programs

表7 Flider和Flock在4個死鎖程序上規(guī)避效率對比 s

ProgramFliderFlockavg.max.min.avg.max.min.Deadlock-Mutex2.0012.0042.0002.0012.0082.000Bank-Transaction0.1300.1600.0960.1230.1680.084SQLite-3.3.33.0003.0042.9962.9993.0042.992Dining-Philosophers0.0170.0400.0120.0190.0480.012

3) 多個規(guī)避工具在非死鎖程序集上的規(guī)避效率

實驗方法：①分別在Flider和Scrider下運行表3中的4個非死鎖程序各30次，每個程序的線程數(shù)目參數(shù)設(shè)置為2；②記錄每個程序的運行時間并求平均值.由于4個非死鎖程序存在使用共享變量進行線程間通信的情況，用Grace對它們進行規(guī)避可能導致活鎖，因此本實驗不選用Grace.實驗結(jié)果如圖13所示.

Fig. 13 Comparison in avoiding efficiency of two tools on four deadlock-free programs圖13 2個規(guī)避工具在4個非死鎖程序上的規(guī)避效率對比

Flider分別對LU，F(xiàn)FT，RADIX，CHOLESKY造成3.6%，-0.1%，3.0%，21%的性能下降，平均規(guī)避開銷是6.9%;而Scrider分別對上述4個程序造成20.5%，178.7%，25.7%，100.5%的性能下降，平均規(guī)避開銷是81.4%.相比來說，F(xiàn)lider對目標程序的性能影響較微小，而Scrider幾乎使目標程序的運行速度變慢為原來的12.這2個工具都采用串行關(guān)鍵區(qū)的方法來規(guī)避死鎖，但與Flider不同，由于沒有鎖效應信息的輔助，Scrider串行所有的關(guān)鍵區(qū)，不論關(guān)鍵區(qū)之間是否可能造成死鎖，這種盲目的方法使得Scrider的規(guī)避開銷急劇上升.Flider只串行可能導致死鎖的關(guān)鍵區(qū)，而不影響絕大部分關(guān)鍵區(qū)的并行執(zhí)行，這種智能的方法大大降低了其規(guī)避開銷.

綜上，F(xiàn)lider對死鎖程序集和非死鎖程序集的規(guī)避開銷都較低，且能高效智能地規(guī)避死鎖程序集中的死鎖缺陷.

5.5 問題3：Flider死鎖規(guī)避可擴展性

為評價Flider的死鎖規(guī)避可擴展性，按如下步驟進行實驗：1)在線程數(shù)目參數(shù)設(shè)置為1，2，4，8，16，32的情況下，分別在Flider和Scrider下運行表3中的各個非死鎖程序30次；2)記錄并計算每個程序在每個工具下對每個線程數(shù)目參數(shù)設(shè)置的平均運行時間.

實驗結(jié)果如圖14所示.對LU，當線程數(shù)目從1增加到32時，F(xiàn)lider的開銷在4.6%～9.7%之間，而Scrider的開銷則在13.0%～38.4%之間.對FFT，當線程數(shù)目從2增加到16時，F(xiàn)lider的開銷從1.2%增加到4.8%，而Scrider的開銷從50%迅速增加到195%.對CHOLESKY，當線程數(shù)目從1增加到32時，F(xiàn)lider的開銷在16%～85.3%之間，而Scrider的開銷在100.5%～802.0%之間，雖然兩者的開銷變化都較大，但在特定的線程數(shù)目時，F(xiàn)lider對目標程序的開銷相對Scrider很小.對RADIX，F(xiàn)lider和Scrider的規(guī)避開銷與對其他3個程序的開銷類似.

Fig. 14 Comparison in avoiding efficiency of two tools on four deadlock-free programs圖14 2個規(guī)避工具在4個非死鎖程序上的規(guī)避效率對比

因此，從圖14中4個折線圖可以看出，總體上，隨著線程數(shù)目指數(shù)增長，F(xiàn)lider的規(guī)避開銷總體保持平穩(wěn)增長;而Scrider對線程數(shù)目的變化較敏感，其規(guī)避開銷隨線程數(shù)目的增多而迅速增加.

6 結(jié) 論

現(xiàn)有動態(tài)規(guī)避方法存在能力有限、被動盲目、開銷較大和影響目標程序正確性等問題，為解決這些問題，本文提出一種動靜結(jié)合的基于未來鎖集的死鎖規(guī)避方案Flider.首先形式化描述該方案并在理論上證明該方案的正確性;然后從3個方面，即過程內(nèi)控制流圖建立、路徑敏感的鎖效應計算與插樁和未來鎖集計算與規(guī)避邏輯執(zhí)行，來具體介紹該方案的實現(xiàn)細節(jié)；最后進行測評和對比實驗，回答以下3個研究問題：

1) 與問題1相關(guān)的實驗中，F(xiàn)lider主動規(guī)避了所有13個死鎖缺陷中的11個(這11個死鎖缺陷分別屬于5種不同類型的死鎖)，且在規(guī)避所有11個死鎖缺陷時，沒有對目標程序的正確性造成影響.實驗結(jié)果表明Flider能主動規(guī)避多種類型的死鎖，且不會影響目標程序的正確性.

2) 與問題2相關(guān)的實驗中，F(xiàn)lider借助于靜態(tài)時插樁的鎖效應信息，智能地只串行化可能發(fā)生死鎖的關(guān)鍵區(qū)，在執(zhí)行規(guī)避邏輯時對目標程序造成的影響小.實驗結(jié)果表明Flider能智能高效地規(guī)避死鎖.

3) 與問題3相關(guān)的實驗中，F(xiàn)lider在目標程序線程數(shù)目從1指數(shù)級增長到32時，規(guī)避開銷的增長相對于線程數(shù)目的增長較平穩(wěn).實驗結(jié)果表明Flider的可擴展性良好.

綜上所述，本文提出的死鎖規(guī)避方案達到了 “智能、主動、高效地規(guī)避多種類型死鎖，不影響程序正確性”的研究目標.

[1]Agarwal R, Stoller S D. Runtime detection of potential deadlocks for programs with locks, semaphores and conditional variables[C] //Proc of the 2006 Workshop on Parallel and Distributed Systems: Testing and Debugging. New York: ACM, 2006: 51-60

[2]Wang Zhaofei, Huang Chun. Static detection of deadlocks in OpenMP Fortran programs[J]. Journal of Computer Research and Development, 2007, 44(3): 536-543 (in Chinese)(王昭飛，黃春. OpenMP Fortran程序中死鎖的靜態(tài)檢測[J]. 計算機研究與發(fā)展, 2007, 44(3): 536-543)

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

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

[5]Lu S, 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

[6]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]. 計算機學報, 2015, 38(11): 2215-2233)

[7]Jula H, Tralamazza D M, 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, 2008: 295-308

[8]Nir-Buchbinder Y, Tzoref R, Ur S. Deadlocks: From exhibiting to healing[C] //Proc of the 8th Int Conf on Runtime Verification. Berlin: Springer, 2008: 104-118

[9]Pyla H K, Varadarajan S. Avoiding deadlock avoidance[C] //Proc of the 19th Int Conf on Parallel Architectures and Compilation Techniques. New York: ACM, 2010: 75-86

[10]Berger E D, Yang T, Liu T, et al. Grace: Safe multithreaded programming for C/C++[J]. ACM SIGPLAN Notices, 2009, 44(10): 81-96

[11]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

[12]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

[13]Necula G C, McPeak S, Rahul S P, et al. CIL: Intermediate language and tools for analysis and transformation of C programs[C] //Proc of the 11th Int Conf on Compiler Construction. Berlin: Springer, 2002: 213-228

[14]Wang Y, Kelly T, Kudlur M, et al. Gadara: Dynamic deadlock avoidance for multithreaded programs[C] //Proc of the 8th USENIX Symp on Operating Systems Design and Implementation. Berkeley, CA: USENIX, 2008: 281-294

Yu Zhen, born in 1987. PhD candidate in the School of Computer Sience and Technology at Harbin Institute of Technology (HIT). 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 HIT. Senior member of CCF. Her main research interests include software engineering, information fusion, image processing and computer graphics.

Qi Peng, born in 1990. Master in the School of Computer Science and Technology at HIT. His main research interests include software engineering and deadlock bug detectionavoidance (qipengsemail@163.com).

Ma Peijun, born in 1963. Professor and PhD supervisor in the School of Computer Science and Technology at HIT. His main research interests include software engineering, information fusion, image processing, embedded system simulation, and so on (ma@hit.edu.cn).

Deadlock Avoiding Based on Future Lockset

Yu Zhen, Su Xiaohong, Qi Peng, and Ma Peijun

(SchoolofComputerScienceandTechnology,HarbinInstituteofTechnology,Harbin150001)

Existing dynamic methods for deadlock avoidance have four main drawbacks: limited capability, passive or blind avoiding algorithm, large performance overhead and no guarantee of correctness of target programs. In order to solve these problems, a combined static and dynamic avoiding method based on future lockset is proposed and named as Flider. The key idea is that, for a lock operation, if none of its future locks are occupied, then it makes sure that executing this lock operation won’t lead the current thread to trap into a deadlock state. The future lockset for a lock operation is a set of locks that will be requested by the current thread before the corresponding unlock operation is reached. Firstly, Flider statically computes lock effects for lock operations and function call operations, and inserts them before and after the corresponding operations. Secondly, Flider dynamically intercepts lock operations and computes its future lockset using lock effects inserted by static analysis. Flider permits a lock operation to be executed if and only if all locks of its lockset are not held by any other threads. Otherwise, the lock operation waits until the condition is satisfied. Evaluation and comparison experiments verify that this method can efficiently avoid multi-type deadlocks in an active, intelligent, scalable and correctness-guaranteed way.

concurrency bugs; concurrent testing; deadlock bugs; deadlock detection; deadlock avoidance; future lockset

2015-07-29

2016-12-22

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

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

TP311