一種基于調(diào)用鏈的Java程序數(shù)據(jù)競爭靜態(tài)檢測算法＊

宋東海 陳二虎

（1.92493部隊(duì)88分隊(duì) 葫蘆島 125001）（2.92515部隊(duì) 葫蘆島 125001）

1 引言

隨著多核技術(shù)的出現(xiàn)和GUI程序的廣泛應(yīng)用，為有效利用計(jì)算資源，提高系統(tǒng)效率，而廣泛采用并發(fā)程序設(shè)計(jì)。雖然Java編程語言為編寫多線程程序提供了強(qiáng)大的語言支持，但是編寫正確高效的多線程并發(fā)程序仍然比較困難。在多線程程序中，當(dāng)兩個(gè)線程在無時(shí)序約束的情況下訪問同一內(nèi)存位置并且至少有一個(gè)是寫訪問時(shí)，就會(huì)導(dǎo)致數(shù)據(jù)競爭［1］。粗粒度的保守機(jī)制可以避免數(shù)據(jù)競爭，但與此同時(shí)可能會(huì)產(chǎn)生死鎖，并發(fā)多線程編程導(dǎo)會(huì)致許多特定的優(yōu)化和檢錯(cuò)問題。高效、精確的競爭檢測對于提高軟件可靠性，增強(qiáng)系統(tǒng)的穩(wěn)定性具有重要意義。

2 Java數(shù)據(jù)競爭檢測

2.1 競爭檢測技術(shù)研究現(xiàn)狀

按照競爭檢測的時(shí)機(jī)，數(shù)據(jù)競爭檢測可分為競爭動(dòng)態(tài)檢測、競爭靜態(tài)檢測。競爭動(dòng)態(tài)檢測主要有基于發(fā)生序（happen－before order）［2～3］、基于鎖集（lock－set）［4～5］以及其混合方法［6～7］，采用插樁技術(shù)能獲得變量和別名的準(zhǔn)確信息，準(zhǔn)確捕獲共享內(nèi)存訪問的發(fā)生序和鎖集信息，幾乎不產(chǎn)生誤報(bào)（false－positive），但依賴于程序輸入，只分析與程序執(zhí)行路徑有關(guān)的代碼，會(huì)漏報(bào)（false－negative）一些真正的數(shù)據(jù)競爭并且開銷很大。競爭靜態(tài)檢測是程序編譯時(shí)或者編譯后對源程序或者目標(biāo)代碼進(jìn)行檢測，需要分析整個(gè)程序，不像動(dòng)態(tài)競爭檢測，無需插樁，不需占用程序的運(yùn)行時(shí)間，不受程序規(guī)模限制。但因靜態(tài)分析的不可判定性［8］，對于任何一個(gè)有一定規(guī)模的軟件，希望獲得關(guān)于它的完備描述通常是不現(xiàn)實(shí)的［9］，往往采用不完備的近似算法，靜態(tài)分析的結(jié)果比較保守。

由于并發(fā)程序中線程調(diào)度的不確定性，精確的數(shù)據(jù)競爭檢測是一個(gè)NP－h(huán)ard［1］問題，數(shù)據(jù)競爭很難被發(fā)現(xiàn)和重現(xiàn)，并且數(shù)據(jù)競爭不像死鎖，不會(huì)導(dǎo)致程序的突然失效，無法繼續(xù)運(yùn)行，大量的誤報(bào)會(huì)使得使用者對靜態(tài)分析工具失去信心和耐心。含有數(shù)據(jù)競爭錯(cuò)誤的程序調(diào)試是非常困難的，為了提高分析精度，減少誤報(bào)，便于調(diào)試程序，有必要提高數(shù)據(jù)競爭靜態(tài)檢測的精度。

2.2 Java內(nèi)存模型

內(nèi)存模型描述的是程序中變量（實(shí)例域、靜態(tài)域、數(shù)組元素等）之間的關(guān)系，以及在實(shí)際計(jì)算機(jī)系統(tǒng)中將變量存儲(chǔ)到內(nèi)存和從內(nèi)存取出變量的底層細(xì)節(jié)。

JMM（Java memory model）是JVM的內(nèi)存模型，規(guī)范了線程之間通過內(nèi)存的交互原則。JMM定義了一個(gè)統(tǒng)一的內(nèi)存管理模型，屏蔽了底層平臺(tái)內(nèi)存管理細(xì)節(jié)，具體由各個(gè)虛擬機(jī)來實(shí)現(xiàn)對內(nèi)存的動(dòng)態(tài)管理，包括對內(nèi)存的分配以及回收。JMM將線程能訪問的內(nèi)存分為主內(nèi)存（main memory）與工作內(nèi)存（working memory），Java中所有類實(shí)例域、靜態(tài)域、數(shù)組都儲(chǔ)存在主內(nèi)存中，對于所有線程都是共享的。每個(gè)線程都有自己的工作內(nèi)存，工作內(nèi)存中保存的是主內(nèi)存中某些變量的拷貝和臨時(shí)變量，線程內(nèi)對所有變量的操作都是在工作內(nèi)存中進(jìn)行，線程之間無法相互直接訪問，變量傳遞均需要通過主內(nèi)存完成，數(shù)據(jù)競爭只可能出現(xiàn)在主內(nèi)存變量上。

2.3 Java語言數(shù)據(jù)競爭靜態(tài)檢測

Java程序競爭靜態(tài)檢測主要有流非敏感的類層次型約束的系統(tǒng)，流敏感的基于鎖集合算法的靜態(tài)檢測，路徑敏感的模型檢測器。Choi［10］等人將競爭檢測分成一系列分析階段，包括逃逸分析階段、別名分析階段、競爭檢測階段。在此基礎(chǔ)上斯坦福Naik［11］等人提出了一種K－對象敏感、上下文敏感Java程序競爭靜態(tài)檢測算法，算法分為五個(gè)階段：1）可達(dá)競爭對檢測（originalRaces）；2）別名競爭對檢測（aliasingRaces）；3）逃逸競爭對檢測（escapingRaces）；4）并發(fā)競爭對檢測（paralleRaces）；5）未加鎖競爭對檢測（unlockedRaces）。該算法隨著各階段的進(jìn)行，逐漸縮小檢測范圍，采用了自適應(yīng) K－對象敏感（k－object－sensitive）的上下文信息，提高了靜態(tài)分析的精度。張昱［7］等人基于即時(shí)編譯器（just－in time，JIT）采用增量式競爭檢測技術(shù)，提高了競爭檢測的精度。

2.4 并發(fā)程序靜態(tài)切片

程序切片作為一種對程序結(jié)構(gòu)進(jìn)行分析的技術(shù)，可以用在程序信息分析方面，從而增強(qiáng)對程序的理解、調(diào)試、測試和確認(rèn)。1993年，J.Cheng［12］最早考慮了并發(fā)程序的靜態(tài)切片，并提出了一種基于程序依賴網(wǎng)（PDN）的并發(fā)程序切片方法。1998年，J.Krinke［13］針對多線程程序提出了一種新的靜態(tài)切片算法，引入了線程控制流圖、線程程序依賴圖，同時(shí)提出了線程證據(jù)的概念，用來描述多線程程序的執(zhí)行路徑。對程序的分析主要考慮程序數(shù)據(jù)依賴和控制依賴關(guān)系。Ranganath［14］于2003年又提出了并發(fā)程序干擾依賴（Interference Dependence）和現(xiàn)成依賴（Ready Dependence）的概念。2007年，戚曉芳［15］提出了線程交互可達(dá)圖，構(gòu)建了以程序狀態(tài)和語句二元組為節(jié)點(diǎn)的并發(fā)程序依賴圖。隨著Java等語言并發(fā)程序的應(yīng)用越來越多，多線程程序的分析、調(diào)試、測試比傳統(tǒng)單線程程序更復(fù)雜。并發(fā)程序切片工具可以使并發(fā)程序的理解和維護(hù)等工作更容易完成。

3 類層次的Java競爭靜態(tài)檢測算法（Class－lever DC）

雖然競爭靜態(tài)檢測作為一種有效的數(shù)據(jù)競爭檢測方法，但是競爭靜態(tài)檢測受到線程交互、動(dòng)態(tài)數(shù)據(jù)分配、別名信息、流信息、路徑信息、數(shù)組元素的影響，很難有精確的實(shí)現(xiàn)。為了提高檢測競爭檢測的有效性并且方便程序理解，需要對競爭靜態(tài)檢測的結(jié)果進(jìn)行確認(rèn)，但是對數(shù)據(jù)競爭結(jié)果進(jìn)行確認(rèn)費(fèi)時(shí)費(fèi)力。

本文將競爭靜態(tài)檢測技術(shù)和靜態(tài)程序切片技術(shù)結(jié)合起來，提出了一種類層次的Java數(shù)據(jù)競爭靜態(tài)檢測算法。該算法首先以函數(shù)調(diào)用鏈為上下文信息對類域進(jìn)行分析，找出可能數(shù)據(jù)競爭，然后通過對函數(shù)調(diào)用鏈靜態(tài)切片分析，并結(jié)合數(shù)據(jù)競爭的必要條件，去掉不可能數(shù)據(jù)競爭。

3.1 數(shù)據(jù)競爭必要條件

用五元組（t，p，v，e，ls）表示線程t在程序點(diǎn)p 對變量v進(jìn)行訪問e（e為讀r或?qū)憌），ls表示在程序點(diǎn)p變量v訪問時(shí)擁有的鎖集，如果線程t在程序點(diǎn)p對變量v進(jìn)行訪問e時(shí)，v沒有被鎖保護(hù)，則ls為?。數(shù)據(jù)對（t1，p1，v1，e1，ls1），（t2，p2，v2，e2，ls2）為數(shù)據(jù)競爭的必要條件：

1）t1≠t2；

2）alias（v1，v2）＝true；

3）程序點(diǎn)p1、p2處對變量v1、v2的訪問語句能夠并發(fā)執(zhí)行，不具有發(fā)生序；

4）e1，e2至少一個(gè)為寫操作；

5）?l1∈ls1，?l2∈ls2，alias（l1，l2）＝false（v1，v2在程序點(diǎn)p不被同一別名鎖保護(hù)）。

3.2 競爭檢測算法描述

Narayanasamy［16］發(fā)現(xiàn)程序中的絕大部分?jǐn)?shù)據(jù)競爭是無害的。通過對Java并發(fā)程序進(jìn)行分析，可以發(fā)現(xiàn)產(chǎn)生數(shù)據(jù)競爭的類是非常少的，需要更加重視頻繁使用以及更值得關(guān)注的類，因此本文提出了類層次的Java程序數(shù)據(jù)競爭靜態(tài)檢測算法。

3.2.1 類層次的Java數(shù)據(jù)競爭靜態(tài)檢測算法

類層次的Java程序數(shù)據(jù)競爭靜態(tài)檢測算法包含兩個(gè)部分：類層次數(shù)據(jù)競爭預(yù)測部分和以函數(shù)調(diào)用鏈的數(shù)據(jù)競爭確認(rèn)部分。

類層次的Java程序數(shù)據(jù)競爭靜態(tài)檢測算法：

類層次的Java程序數(shù)據(jù)競爭靜態(tài)檢測算法的數(shù)據(jù)競爭預(yù)測部分對一個(gè)類的每個(gè)字段進(jìn)行分析，找出一對可能產(chǎn)生數(shù)據(jù)競爭的程序語句。記一個(gè)待分析類的字段集合F（包含實(shí)例字段和靜態(tài)字段）、函數(shù)集合M，啟動(dòng)線程集T（T表示啟動(dòng)線程集合，包含main函數(shù)和start函數(shù)啟動(dòng)的線程。滿足關(guān)系；T＝｛（［］，main）｝∪｛（o，start）｝），字段操作E（E＝｛r，w｝），函數(shù)調(diào)用鏈L（L為 m1－m2－m3…mn－1mn，表示函數(shù) mn調(diào)用 mn－1，…，m3調(diào)用 m2，m2調(diào)用m1），則函數(shù)m中對字段f操作記為f－e－m∈F×E×M，線程t中調(diào)用函數(shù)m記為m－l－t∈M×L×T。因此f－e－m－l－t∈F×E×M×L×T表示線程t以l為調(diào)用鏈的方法m內(nèi)對類字段f進(jìn)行e操作，用OP表示這些操作的集合。

如圖1所示，我們從類Class的代碼中可以獲得類的F×E×M集合，從程序函數(shù)調(diào)用圖中可以獲得M×L×T集合。根據(jù)數(shù)據(jù)競爭必要條件4），利用笛卡爾積運(yùn)算可以計(jì)算待分析類上的數(shù)據(jù)競爭〈f－w／r－m1－l1－t1，f－wm2－l2－t2〉。

圖1 數(shù)據(jù)競爭預(yù)測

圖2 數(shù)據(jù)競爭確認(rèn)

如圖2所示，〈f－e－m1－l1－t1，f－e－m2－l2－t2〉表示一個(gè)可能的數(shù)據(jù)競爭對，以函數(shù)調(diào)用鏈的數(shù)據(jù)競爭確認(rèn)部分對類層次的數(shù)據(jù)競爭預(yù)測部分產(chǎn)生的數(shù)據(jù)競爭進(jìn)行確認(rèn)。通過MHP（可能并行執(zhí)行）分析［17］，根據(jù)數(shù)據(jù)競爭必要條件3）去掉不能并發(fā)執(zhí)行的語句對；通過TLO（線程局部對象）分析［18］，根據(jù)數(shù)據(jù)競爭必要條件1）去掉不能被多個(gè)線程訪問變量的語句對；最后進(jìn)行別名鎖分析，根據(jù)數(shù)據(jù)競爭必要條件2）和5），更進(jìn)一步對競爭結(jié)果進(jìn)行確認(rèn)，判斷兩個(gè)引用變量是否可能別名，如果不可能的話，則說明不可能產(chǎn)生數(shù)據(jù)競爭。如果兩個(gè)引用變量可能別名，則在此基礎(chǔ)上判斷它們是否被相同鎖保護(hù)，如果被同一鎖保護(hù)，則說明對共享變量的訪問被同步保護(hù)，不會(huì)產(chǎn)生數(shù)據(jù)競爭，否則說明可能產(chǎn)生數(shù)據(jù)競爭。

3.2.2 算法分析

A和B為待分析的兩個(gè)類，其中類A有字段f1，類B有字段f2，類B上的可能數(shù)據(jù)競爭對記為〈B.f2－e－B.mi－l1－t1，B.f2－e－B.mj－l2－t2〉，類B 的函數(shù)mi訪問（直接或間接）類A的字段f1，類B的函數(shù)mj訪問（直接或間接）類A的字段f1，因此，類A上的可能數(shù)據(jù)競爭對可以記為〈A.f1－e－A.mp－mp＋1－…－B.mi－l1－t1，A.f1－e－A.mq－mq＋1－B.mj－l2－t2〉。消除類A 上數(shù)據(jù)競爭〈A.f1－e－A.mp－mp＋1－…－B.mi－l1－t1，A.f1－e－A.mq－mq＋1－B.mj－l2－t2〉的同時(shí)可以消除與之關(guān)聯(lián)的類B上的數(shù)據(jù)競爭〈B.f2－e－B.mi－l1－t1，B.f2－e－B.mj－l2－t2〉，即消除一個(gè)類上的數(shù)據(jù)競爭同時(shí)可以消除與之有關(guān)聯(lián)類上的相應(yīng)數(shù)據(jù)競爭。類A上的函數(shù)相對于類B上的函數(shù)處于函數(shù)調(diào)用鏈的底層，類層次的數(shù)據(jù)競爭算法預(yù)測部分以類為基礎(chǔ)對程序進(jìn)行數(shù)據(jù)競爭預(yù)測，使得我們可以根據(jù)類之間的關(guān)系來安排類上數(shù)據(jù)競爭檢測的順序，可以首先分析類層次較低的類（一般它的函數(shù)處于函數(shù)調(diào)用鏈的底層）或者更需要關(guān)注的類（程序中頻繁使用的類或?qū)θ蝿?wù)關(guān)鍵的類）。

在以函數(shù)調(diào)用鏈為上下文的數(shù)據(jù)競爭確認(rèn)部分，利用數(shù)據(jù)競爭的必要條件，對以類為層次的數(shù)據(jù)競爭預(yù)測部分產(chǎn)生的可能數(shù)據(jù)競爭進(jìn)行確認(rèn)，逐步求精，最后可以獲得較精確的數(shù)據(jù)競爭檢測結(jié)果，但由于靜態(tài)程序分析的不可判定性，由于是根據(jù)數(shù)據(jù)競爭的必要條件進(jìn)行判斷，檢測結(jié)果有一定的誤報(bào)率。

可以通過對程序中的每個(gè)類執(zhí)行一次算法，就會(huì)獲得整個(gè)程序的數(shù)據(jù)競爭。并且以函數(shù)調(diào)用鏈為上下文，縮小了程序分析的范圍，易于理解競爭出現(xiàn)的原因，讓程序員關(guān)注函數(shù)調(diào)用鏈上的代碼，便于指導(dǎo)修復(fù)程序中的競爭缺陷。

4 競爭檢測實(shí)例分析

本節(jié)將通過一個(gè)Java多線程程序?qū)嵗敿?xì)介紹了競爭靜態(tài)檢測原型工具的分析執(zhí)行過程。以附錄1程序進(jìn)行實(shí)例分析。我們對類A進(jìn)行分析，首先獲得F＝｛f4｝，M＝｛A.init，A.set，A.get｝（其中init為類的構(gòu)造函數(shù)），F(xiàn)－EM＝｛f4－r－A.get，f4－w－A.init，f4－w－A.get｝。

從附錄1程序的函數(shù)調(diào)用圖中可以獲得M－L－T＝｛A.get－B.get－T.main，A.get－B.get－T.run，A.set－B.set－T.main，A.init－B.init－T.main，A.set－B.set－T.run｝，為了方便后面闡述，F(xiàn)－E－M－L－T記為：

防疫部門應(yīng)加大對疫情的監(jiān)測力度，并制定一套完善的疫情預(yù)警報(bào)告制度，時(shí)刻留意牧區(qū)羊群的生長狀況。一旦發(fā)現(xiàn)存在疑似感染小反芻獸疫病的羊只，應(yīng)在第一時(shí)間內(nèi)進(jìn)行隔離，待其恢復(fù)健康后，才能繼續(xù)同群飼養(yǎng)。因此，積極做好對牧區(qū)疫情的監(jiān)測工作是控制小反芻獸疫病毒肆意傳播的重要舉措。

①f4－r－A.get－B.get－T.main；②f4－r－A.get－B.get－T.run；

③f4－w－A.set－B.set－T.main；④f4－w－A.init－B.init－T.main；⑤f4－w－A.set－B.set－T.run（其中⑤屬于多個(gè)線程）

如表1所示，對于可能競爭〈①，⑤〉，通過對調(diào)用鏈①，⑤分析，調(diào)用鏈①，⑤分別對v1.v8.f4（即同一內(nèi)存快）進(jìn)行讀寫，并且他們沒有被鎖保護(hù)，會(huì)產(chǎn)生數(shù)據(jù)競爭。

表1 競爭詳細(xì)信息

如表2所示，可以對類層次生成的其他可能數(shù)據(jù)競爭進(jìn)行分析。

表2 競爭檢測

通過對調(diào)用鏈②，③分析，v2，v7屬于別名，并且被別名鎖（v2，v7）保護(hù)，則不會(huì)產(chǎn)生數(shù)據(jù)競爭。對于可能競爭〈②，④〉，通過對調(diào)用鏈②，④分析，調(diào)用鏈②先于④執(zhí)行，他們不會(huì)產(chǎn)生數(shù)據(jù)競爭。對于可能競爭〈②，⑤〉，通過對調(diào)用鏈②，⑤分析，調(diào)用鏈②，⑤分別對v1.v8.f4，v2.v8.f4進(jìn)行讀寫，但是v1，v2屬于不同對象，則不會(huì)產(chǎn)生數(shù)據(jù)競爭。對于可能競爭〈③，⑤〉，通過對調(diào)用鏈③，⑤分析，調(diào)用鏈③，⑤分別對v1.v8.f4，v2.v8.f4進(jìn)行讀寫，但是v1，v2屬于不同對象，則不會(huì)產(chǎn)生數(shù)據(jù)競爭。對于可能競爭〈④，⑤〉，通過對調(diào)用鏈④，⑤分析，調(diào)用鏈④先于調(diào)用鏈⑤執(zhí)行，則不會(huì)產(chǎn)生數(shù)據(jù)競爭。對于可能競爭〈⑤，⑤〉，調(diào)用鏈⑤，⑤分別對v1.v8.f4（即同一內(nèi)存快）進(jìn)行讀寫，并且他們沒有被鎖保護(hù)，會(huì)產(chǎn)生數(shù)據(jù)競爭。

表3 競爭檢測結(jié)果

同理，對類B，T進(jìn)行分析，可以獲得整個(gè)程序的數(shù)據(jù)競爭。通過對每個(gè)類進(jìn)行分析，我們發(fā)現(xiàn)類A〈①f4－r－A.get－B.get－T.main，⑤f4－w－A.set－B.set－T.run〉上的數(shù)據(jù)競爭與類B〈①f3－r－B.get－T.main，⑤f3－w－B.set－T.run〉上的數(shù)據(jù)競爭是有關(guān)聯(lián)的，實(shí)際上是由于對類B的A類型實(shí)例字段f3的訪問導(dǎo)致的?？梢酝ㄟ^對類A的訪問進(jìn)行保護(hù)，消除類A，類B上的數(shù)據(jù)競爭。同理可以消除類T的數(shù)據(jù)競爭。

5 結(jié)語

數(shù)據(jù)競爭不會(huì)導(dǎo)致程序的突然失效，而未受到開發(fā)人員的重視，雖然現(xiàn)在的數(shù)據(jù)競爭檢測主要是以動(dòng)態(tài)競爭檢測為主，但是由于靜態(tài)競爭檢測不需要對運(yùn)行程序進(jìn)行插裝，不會(huì)影響系統(tǒng)運(yùn)行。隨著靜態(tài)競爭檢測技術(shù)分析結(jié)果精度的不斷提高，靜態(tài)競爭檢測越來越受到重視。本文通過引入切片技術(shù)，提出了一種類層次基于調(diào)用鏈的Java數(shù)據(jù)競爭靜態(tài)檢測算法。通過實(shí)例分析，發(fā)現(xiàn)類之間的數(shù)據(jù)競爭是有關(guān)聯(lián)的，對一個(gè)類進(jìn)行修改，不僅可以消除這個(gè)類上的數(shù)據(jù)競爭，還能消除與之有關(guān)聯(lián)的類上的部分?jǐn)?shù)據(jù)競爭。實(shí)例表明，該算法是可行的，我們對整個(gè)程序進(jìn)行數(shù)據(jù)競爭檢測分析，可以首先對待分析的各個(gè)類按照使用頻率和重要程度進(jìn)行排序，然后對各個(gè)類進(jìn)行數(shù)據(jù)競爭檢測，由于各個(gè)類上的數(shù)據(jù)競爭是有關(guān)聯(lián)的，并且對于修復(fù)程序中的競爭缺陷具有指導(dǎo)意義。下一步可以進(jìn)一步研究類之間的關(guān)系與其上數(shù)據(jù)競爭分布的規(guī)律，安排類之間競爭檢測的順序，在保證軟件質(zhì)量的同時(shí)，盡可能的節(jié)約測試成本。

［1］Netzer R H B，Miller B P.What are race conditions？some issues and formalizations［J］.ACM Letters on Programming Languages and Systems，1992，1（1）：74－88.

［2］Adve S V，Hill M D，Miller B P，et al.Detecting data races on weak memory systems［C］／／Proceedings of the 18th Annual International Symposium on Computer Architecture（ISCA'91）.Toronto，Canada，1991：234－243.

［3］Christiaens M，Brosschere K.TRaDe：A topological approach to on－the－fly race detection in Java programs［C］／／Proceedings of the 1st Java Virtual Machine Research and Technology Symposium（JVM'01）.Monterey，California，USA，2001：105－116.

［4］Agarwal R，Sasturkar A，Wang L，et al.Optimized run－time race detection and atomicity checking using partial discovered types［C］／／Proceedings of the 20th IEEE／ACM International Conference on Automated Software Engineering（ASE 2005），Long Beach，USA，November，2005：233－242.

［5］Cheng G，F(xiàn)eng M，Leiserson C，et al.Detecting data races in Cilk programs that use locks［C］／／Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures（SPAA'98），Puerto Vallarta，Mexico，1998：298－309.

［6］Yu Y，Rodeheffer T，Chen W.RaceTrack：Efficient detection of data race conditions via adaptive tracking［C］／／Proceedings of the 20th ACM Symposium on Operating Systems Principles（SOSP'05），Brighton，United Kingdom，2005：221－234.

［7］張昱，郝允允.Java程序數(shù)據(jù)競爭的增量式檢測［J］.西安交通大學(xué)學(xué)報(bào)，2009，43（8）：22－27.

［8］Landi W.Undecidability of static analysis［J］.ACM Letters on Programming Languages and Systems，1992，1（4）：323－337.

［9］梅宏，王千祥，張路，等.軟件分析技術(shù)進(jìn)展［J］.計(jì)算機(jī)學(xué)報(bào)，2009，32（9）：1697－1710.

［10］Choi J D，Loginov A，Sarkar K.Static datarace analysis for multithreaded object－oriented programs［R］.IBM Research：Technical Report RC22146，2001.

［11］Naik M.Effective static race detection for java［D］.Stanford University，2008.

［12］Cheng J.Slicing concurrent program s－A graph theoretical approach［C］／／The First International Workshop on Automated and Algorithmic Debugging.Link ping，Sweden，1993：223－240.

［13］Krnke J.Static slicing of threaded programs［J］.ACM SIGPLAN Notices，1998，33（7）：35－42.

［14］Ranganath V P，Hatcliff J.Slicing concurrent Java programs using Indus and Kaveri［J］.International Journal on Software Tools for Technology Transfer（STTT），2007，9（5－6）：489－504.

［15］戚曉芳，徐寶文，周曉宇.一種基于程序可達(dá)圖的并發(fā)程序依賴性分析方法［J］.電子學(xué)報(bào)，2007，35（2）：287－291.

［16］Narayanasamy S，Wang Z，Tigani J，et al.Automatically classifying benign and harmful data races using replay analysis［C］／／Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation（PLDI）.San Diego，California，USA，2007：22－31.

［17］Li L.A practical MHP information computation for concurrent Java programs［D］.Montreal，Canada：McGill University，2004.

［18］Halpert R.Static lock allocation［D］.Montreal，Canada：McGill University，2008.

附錄1：Java多線程樣例程序EX1（該程序出自文獻(xiàn)［1］Naik M的學(xué)位論文第13頁）