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

禹 振 蘇小紅 齊 鵬 馬培軍

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

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

禹 振 蘇小紅 齊 鵬 馬培軍

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

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

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

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

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

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

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

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

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

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

1 規(guī)避對(duì)象

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

Fig. 2 Five deadlock scenarios caused by mutex and rwlock圖2 互斥鎖和讀寫(xiě)鎖造成的5種死鎖場(chǎng)景

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

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

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

定義1. 混合鎖分配圖.混合鎖分配圖G是一個(gè)動(dòng)態(tài)的簡(jiǎn)單圖(V(t),E(t))，其中：

1)V(t)和E(t)分別表示在時(shí)刻t的頂點(diǎn)和邊的集合.

2)V(t)中的頂點(diǎn)分成3類(lèi)：代表線程的頂點(diǎn)集合T(t)、代表互斥鎖的頂點(diǎn)的集合M(t)和代表讀寫(xiě)鎖的頂點(diǎn)集合RW(t)，顯然3個(gè)頂點(diǎn)集合中任2個(gè)交集為空.

3)E(t)中的每一條邊e是一個(gè)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方式請(qǐng)求同步設(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í)行的加鎖解鎖操作而實(shí)時(shí)更新，當(dāng)圖上出現(xiàn)環(huán)時(shí)，可以根據(jù)環(huán)中頂點(diǎn)的類(lèi)型和邊的類(lèi)型判斷其是否代表死鎖以及是哪種死鎖.假設(shè)G中存在一個(gè)環(huán)p=v1e1v2e2v3…vkekv1，其中1≤k≤min(|V(t)|,|E(t)|)，v1∈(M(t)∪RW(t))，記tp(e)為邊e的到其類(lèi)型值的映射.根據(jù)G的定義，k必定是偶數(shù).

定義2. 互斥鎖死鎖.環(huán)p代表一個(gè)互斥鎖死鎖當(dāng)且僅當(dāng)同時(shí)滿足下列條件：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. 讀寫(xiě)鎖死鎖.環(huán)p代表一個(gè)讀寫(xiě)鎖死鎖當(dāng)且僅當(dāng)同時(shí)滿足下列條件：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要求讀寫(xiě)鎖頂點(diǎn)的入邊和出邊不能同時(shí)是讀類(lèi)型的邊.

定義4. 混合死鎖.環(huán)p代表一個(gè)混合死鎖當(dāng)且僅當(dāng)同時(shí)滿足下列條件：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代表一個(gè)互斥鎖自鎖當(dāng)且僅當(dāng)同時(shí)滿足下列條件：1)k=2；2)v1∈M(t)，v2∈T(t)；3)e1=wr_held且e2=wr_request.

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

2 鎖效應(yīng)與未來(lái)鎖集

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

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

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

關(guān)鍵區(qū)既可局限在一個(gè)函數(shù)內(nèi)，也可跨越函數(shù)而存在.對(duì)關(guān)鍵區(qū)的定義考慮到了可遞歸互斥鎖的語(yǔ)義.圖3給出了一個(gè)線程可能執(zhí)行的5條路徑，其中x和z是互斥鎖，y是讀寫(xiě)鎖.在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ū)，因?yàn)閕ns2,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 單個(gè)線程可能執(zhí)行的5條路徑

定義8. 鎖效應(yīng).假設(shè)path是非空函數(shù)f()的一條路徑，insn表示函數(shù)結(jié)束指令.記effect(ins)為指令ins的鎖效應(yīng)信息.如果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)的計(jì)算過(guò)程與2)相同(除判斷任意鎖y是否等于x外，因?yàn)檫@里沒(méi)有特定鎖x).

鎖效應(yīng)的概念和定義只局限在單個(gè)函數(shù)范圍內(nèi).只為加鎖操作和自定義函數(shù)調(diào)用操作計(jì)算鎖效應(yīng)信息.對(duì)于某函數(shù)內(nèi)一條路徑上的加鎖操作，其鎖效應(yīng)是從該加鎖操作到與之相對(duì)應(yīng)的解鎖操作或者函數(shù)結(jié)束點(diǎn)的過(guò)程中遇到的所有非冗余加鎖解鎖信息.函數(shù)調(diào)用操作的鎖效應(yīng)信息與之類(lèi)似.在圖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. 未來(lái)鎖集.假設(shè)path為非空線程thd的一條路徑，insn表示當(dāng)前thd將要執(zhí)行的指令.記flset(ins)為指令ins的未來(lái)鎖集.如果ins不是加鎖操作，則flset(ins)為空.記stack為線程thd專(zhuān)用的一個(gè)棧，在thd被創(chuàng)建時(shí)為空.

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

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

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

未來(lái)鎖集的概念與定義只局限在單個(gè)線程范圍內(nèi).只為加鎖操作計(jì)算未來(lái)鎖集.對(duì)于某線程內(nèi)一個(gè)路徑上的加鎖操作，其未來(lái)鎖集包括該加鎖操作所要加的鎖和從該加鎖操作到與之相對(duì)應(yīng)的解鎖操作或線程結(jié)束點(diǎn)的過(guò)程中遇到的所有非冗余加鎖操作所要加的鎖.在圖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è)一個(gè)多線程程序有thd1,thd2,…,thdm共m個(gè)線程，m≥1，線程thdi到目前為止的執(zhí)行路徑是pathi，1≤i≤m.pathi由指令insi,1,insi,2,…,insi,len(i)構(gòu)成，其中l(wèi)en(i)表示當(dāng)前路徑pathi的長(zhǎng)度.

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

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

證畢.

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

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

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

Fig. 4 A deadlock example caused by rwlocks圖4 一個(gè)讀寫(xiě)鎖死鎖例子

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

證畢.

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

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

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

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

4 Flider實(shí)現(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

需要注意的一點(diǎn)是，為保證正確性和深度優(yōu)先遍歷特性，算法1僅在彈出棧頂元素時(shí)調(diào)用UpdateArcStatus(VertexStatus,ArcStatus).在圖7(b)上運(yùn)行算法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，

其中→表示直接可達(dá).

4.3 鎖效應(yīng)計(jì)算與插樁

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

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

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

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

對(duì)于路徑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)過(guò)至少一個(gè)塊可達(dá)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)用操作計(jì)算和插樁鎖效應(yīng)信息：

1) 按照定義8計(jì)算鎖效應(yīng).

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

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

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

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

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

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

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

Fig. 10 Examples of buggy instrumentation圖10 錯(cuò)誤插樁的例子

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

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

4.4 加鎖解鎖操作劫持

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

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

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

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

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

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

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 實(shí)驗(yàn)與分析

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

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

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

問(wèn)題1. Flider的規(guī)避能力如何，即能否主動(dòng)地規(guī)避多種類(lèi)型的死鎖.

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

問(wèn)題3. Flider的可擴(kuò)展性如何，即能否在線程數(shù)目指數(shù)級(jí)增長(zhǎng)情況下，其規(guī)避開(kāi)銷(xiāo)保持平穩(wěn)增長(zhǎng).

5.1 死鎖基準(zhǔn)程序集和非死鎖基準(zhǔn)程序集

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

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

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

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

所有評(píng)測(cè)和對(duì)比實(shí)驗(yàn)在下列實(shí)驗(yàn)環(huán)境下進(jì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編譯器.

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

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

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

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

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

Table 5 Deadlock Avoiding Results of Five Avoidance Tools

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

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

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

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

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

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

為評(píng)價(jià)Flider的死鎖規(guī)避效率，對(duì)比分析多個(gè)規(guī)避工具在死鎖程序集和非死鎖程序集上的規(guī)避開(kāi)銷(xiāo).

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

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

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

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

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

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

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

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

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

另外，對(duì)所有6個(gè)程序中的4個(gè)，即Deadlock-Mrwlock，Bank-Transaction，Sshfs-fuse-2.2，Openldap-2.2.20-kernel，F(xiàn)lider的規(guī)避開(kāi)銷(xiāo)與Grace相近，平均約是Grace的0.85倍.圖12還直觀地反映出3個(gè)工具的穩(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.我們對(duì)比Flider和Flock對(duì)包含這些死鎖缺陷的并發(fā)程序的規(guī)避開(kāi)銷(xiāo)，如表7所示.從表7中可以看出，F(xiàn)lider和Flock對(duì)這4個(gè)死鎖缺陷的平均、最大和最小規(guī)避開(kāi)銷(xiāo)在數(shù)值上幾乎相同，而在百分比上平均規(guī)避開(kāi)銷(xiāo)差異在-9.1%～6%之間，最大規(guī)避開(kāi)銷(xiāo)差異在0～12.5%之間，最小規(guī)避開(kāi)銷(xiāo)在0.2%～14.3%之間.Flider和Flock對(duì)這4個(gè)死鎖缺陷的規(guī)避開(kāi)銷(xiāo)相差很小，是因?yàn)檫@4個(gè)死鎖都是互斥鎖死鎖，而且包含這4個(gè)死鎖缺陷的并發(fā)程序只調(diào)用互斥鎖函數(shù)進(jìn)行加鎖解鎖操作，這就使得Flider和Flock進(jìn)行的靜態(tài)分析(包括鎖效應(yīng)計(jì)算和代碼插樁)完全一樣，進(jìn)而導(dǎo)致并發(fā)程序執(zhí)行的規(guī)避邏輯完全一樣.這樣，F(xiàn)lider和Flock對(duì)每個(gè)死鎖缺陷的規(guī)避開(kāi)銷(xiāo)就幾乎相同.

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

表7 Flider和Flock在4個(gè)死鎖程序上規(guī)避效率對(duì)比 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) 多個(gè)規(guī)避工具在非死鎖程序集上的規(guī)避效率

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

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

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

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

5.5 問(wèn)題3：Flider死鎖規(guī)避可擴(kuò)展性

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

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

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

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

6 結(jié) 論

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

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

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

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

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

[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)檢測(cè)[J]. 計(jì)算機(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ā)缺陷暴露、檢測(cè)與規(guī)避研究綜述[J]. 計(jì)算機(jī)學(xué)報(bào), 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

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

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

TP311