基于程序運行軌跡Petri網(wǎng)模型挖掘的死鎖檢測方法

魯法明，崔明浩，包云霞，曾慶田，段 華

(1.山東科技大學 計算機科學與工程學院，山東 青島 266590;2.山東科技大學 數(shù)學與系統(tǒng)科學學院，山東 青島 266590)

0 引言

隨著多核處理器技術的快速發(fā)展，多線程程序被廣泛應用，軟件系統(tǒng)的運行效率得到顯著提升。然而，由于程序調度的不確定性和執(zhí)行空間的復雜性，多線程程序容易引發(fā)死鎖和數(shù)據(jù)競爭等諸多并發(fā)缺陷[1]。死鎖通常會導致系統(tǒng)運行不穩(wěn)定，甚至造成嚴重后果，而且，據(jù)統(tǒng)計，約30%的并發(fā)缺陷與死鎖有關[2]。因此，多線程程序的死鎖檢測具有重要意義。

常見的死鎖檢測方法分為3類[1,3-4]：模型檢驗[5]、靜態(tài)分析[6-9]和動態(tài)分析[10-16]。模型檢驗借助形式化模型分析程序所有可能的行為，但其程序建模復雜，而且狀態(tài)空間爆炸等問題也容易導致時間性能的降低，不適合大型軟件程序的分析驗證；靜態(tài)分析通過對程序代碼(而非執(zhí)行代碼)的靜態(tài)分析來進行死鎖檢測，能較全面地發(fā)現(xiàn)潛在死鎖，但同樣存在效率低的問題。此外，由于缺乏程序運行時的諸多信息，靜態(tài)分析通常會產(chǎn)生較多誤報；動態(tài)分析[15]通過分析程序運行軌跡，研究鎖授權順序中存在的特定模式，并據(jù)此進行死鎖檢測。動態(tài)方法通常只針對某次或有限的幾次運行軌跡對程序進行分析，故存在死鎖漏報率高的不足。但是，同時具有動態(tài)分析效率高、可自動化進行的優(yōu)點。而且，由于動態(tài)分析依賴的程序運行軌跡隱含了大量程序運行時的信息，因此存在誤報率低的優(yōu)點。鑒于誤報率高嚴重影響死鎖分析的實際應用(如，文獻[5]對Sun JDK1.4進行分析時報告了100 000個潛在死鎖，但僅有7個為真實死鎖)，并且誤報的排除費時費力，故本文著眼于對死鎖的動態(tài)分析。

動態(tài)死鎖分析方法對程序運行軌跡進行分析并構建能部分反映程序行為的鎖圖等模型，再基于這些模型研究鎖授權順序中存在的特定模式，并根據(jù)這些模式來檢測死鎖。例如，文獻[7]首次基于鎖圖(將每個鎖對象作為一個節(jié)點；當某線程在持有鎖A并請求鎖B時，在節(jié)點A到B間添加一有向弧，由此形成的圖稱為鎖圖。)給出了一個死鎖的動態(tài)分析工具Visual Threads，它將鎖圖中每個環(huán)路視為一個潛在死鎖。這種方法簡單有效，但存在多種類型的誤報。比如，單一線程訪問鎖對象時形成的環(huán)路、門鎖保護的環(huán)路、具有因果關系的多個線程之間的鎖授權操作導致的環(huán)路等，這些環(huán)路都會導致死鎖誤報。文獻[11]提出基于鎖樹的GoodLock死鎖檢測算法，該算法能排除單線程環(huán)和門鎖環(huán)導致的誤報，但只能檢測兩個線程之間由于鎖對象的持有和等待導致的死鎖。文獻[12-13]提出了環(huán)鎖依賴鏈的概念，相比鎖圖，它相當于在鎖圖的有向弧上擴充了線程ID、當前持有的鎖集等信息，能同時排除單線程環(huán)和門鎖保護環(huán)導致的誤報，而且對構成死鎖的線程數(shù)量沒有限制。文獻[14-15]一方面基于線程之間的start和join操作對線程進行了分段，根據(jù)段之間的依賴關系提出了分段圖的概念；另一方面，在鎖圖的基礎上擴充線程ID、當前持有的鎖集以及段號等信息，提出了分段鎖圖的概念；最終，提出一種基于分段圖和分段鎖圖的死鎖檢測新方法，可以排除單線程環(huán)、門鎖環(huán)和多線程間具有因果關系的段鎖授權操作環(huán)導致的誤報。然而，前述各種工具對多線程程序并發(fā)原語的建模能力有限，比如，無法對鎖的授權/釋放操作及其執(zhí)行的場景進行準確刻畫，從而仍然會導致一些誤報現(xiàn)象(見1.1節(jié)案例分析)。在并行程序分析、業(yè)務過程管理[17-19]等分布式并發(fā)系統(tǒng)建模與分析領域，Petri網(wǎng)以其堅實的數(shù)學基礎和直觀的圖形化表示被廣泛應用[20-21]。鑒于此，本文擬采用Petri網(wǎng)對程序運行軌跡中蘊含的與死鎖相關的多種并發(fā)原語進行建模，對鎖的授權和釋放、并發(fā)原語的每一次執(zhí)行都采用獨立的變遷來建模，這可以有效提高程序行為建模的精確度；之后，基于該Petri網(wǎng)模型的行為分析對多線程程序的潛在死鎖進行檢測。相比傳統(tǒng)方法，本文所提方法能排除更多的誤報。

對多線程程序而言，除各類并發(fā)原語，線程的循環(huán)等待、語句執(zhí)行時間等也對死鎖的產(chǎn)生具有重要影響。前述各種模型，包括本文擬采用的Petri網(wǎng)模型，很難完整建模所有死鎖相關的信息，從而仍會導致一些誤報現(xiàn)象。為保證所檢測死鎖的真實性，文獻[22]提出一種多線程程序的隨機調度方法，通過不同調度方案下程序的大量運行來盡量觸發(fā)死鎖，這可以保證所檢測死鎖的真實性。但是，該方法事先并不進行潛在死鎖的檢測，其調度是盲目的、完全隨機的，加之死鎖通常是低概率事件，這導致該方法在效率和可靠性方面存在較大不足。相比而言，文獻[12,23-25]先進行潛在死鎖的檢測，之后針對每一個潛在死鎖有針對性地生成程序調度方案以重演死鎖，這提高了死鎖重演成功的概率。具體而言，文獻[12，23]提出一種啟發(fā)式的死鎖重演和程序調度策略，在線程到達潛在的死鎖點時掛起線程，以此增加死鎖觸發(fā)的概率。不過，該方法本質上也是隨機的，通常需要多次運行才能觸發(fā)死鎖，而且存在所謂的顛簸問題[12]，即使是一個真實的死鎖也無法保證一定重演成功。文獻[24-25]針對潛在死鎖生成一組程序調度的約束集，當程序的運行不符合生成的約束時掛起線程的執(zhí)行，該調度方案是確定性的。本文基于挖掘到的程序Petri網(wǎng)模型也可以生成一個確定性的程序調度方案來重演死鎖。相比而言，文獻[24-25]中的工作基于環(huán)鎖依賴鏈檢測潛在死鎖，而本文方法檢測到的潛在死鎖誤報更少、更準確。

總之，本文首先通過對Java多線程程序運行軌跡進行分析，挖掘一個能隱含盡量多程序行為信息的Petri網(wǎng)模型；之后，通過對該模型的動態(tài)行為分析檢測潛在的程序死鎖，并生成一個可用于死鎖重演的確定性的程序調度方案。相比已有工作，本文方法有如下特點：

(1)基于程序運行軌跡挖掘一個更能精確建模程序行為的Petri網(wǎng)模型，該模型相比傳統(tǒng)的鎖圖及其擴展模型能規(guī)避更多的死鎖誤報現(xiàn)象；與此同時，該模型雖由程序的單次運行軌跡重構而得，但它可以包含多條不同的程序運行軌跡，這為檢測出更多的死鎖提供了可能。

(2)在所得程序Petri網(wǎng)模型的基礎上，對傳統(tǒng)Petri網(wǎng)可達樹技術進行擴充，進行程序死鎖檢測的同時可得到死鎖重演的一種確定性調度方案，這為死鎖的真實性奠定了基礎。

1 動機與研究路線

1.1 實例分析

圖1給出了一個多線程程序實例，包含3個線程(主線程、threadA和threadB)、3個鎖對象(G、o1、o2)。主線程首先啟動線程threadA，該線程在一個循環(huán)體中順序獲取鎖G、o1和o2，然后逐個釋放。第一次循環(huán)過程中，線程在獲取鎖G后會啟動線程threadB，然后會先獲取G，釋放G后再依次獲取o2和o1。threadA第二次執(zhí)行循環(huán)體時不進行線程threadB的新建和啟動。不難發(fā)現(xiàn)，“threadA第二次執(zhí)行循環(huán)體時順序獲取鎖o1和o2的操作”與“threadB釋放G后順序獲取o2和o1”的操作會導致程序死鎖的發(fā)生。而“threadA第一次執(zhí)行循環(huán)體時順序獲取鎖o1和o2的操作”與“threadB順序獲取o2和o1”的操作不會導致死鎖，因為第一次循環(huán)執(zhí)行過程中鎖G始終被threadA持有，此時threadB因無法獲得鎖G而不會執(zhí)行獲取o2和o1的操作。

表1 多線程程序Program 1的一次運行軌跡

假設程序某次運行的軌跡如表1所示。表中：fork(u,v)表示線程u啟動線程v的操作, acq(u,o)和rel(u,o)表示線程u獲取和釋放鎖對象o，stop(u)表示線程u終止，join(u,v)表示線程u等待線程v終止后方執(zhí)行后續(xù)操作。基于該運行軌跡，按文獻[11-12]的方法可得如圖2所示分段圖和分段鎖圖。前者實際上將源程序每個線程執(zhí)行的操作分為了多個段，每段對應一個唯一的段ID，段和段之間執(zhí)行順序上的先后關系通過分段圖中的有向路徑來建模；分段鎖圖是在傳統(tǒng)鎖圖有向弧的基礎上擴充了標記信息,其中：preSegID表示線程threadID持有鎖preLockID時所在段的段號，postSegID表示線程threadID獲取鎖postLockID時所在段的段號，Lockset表示線程threadID申請鎖postLockID時持有的鎖集。文獻[9-10]提出的環(huán)鎖依賴鏈相當于將分段鎖圖中更為精確的段ID信息退化為了線程ID，傳統(tǒng)的鎖圖相當于從分段鎖圖中去除弧上所有的標記信息。

基于鎖圖、環(huán)鎖依賴鏈、分段圖與分段鎖圖以及本文方法，對表1中的程序運行軌跡進行分析，得到表2所示的死鎖檢測結果。如前所述，表2第一行給出的潛在死鎖實際是一種誤報，因為threadA在第一次循環(huán)體執(zhí)行過程中會始終持有鎖G，此時threadB會被阻塞在第57行獲取G的位置，從而無法執(zhí)行后續(xù)操作。但是，如表2所示，基于鎖圖、環(huán)鎖依賴鏈、分段圖與分段鎖圖的已有方法均無法排除這一誤報，究其原因，上述幾種模型均無法區(qū)分threadA兩次不同循環(huán)中獲取鎖的操作，而且由于上述模型沒有顯式建模鎖對象的釋放操作，threadB順序獲取o2和o1前需要曾經(jīng)持有鎖對象G的條件也因為G的及時釋放而無法刻畫。正是因為這些因素導致了誤報的發(fā)生。

表2 不同方法對表1運行軌跡進行動態(tài)分析所得死鎖檢測結果

針對上述問題，本文擬利用Petri網(wǎng)對程序運行軌跡中蘊含的程序行為進行更精確的建模：分別對模型中鎖的授權和釋放進行建模，對線程的start/stop/join等并發(fā)原語也進行描述，而且同一并發(fā)原語的多次執(zhí)行分別用多個獨立的Petri網(wǎng)變遷刻畫。這種建模粒度的細化以及更多程序信息的建模為提高死鎖檢測的準確性奠定了基礎。此外，該模型通過資源庫所的沖突結構，描述鎖對象間的互斥競爭關系，通過變遷可執(zhí)行序列中的操作先后關系，刻畫同一線程各操作間的順序關系，以及分段圖所描述的不同線程操作間的順序關系。這種模型隱含的程序行為信息超過了以往的鎖圖、環(huán)鎖依賴鏈、分段圖和分段鎖圖，其死鎖檢測能力理應更加準確。

利用本文方法可排除上述誤報現(xiàn)象，并能準確檢測出真實的死鎖，從而證明了本文方法的有效性。此外，從該Petri網(wǎng)模型出發(fā)還可以方便地得到死鎖重演的一種確定性調度方案。

1.2 研究路線

本文研究路線如圖3所示。給定一個Java多線程程序實例，首先通過RoadRunner[注]RoadRunner是一個Java多線程程序的動態(tài)分析框架，它將事件流通信到后端分析，其中每個事件描述目標程序執(zhí)行的需要關注的操作。[26]捕獲程序某次運行時各并發(fā)原語構成的操作序列，包括鎖的申請和釋放、線程的start/stop/join等；之后，為每個并發(fā)原語構建相應的Petri網(wǎng)子模型，在此基礎上，結合程序運行軌跡構建程序的Petri網(wǎng)模型；接下來，為進行程序死鎖檢測，構造程序Petri網(wǎng)的伴隨網(wǎng)模型，并給出其死鎖檢測可達樹的概念和構造方法；最后，基于死鎖檢測可達樹，一方面給出潛在的程序死鎖，另一方面為每個潛在死鎖生成一個確定性的程序調度方案以用于死鎖重演。下面對研究路線中的各項關鍵內(nèi)容分別進行介紹。

2 程序運行軌跡的Petri網(wǎng)模型挖掘

2.1 多線程程序的運行軌跡

假設多線程程序由一組有限的線程組成，每個線程有一個唯一的線程標識符(如u或v)，程序運行軌跡α定義為程序運行過程中所執(zhí)行的各類并發(fā)原語構成的序列，具體如下：

α∈Trace∷=SynOperation*，

op∈SynOperation∷=c:fork(u,v)|c:join(u,v)|c:stop(u)|c:acq(u,l)|c:rel(u,l)。 其中：

SynOperation表示各類并發(fā)操作的集合，SynOperation*為并發(fā)操作構成的序列全體；

u,v∈Tid表示線程，l∈Lock表示鎖，c表示一個程序語句的標簽；

fork(u,v)表示線程u派生并啟動一個新線程v；

join(u,v)表示線程u等待線程v完成后，方能繼續(xù)向下運行；

stop(u)表示線程u終止；

acq(u,l)和rel(u,l)表示線程u獲取和釋放鎖l。

如表1所示即為Java多線程程序Program 1的一個運行軌跡，它描述了程序某次運行中各個并發(fā)原語的執(zhí)行順序等信息，后文將據(jù)此構建程序的Petri網(wǎng)模型。

2.2 并發(fā)原語與程序的Petri網(wǎng)模型構建

Petri網(wǎng)被廣泛用于并發(fā)系統(tǒng)的建模和分析。一個Petri網(wǎng)對應一個4元組Σ=(P,T;F,M0)，其中：P和T分別是不相交的庫所集和變遷集，F(xiàn)?(P×T)∪(T×P)是網(wǎng)Σ的流關系集，M0:P→{0,1,2,…}被稱為Σ的初始標識，它描述系統(tǒng)的初始狀態(tài)[27]。本文每個Petri網(wǎng)變遷用于刻畫程序中一個并發(fā)原語的某次執(zhí)行，庫所分為控制流庫所和資源庫所兩類，前者對各個線程的控制流狀態(tài)進行建模，后者用來描述多個線程間共享的鎖對象。

根據(jù)Petri網(wǎng)的執(zhí)行規(guī)則與各個并發(fā)原語的操作語義，可得表3所示各類并發(fā)原語和程序狀態(tài)對應的Petri網(wǎng)模型。模型中各庫所、變遷所描述的程序含義見表3第3列。

基于RoadRunner或者其他程序運行分析平臺捕獲多線程程序的運行軌跡后，進而可根據(jù)表3給出的規(guī)則構建程序的Petri 網(wǎng)模型。具體而言，最初為主線程的就緒狀態(tài)生成一個庫所，并在其中添加一個token(表示主線程處于就緒狀態(tài))；同時為每個鎖對象生成一個庫所，也向其中添加一個token(表示初始狀態(tài)下各個鎖對象可用)；之后，對每一個捕獲到的并發(fā)原語操作，按照表3的規(guī)則添加變遷、控制流庫所和資源庫所及相應的流關系。以表1的運行軌跡為例，按上述方法可得其對應的程序Petri網(wǎng)模型，如圖4所示(紅色矩形框對應的變遷及其關聯(lián)的流關系不含在內(nèi))。

Σ1中的綠色圓圈為資源庫所，對應鎖對象；黑色圓圈為控制流庫所，對應線程的控制流狀態(tài)；黑色矩形為變遷，對應并發(fā)操作的一次執(zhí)行。為便于理解，在每個變遷和資源庫所旁用藍色標簽給出了其對應的程序含義，黑色標簽是庫所或變遷的ID。庫所內(nèi)的小黑點為token，控制流庫所中的token表示相應的控制流狀態(tài)被激活，資源庫所中的token表示相應的鎖對象可用。需要指出的是，由程序運行軌跡和表3規(guī)則所構造的Petri網(wǎng)模型是安全的，因為控制流庫所或處于激活狀態(tài)，或處于非激活狀態(tài)；資源庫所或對應鎖對象的可用狀態(tài)，或對應鎖對象的不可用狀態(tài)，這意味著在任意可達狀態(tài)下，程序Petri網(wǎng)模型的各個庫所中的token數(shù)量或為0，或為1，從而是安全的。

對于按上述方法構建的程序Petri網(wǎng)模型，原程序運行軌跡相對應的變遷序列顯然是可引發(fā)的。例如，表1中的運行軌跡對應著圖4中的變遷序列σ=t1t2t3t4t5t6t7t8t9t10t12t11t13t14t15t16t17t18t19t20t21t22t23t24，易驗證該序列是可引發(fā)的。從初始標識出發(fā)，σ引發(fā)后到達的狀態(tài)標識為{p26,p18,p27,p28,p29}。該標識是一個合法的程序終止狀態(tài)(未被join的各線程的終止狀態(tài)庫所含有一個token，每個鎖對象對應的資源庫所含有一個token，其他庫所均不含token。這意味著所有線程均正常終止，且所有的鎖均被釋放)。

表3 程序狀態(tài)與并發(fā)原語的Petri網(wǎng)模型

續(xù)表3

然而，前述構造的程序Petri網(wǎng)模型除隱含原始的程序運行軌跡外，還可能包含許多其他的程序潛在運行軌跡。這是因為，前述構造原理保證了僅在以下情況下才會在Petri網(wǎng)中建立節(jié)點之間的因果關系(其他情況下被處理為并發(fā)或者沖突，由此導致了執(zhí)行軌跡的多樣性)：①同一線程中的兩個操作依次執(zhí)行，則在它們之間建立直接因果關系；②線程u執(zhí)行fork(u,v)操作，此時在fork(u,v)和線程v的第一個操作之間建立直接因果關系；③線程u執(zhí)行Join(u,v)操作，此時在線程v的最后一次操作stop(u)和Join(u,v)之間建立直接因果關系；④鎖l對應的資源庫所和acq(u,l)之間建立直接因果關系；⑤rel(u,l)和鎖l對應的資源庫所之間存在因果關系。對于任何其他情況，即使是運行軌跡中相繼發(fā)生的兩個操作，它們之間也不建立因果關系。例如，表1中第11步操作60:acq(threadB,o2)和第12步操作28:acq(threadA,G)，雖然他們之間在表1運行軌跡中緊鄰發(fā)生，但不滿足前述5種條件，故其在Petri網(wǎng)模型的可執(zhí)行變遷序列中順序是不確定的(t12與t11的引發(fā)次序多樣化)。例如，σ′=t1t2t3t4t5t6t7t8t9t10t11t12t13t14t15t16t17t18t19t20t21t22t23t24也是Σ1中的一個可執(zhí)行變遷序列。

程序Petri網(wǎng)模型隱含了多樣化的程序運行軌跡，這為程序的死鎖檢測提供了可能。例如，σ″=t1t2t3t4t5t6t7t8t9t10t11t12t17也是Σ1的一個可執(zhí)行變遷序列，該序列執(zhí)行后到達一個死標識{p1,p14,p19}，該標識下沒有任何一個變遷可執(zhí)行，而且存在未正常終止的線程。這實際對應著源程序的一個死鎖狀態(tài)(threadA持有o1申請o2，threadB持有o2申請o1)，該變遷序列對應的程序運行軌跡如表4所示，表中加粗字體給出的操作由于threadA與threadB對鎖對象o1和o2的持有等待導致了程序死鎖。

表4 導致死鎖的實例程序的運行軌跡

2.3 程序模型的伴隨Petri網(wǎng)

對于2.2節(jié)由運行軌跡挖掘到的程序Petri網(wǎng)模型，無論是程序的合法結束狀態(tài)，還是程序的死鎖狀態(tài)，均對應Petri網(wǎng)模型的一個死標識。為區(qū)分二者，在程序Petri網(wǎng)模型的基礎上添加一個額外的變遷(對應圖4中紅色矩形框表示的recover變遷)，其作用是將程序的合法終止狀態(tài)恢復為初始狀態(tài)。如此一來，程序的合法終止狀態(tài)在修改后的網(wǎng)模型中便不再是死標識，而程序的死鎖狀態(tài)仍將對應一個死標識。為達到這一目的，recover變遷的輸入庫所應設置為所有未被join的線程的終止態(tài)庫所和所有鎖對象對應的資源庫所，其輸出庫所應設置為主線程的就緒態(tài)庫所和所有鎖對象對應的資源庫所。稱添加recover變遷后的網(wǎng)模型為原始程序Petri網(wǎng)模型的伴隨網(wǎng)，其嚴格定義如下：

定義1程序模型的伴隨Petri網(wǎng)給定一個由運行軌跡挖掘的程序Petri網(wǎng)模型Σ=(P,T;F,M0)，設PthreadStop是所有未被join的線程之終止狀態(tài)庫所的集合，Plock是所有鎖對象對應的資源庫所集合，p0是主線程就緒狀態(tài)對應的庫所。令P′=P，T′=T∪{recover}，其中recover是一個新添加的變遷，F(xiàn)′=F∪((PthreadStop∪Plock)×{recover})∪({recover}×({p0}∪Plock))，稱Σ′=(P′,T′;F′,M0)為Σ的伴隨Petri網(wǎng)。

例如，圖4含有recover變遷完整模型就是Σ1的伴隨Petri網(wǎng)。顯然，源程序的合法終止狀態(tài)不再是伴隨Petri網(wǎng)的一個死標識，因為該狀態(tài)下recover變遷可使能，并將系統(tǒng)狀態(tài)恢復為程序的初始狀態(tài)。而源程序的死鎖狀態(tài)仍然對應伴隨Petri網(wǎng)的一個死標識(即{p1,p14,p19})，因為在死鎖狀態(tài)下，recover變遷和原來的所有變遷均不使能。因此，要檢測多線程程序的潛在死鎖，只需要對伴隨Petri網(wǎng)進行死標識檢測，下面給出檢測方法。

3 多線程程序的死鎖檢測與重演

可達樹[14]是進行Petri網(wǎng)可達性分析的重要工具，安全Petri網(wǎng)可達樹的每個節(jié)點都關聯(lián)著網(wǎng)模型的一個可達標識。樹中的葉節(jié)點分為兩類：①復制節(jié)點，它與可達樹中之前出現(xiàn)的某個節(jié)點關聯(lián)的標識相同；②終端節(jié)點，該節(jié)點關聯(lián)的標識為死標識，死標識下不存在可使能的變遷。2.3節(jié)已經(jīng)指出，伴隨Petri網(wǎng)模型的每個死標識均對應源程序的一個潛在死鎖。

已有不少工作基于可達樹進行Petri網(wǎng)死標識的分析和檢測[9,28-29]，本章在傳統(tǒng)可達樹構造算法的基礎上，基于各個變遷所對應并發(fā)原語的含義，為每個死標識生成一個用于死鎖重演的程序調度方案，并稱包含該死鎖重演調度信息的可達樹為死鎖檢測可達樹。

死鎖檢測可達樹的構造思想如下：首先，構造伴隨Petri網(wǎng)模型的可達樹；之后，對于可達樹中每個死標識對應的終端節(jié)點，求取根節(jié)點到終端節(jié)點的變遷序列對應的操作序列；最后，基于各個死標識對應的操作序列，計算序列中涉及的每個鎖對象的授權線程序列。各個鎖對象的授權線程序列就是后續(xù)重演的依據(jù)，據(jù)此可生成一個確定性的程序調度方案，具體方法如下：

對于可達樹中某終端節(jié)點，假設從根節(jié)點到它的操作序列中出現(xiàn)了鎖對象o，而且在操作序列中o被依次授權給了線程u1u2…uk，記δ(o)=為鎖o的授權線程序列。得到各個鎖對象的授權線程序列后，可基于CalFuzzer[30]或其他程序主動調試平臺進行程序調度和死鎖重演。以CalFuzzer平臺為例，它提供了lockBefore、lockAfter、unlockAfter等程序執(zhí)行的干預函數(shù)。其中，lockBefore函數(shù)在源程序進入同步塊之前(即鎖獲取操作acq(u,o) 執(zhí)行前)被自動調用，lockAfter函數(shù)在源程序進入同步塊之后(即鎖獲取操作acq(u,o) 執(zhí)行后)被自動調用，unlockAfter函數(shù)在源程序退出一個同步塊后(即鎖釋放操作rel(u,o) 執(zhí)行后)被自動調用?；谏鲜龊瘮?shù)，可按如下規(guī)則對程序進行調度以實現(xiàn)死鎖重演：

(1)每當有線程u嘗試進入鎖對象o的同步塊(即嘗試獲取o)時，判斷u是否為δ(o)的首元素。若u不是δ(o)的首元素，則在CalFuzzer提供的lockBefore函數(shù)中阻塞線程u，并將其加入到o所關聯(lián)的一個阻塞線程池中；若u是δ(o)的首元素，則在CalFuzzer提供的lockAfter函數(shù)中刪除δ(o)的首元素；

(2)每當有線程u退出鎖對象o的同步塊(即釋放o)時，在CalFuzzer提供的unlockAfter函數(shù)中，將鎖對象o阻塞線程池中的線程全部喚醒；

(3)lockAfter函數(shù)中，一旦所有鎖對象的授權線程序列變?yōu)榭?，則喚醒所有阻塞線程池中的線程對象，后續(xù)不再對程序的運行作任何干預和調度；

(4)每次LockBefore函數(shù)被調用，都判斷當前程序執(zhí)行狀態(tài)下是否已經(jīng)觸發(fā)死鎖。若有程序死鎖被觸發(fā)，且各個鎖對象的授權線程序列為空，則說明潛在死鎖重演成功；若有死鎖被觸發(fā)，但存在鎖對象的授權線程序列不空，則說明程序存在另一個真實死鎖，本文試圖重演的潛在死鎖的真實性無法判定；若沒有死鎖被觸發(fā)，而且程序正常終止，則說明潛在死鎖是一個誤報。

以圖4中的伴隨Petri網(wǎng)為例，其對應的死鎖檢測可達樹如圖5所示。樹中存在兩個終端節(jié)點(復制節(jié)點的標識采用綠色字體，終端節(jié)點用紅色，藍色標簽為各個變遷對應的并發(fā)操作)，從根節(jié)點到他們的變遷序列分別為t1t2t3t4t5t6t7t8t9t10t11t17t12和t1t2t3t4t5t6t7t8t9t10t12t11t17。這兩個變遷序列均涉及到鎖對象G、o1和o2，而且兩個序列中鎖對象的授權序列也是一致的：鎖對象G依次授權給threadA、threadB、threadA，鎖對象o1依次授權給threadA、threadA，鎖對象o2依次授權給threadA、threadB。進行重演時，假設源程序仍嘗試按表1未觸發(fā)死鎖的操作序列運行。按前述調度規(guī)則，可得表5中的調度方案(表中13行第3列操作意味著線程嘗試執(zhí)行它時被阻塞，15行第3列的操作意味著被阻塞線程喚醒后又一次執(zhí)行前面阻塞發(fā)生時的操作，加粗字體的操作構成觸發(fā)死鎖的操作集)。最終，潛在死鎖會被觸發(fā)，重演成功，驗證了死鎖的真實性。

表5 死鎖重演過程實例

續(xù)表5

綜上所述，基于本文所提方法，一方面對程序實例Program1的潛在死鎖進行了更為準確的檢測，相比傳統(tǒng)基于鎖圖、環(huán)鎖依賴鏈、分段圖和分段鎖圖減少了死鎖誤報現(xiàn)象的發(fā)生；另一方面，給出了一種用于死鎖重演的確定性程序調度方案生成方法與調度策略，相比傳統(tǒng)的隨機性調度方法，可以更為方便和有效地對潛在死鎖進行重演和驗證。

4 工作對比與實驗評估

第1章結合程序1從原理上說明了本文方法相比iGoodlock等經(jīng)典動態(tài)分析方法的優(yōu)勢，本章進一步結合CalFuzzer開源項目中公開的多個Java多線程程序實例[注]CalFuzzer項目及其程序實例鏈接https://github.com/ksen007/calfuzzer/tree/master/test/benchmarks/testcases,Demo2程序實例鏈接https://pan.baidu.com/s/1aRyD7jAEKWSS0EGkuZDFpg，提取碼：bmv9。進行實驗評估。實驗對比結果如表6所示，實驗時的機器配置為：Intel(R) Xeon(R) Platinum 8163 CPU @ 2.50 GHz、內(nèi)存2 GB、操作系統(tǒng)為Ubuntu 5.4.0。(表中的CF代表Clafuzzer集成的死鎖檢測和重演方法)

就檢測準確性而言，CalFuzzer中集成的是iGoodlock死鎖檢測方法，該方法使用環(huán)鎖依賴鏈檢測潛在死鎖，如第1章所述，該方法相比本文方法會產(chǎn)生更多的死鎖誤報。表1中程序Demo2和本文實例就體現(xiàn)了這一點，iGoodlock算法報告的潛在死鎖數(shù)更多，而且多出的死鎖均為誤報。對于每個檢測到的潛在死鎖，CalFuzzer基于DeadlockFuzzer進行死鎖重演，其本質是一種隨機的重演策略，而本文的調度方案是確定性的，由此導致的結果是：同一個真實死鎖，DeadlockFuzzer通常需要運行多次方能觸發(fā)成功，而本文基于鎖授權線程序列只需一次重演即可(實驗中，對于程序實例Test1a和Test1b，運行了3次以上方才重演成功)。

表6 程序死鎖檢測的實驗結果對比

從時間性能來看，在潛在死鎖的檢測階段，本文所提方法耗時更多，本質上是因為本文構建的程序模型包含了程序更多的行為信息，而且Petri網(wǎng)的死鎖檢測算法本身耗時較多，但這種時間性能的降低換來的是潛在死鎖檢測準確度的提高；在潛在死鎖的重演階段，本文所提的重演方法效率更高，因為本文給出的是一種確定性的程序調度方案，而CalFuzzer的調度方案是隨機的、通常需要多次運行方能重演成功。

5 結束語

本文提出一種新型的多線程程序死鎖檢測和重演方法，首先捕獲程序運行軌跡中各類并發(fā)原語對應的操作，據(jù)此構建程序的Petri網(wǎng)模型；之后，將程序的死鎖檢測問題轉化為程序模型伴隨Petri網(wǎng)的死標識檢測問題；最后，在傳統(tǒng)可達樹的基礎上，計算并擴充了可用于死鎖重演的程序調度方案，給出了具體的程序調度規(guī)則，為潛在死鎖的真實性判定奠定了基礎。文中分析和程序實例表明，所提出的基于程序Petri網(wǎng)模型的死鎖檢測方法能排除更多的誤報，而且給出的死鎖重演方案簡單易懂，相比過往隨機性的程序調度方案可以更為有效地完成死鎖重演。然而，本文方法也存在一定的不足，尤其是程序包含很多的并發(fā)行為時，所構建Petri網(wǎng)模型的可達樹可能出現(xiàn)狀態(tài)爆炸問題，后續(xù)將借助Petri網(wǎng)展開等方法來緩解該問題。

此外，本文僅給出了所提死鎖檢測和重演方法的基本原理，在開發(fā)具體的應用軟件時還存在諸多技術問題。例如，在死鎖檢測和重演兩個不同的階段需分別運行程序，而程序中鎖對象和線程對象在兩次不同的運行中具有不同的ID，如何進行同一對象在兩次運行中不同ID間的對應，這在以往工作中是一個難點。幸運的是，該問題基于本文方法是可以有效解決的，限于篇幅，具體解決方法在后續(xù)工作中給出。此外，影響死鎖的并發(fā)原語還包括wait/notify等并發(fā)原語，如何對它們進行Petri網(wǎng)建模和分析也是后續(xù)工作需要解決的問題。