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

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

0 引言

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

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

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

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

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

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

(2)在所得程序Petri網(wǎng)模型的基礎(chǔ)上，對傳統(tǒng)Petri網(wǎng)可達(dá)樹技術(shù)進(jìn)行擴(kuò)充，進(jìn)行程序死鎖檢測的同時(shí)可得到死鎖重演的一種確定性調(diào)度方案，這為死鎖的真實(shí)性奠定了基礎(chǔ)。

1 動(dòng)機(jī)與研究路線

1.1 實(shí)例分析

圖1給出了一個(gè)多線程程序?qū)嵗?個(gè)線程(主線程、threadA和threadB)、3個(gè)鎖對象(G、o1、o2)。主線程首先啟動(dòng)線程threadA，該線程在一個(gè)循環(huán)體中順序獲取鎖G、o1和o2，然后逐個(gè)釋放。第一次循環(huán)過程中，線程在獲取鎖G后會(huì)啟動(dòng)線程threadB，然后會(huì)先獲取G，釋放G后再依次獲取o2和o1。threadA第二次執(zhí)行循環(huán)體時(shí)不進(jìn)行線程threadB的新建和啟動(dòng)。不難發(fā)現(xiàn)，“threadA第二次執(zhí)行循環(huán)體時(shí)順序獲取鎖o1和o2的操作”與“threadB釋放G后順序獲取o2和o1”的操作會(huì)導(dǎo)致程序死鎖的發(fā)生。而“threadA第一次執(zhí)行循環(huán)體時(shí)順序獲取鎖o1和o2的操作”與“threadB順序獲取o2和o1”的操作不會(huì)導(dǎo)致死鎖，因?yàn)榈谝淮窝h(huán)執(zhí)行過程中鎖G始終被threadA持有，此時(shí)threadB因無法獲得鎖G而不會(huì)執(zhí)行獲取o2和o1的操作。

表1 多線程程序Program 1的一次運(yùn)行軌跡

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

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

表2 不同方法對表1運(yùn)行軌跡進(jìn)行動(dòng)態(tài)分析所得死鎖檢測結(jié)果

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

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

1.2 研究路線

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

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

2.1 多線程程序的運(yùn)行軌跡

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

α∈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ā)操作構(gòu)成的序列全體；

u,v∈Tid表示線程，l∈Lock表示鎖，c表示一個(gè)程序語句的標(biāo)簽；

fork(u,v)表示線程u派生并啟動(dòng)一個(gè)新線程v；

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

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

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

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

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

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

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

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

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

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

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

續(xù)表3

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

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

表4 導(dǎo)致死鎖的實(shí)例程序的運(yùn)行軌跡

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表5 死鎖重演過程實(shí)例

續(xù)表5

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

4 工作對比與實(shí)驗(yàn)評估

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

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

表6 程序死鎖檢測的實(shí)驗(yàn)結(jié)果對比

從時(shí)間性能來看，在潛在死鎖的檢測階段，本文所提方法耗時(shí)更多，本質(zhì)上是因?yàn)楸疚臉?gòu)建的程序模型包含了程序更多的行為信息，而且Petri網(wǎng)的死鎖檢測算法本身耗時(shí)較多，但這種時(shí)間性能的降低換來的是潛在死鎖檢測準(zhǔn)確度的提高；在潛在死鎖的重演階段，本文所提的重演方法效率更高，因?yàn)楸疚慕o出的是一種確定性的程序調(diào)度方案，而CalFuzzer的調(diào)度方案是隨機(jī)的、通常需要多次運(yùn)行方能重演成功。

5 結(jié)束語

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

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