禹振　楊振　蘇小紅　王甜甜

摘要：隨著軟件規(guī)模的日益增長(zhǎng)，多線程并發(fā)程序帶來的缺陷也很快蔓延開來。數(shù)據(jù)競(jìng)爭(zhēng)作為多線程并發(fā)程序中常見的問題，經(jīng)常會(huì)導(dǎo)致程序不能正常運(yùn)行，或更為嚴(yán)重地導(dǎo)致程序直接崩潰。數(shù)據(jù)競(jìng)爭(zhēng)產(chǎn)生的條件往往都比較隱蔽和苛刻，不僅需要特定的輸入，而且還需要特定的線程執(zhí)行交錯(cuò)。因此，數(shù)據(jù)競(jìng)爭(zhēng)很難被檢測(cè)出來。本文介紹了多線程數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)和驗(yàn)證相關(guān)的研究現(xiàn)狀，并對(duì)已有的數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)和驗(yàn)證方法在檢測(cè)能力以及檢測(cè)效率等方面做出比較、分析以及歸納。同時(shí)，對(duì)未來數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)和驗(yàn)證相關(guān)的研究方向進(jìn)行了展望。

關(guān)鍵詞：多線程；數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)；數(shù)據(jù)競(jìng)爭(zhēng)驗(yàn)證

0引言

在這個(gè)多核硬件的時(shí)代，充分利用硬件帶來的優(yōu)勢(shì)，并發(fā)程序也大受歡迎并已進(jìn)入廣泛應(yīng)用中。時(shí)下，常見的Microsoft Windows或是Linux Ubuntu操作系統(tǒng)，或是Google Chrome網(wǎng)頁瀏覽器等均采用了多線程并發(fā)技術(shù)。比較流行的編程語言，如C/C++，Java和Python等也對(duì)并發(fā)程序有著良好的支持。

雖然多線程并發(fā)技術(shù)為人們提供了使用上的遍歷以及優(yōu)質(zhì)暢快的用戶體驗(yàn)和軟件交互，但是編寫多線程并發(fā)程序也是令許多開發(fā)者苦惱的事。在多線程并發(fā)程序中，由于對(duì)共享內(nèi)存空間訪問的隱蔽性以及并發(fā)線程執(zhí)行調(diào)度的隨機(jī)性，導(dǎo)致并發(fā)線程之間產(chǎn)生一些不確定的相互作用和影響。這些都給并發(fā)程序的分析帶來了現(xiàn)實(shí)嚴(yán)峻的挑戰(zhàn)，而且很容易導(dǎo)致多線程并發(fā)程序在設(shè)計(jì)上存在一些缺陷。這些缺陷往往較難調(diào)試和診斷，并且可能最終導(dǎo)致并發(fā)程序在運(yùn)行的過程中出現(xiàn)崩潰，從而造成嚴(yán)重的后果。

在并發(fā)程序的安全性缺陷中，主要包括：數(shù)據(jù)競(jìng)爭(zhēng)、原子性違背、順序違背和死鎖。具體地，數(shù)據(jù)競(jìng)爭(zhēng)是指對(duì)同一個(gè)共享內(nèi)存空間，存在若干并發(fā)訪問，并且至少有一個(gè)是寫訪問。原子性違背是指原來必須原子性執(zhí)行的指令序列，在并發(fā)交錯(cuò)的干擾下，其執(zhí)行的效果不與任何原子性指令序列的執(zhí)行效果相同，各個(gè)線程需保持的一致性遭到其他并發(fā)線程寫操作破壞。順序違背指的是一指令（組）沒有按照預(yù)期執(zhí)行，總是在另一（組）指令之前或是之后執(zhí)行。死鎖指的是某個(gè)線程集合中每一個(gè)線程都在等待該集合中的另一個(gè)線程釋放占有的互斥性資源，從而導(dǎo)致整體陷入循環(huán)等待狀態(tài)。研究分析可知，數(shù)據(jù)競(jìng)爭(zhēng)在上述常見的4種并發(fā)缺陷中占的比例較大，并且大部分是導(dǎo)致原子性違背和順序違背的根源。在圖1a）原子性違背實(shí)例中，L2和L3，以及L1和L3中對(duì)共享索引變量buf_index的訪問分別構(gòu)成數(shù)據(jù)競(jìng)爭(zhēng)：而在圖1b）順序違背實(shí)例中，L1和L2對(duì)共享變量mThread的訪問構(gòu)成數(shù)據(jù)競(jìng)爭(zhēng)。因此，如何準(zhǔn)確并且有效地檢測(cè)多線程并發(fā)程序中的數(shù)據(jù)競(jìng)爭(zhēng)缺陷即已成為頗具研究?jī)r(jià)值的重要課題。

目前已經(jīng)提出的數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)和驗(yàn)證方法在不同程度上呈現(xiàn)有一定的不足。探討解析可得結(jié)論如下：

靜態(tài)檢測(cè)方法只需要分析程序源碼，但是缺少程序運(yùn)行時(shí)的信息，導(dǎo)致報(bào)告的數(shù)據(jù)競(jìng)爭(zhēng)大部分都是誤檢。動(dòng)態(tài)檢測(cè)方法監(jiān)視程序在執(zhí)行過程中的行為，收集必要的信息來判斷哪些訪問操作構(gòu)成數(shù)據(jù)競(jìng)爭(zhēng)，但是受限于線程執(zhí)行交錯(cuò)的不確定性以及收集到信息的不完整性，該方法依然會(huì)生成很多誤檢和漏檢。動(dòng)靜結(jié)合的方法雖然能夠彌補(bǔ)各自方法的一些缺陷，但是在源程序運(yùn)行過程中引入了大量的性能開銷，同時(shí)并沒有真正顯著提升數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)的精度。數(shù)據(jù)競(jìng)爭(zhēng)驗(yàn)證方法雖然能夠精準(zhǔn)地找到數(shù)據(jù)競(jìng)爭(zhēng)，但是該方法同時(shí)會(huì)造成大量的漏檢并且驗(yàn)證效率也比較低。

本文在綜合論述以往研究的基礎(chǔ)上，對(duì)已經(jīng)存在的數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)和驗(yàn)證方法進(jìn)行了分析和比較，同時(shí)歸納提煉了這些方法的優(yōu)缺點(diǎn)。最后，討論給出了后續(xù)對(duì)于數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)和驗(yàn)證方法在未來研究的重點(diǎn)展望。

1數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)和驗(yàn)證方法的研究

迄今為止，已經(jīng)研究提出了很多數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)和驗(yàn)證的方法，主要分為3類：靜態(tài)數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)方法，動(dòng)態(tài)數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)方法以及動(dòng)靜結(jié)合的數(shù)據(jù)競(jìng)爭(zhēng)驗(yàn)證方法。下面針對(duì)各類研究成果給出完整論述和設(shè)計(jì)解析。

1.1靜態(tài)數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)

靜態(tài)數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)主要是進(jìn)行鎖集分析，從而檢測(cè)數(shù)據(jù)競(jìng)爭(zhēng)。常用的靜態(tài)數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)工具包括Warlock、RacerX、RELAY和Locksmith。其中，RacerX利用流敏感和過程間分析檢測(cè)數(shù)據(jù)競(jìng)爭(zhēng)和死鎖；Locksmith首先使用標(biāo)簽流約束和抽象控制流圖約束信息來進(jìn)行鎖集分析，然后使用標(biāo)簽流約束、抽象控制流圖約束和上下文敏感約束展開共享變量的分析，最后結(jié)合線性分析，檢測(cè)出數(shù)據(jù)競(jìng)爭(zhēng)；RELAY通過控制流圖和程序調(diào)用圖，采用自底向上的分析方式，首先進(jìn)行過程內(nèi)鎖集分析并緩存在函數(shù)標(biāo)簽中，然后開啟過程間鎖集分析，等到所有的線程相關(guān)的函數(shù)全部分析完畢，再判斷相關(guān)的共享變量是否產(chǎn)生數(shù)據(jù)競(jìng)爭(zhēng)。RELAY由于其擴(kuò)展性堪稱優(yōu)良，能夠應(yīng)用在百萬級(jí)別代碼量的程序上，因此，在實(shí)際使用過程中獲得了高度認(rèn)可與廣泛接受。

盡管靜態(tài)數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)只需要分析程序源碼、監(jiān)測(cè)效率高并且基本不會(huì)有漏報(bào)，但由于其忽略了程序執(zhí)行過程中的一些happens-before關(guān)系，因此靜態(tài)數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)方法得到的絕大部分都不是真正的數(shù)據(jù)競(jìng)爭(zhēng)。

1.2動(dòng)態(tài)數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)

動(dòng)態(tài)數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)算法主要分為基于lockset的算法、基于happens-before關(guān)系的算法以及兩者混合的hybrid算法三種。下面即順次概述各類方法的設(shè)計(jì)過程實(shí)現(xiàn)。

Savage等人提出基于lockset的動(dòng)態(tài)數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)方法Eraser，該方法在程序執(zhí)行過程中維護(hù)每個(gè)線程當(dāng)前的鎖信息，同時(shí)更新共享變量持有的鎖信息，當(dāng)共享變量不再受到鎖保護(hù)的時(shí)候，報(bào)告數(shù)據(jù)競(jìng)爭(zhēng)。

Von和Elmas等在Eraser的基礎(chǔ)上對(duì)基于lockset算法的動(dòng)態(tài)數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)方法進(jìn)行了精細(xì)和擴(kuò)展，使得能夠更加精確和有效地檢測(cè)對(duì)象級(jí)別的數(shù)據(jù)競(jìng)爭(zhēng)。

Netzer和Perkovic等基于Lamport的happens-before關(guān)系提出了使用邏輯時(shí)鐘來動(dòng)態(tài)地檢測(cè)數(shù)據(jù)競(jìng)爭(zhēng)。Happens-before關(guān)系是在多線程并發(fā)程序執(zhí)行的所有事件上的一種偏序關(guān)系。該關(guān)系要求同一個(gè)線程內(nèi)部按照時(shí)序邏輯順序執(zhí)行，而在線程間程序的執(zhí)行依賴于同步機(jī)制。一旦對(duì)一個(gè)共享內(nèi)存空間的訪問違背了happens-before關(guān)系，那么就會(huì)產(chǎn)生數(shù)據(jù)競(jìng)爭(zhēng)。

Pozniansky、Flanagan、Cai以及Ha等相繼提出了改進(jìn)后的基于happens-before關(guān)系的動(dòng)態(tài)數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)方法。其中，Djit算法使用vector-clock的形式記錄線程和共享內(nèi)存空間訪問的邏輯時(shí)鐘，同時(shí)每一個(gè)時(shí)間幀中只記錄第一個(gè)對(duì)共享內(nèi)存空間的讀/寫訪問。FastTrack認(rèn)為在一個(gè)沒有數(shù)據(jù)競(jìng)爭(zhēng)故障的程序執(zhí)行過程中，對(duì)共享內(nèi)存空間的寫訪問是有序的，而只有多個(gè)線程對(duì)同一共享內(nèi)存空間進(jìn)行讀訪問才可能是并發(fā)進(jìn)行的。因此對(duì)于寫訪問可以采用輕量級(jí)的epoch形式的邏輯時(shí)鐘，而只有并發(fā)的讀訪問才會(huì)依然采用vector-clock形式的邏輯時(shí)鐘。Loft在FastTrack的基礎(chǔ)上提出一些場(chǎng)景來進(jìn)一步減少基于vector-clock的賦值和比較操作。iFr對(duì)FastTrack實(shí)施特別簡(jiǎn)化，不再需要遍歷vector-clock的每一項(xiàng)進(jìn)行分析，而只是關(guān)注left-most和right-most兩項(xiàng)，從而將讀寫訪問操作的數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)復(fù)雜度降低到了O（1）。

Poznianskv、Jannesari、Serebryan、Nethercote、Xie和Yu等分別提出了基于hvbrid的動(dòng)態(tài)數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)方法。MultiRace首先利用改進(jìn)的lockset算法找到可疑的數(shù)據(jù)競(jìng)爭(zhēng)，然后利用Diit+算法集中檢測(cè)可行的語句對(duì)是否真正是并發(fā)的。Helgrind+將線程順序執(zhí)行的操作序列約束在一個(gè)segment中，segment能夠反映線程和線程的邏輯時(shí)鐘。Helgrind+則先SHI進(jìn)行happens-before關(guān)系的分析找到所有潛在并發(fā)的segment，而后利用lockset算法驗(yàn)證共享內(nèi)存空間的訪問是否可由公共的鎖提供保護(hù)。ThreadSanitizer同樣使用segment來表示一個(gè)線程中連續(xù)執(zhí)行的內(nèi)存訪問事件（不包括同步事件）。Segment中第一個(gè)事件包含當(dāng)前segment中所有事件的上下文信息，同時(shí)維護(hù)2個(gè)鎖集合分別表示保護(hù)讀/寫持有的鎖集合LS和LS ThreadSanitizer設(shè)計(jì)配置了2個(gè)segment集合，SS和SS-分別表示并發(fā)的讀/寫segment集合。任何對(duì)共享內(nèi)存空間的訪問都會(huì)更新并迭代遍歷這2個(gè)segment集合，利用lockset算法實(shí)現(xiàn)數(shù)據(jù)競(jìng)爭(zhēng)。Acculock在開發(fā)中使用了epoch形式的邏輯時(shí)鐘進(jìn)行happens-before關(guān)系的分析，以此為基礎(chǔ)再利用Iockset算法給出驗(yàn)證。同時(shí)Acculock再次根據(jù)lockset的包含關(guān)系卓具實(shí)效地減少了冗余操作的分析。而且，MultiLock-HB又對(duì)Acculock算法中的固有缺陷切實(shí)引入了改進(jìn)，提升了檢測(cè)數(shù)據(jù)競(jìng)爭(zhēng)的能力。SimpleLock和SimpleLock+則是分別使用標(biāo)量變量lockcnt和布爾變量iszero來對(duì)lockset算法融合了優(yōu)化改進(jìn)，加快了可疑并發(fā)操作是否被公共鎖保護(hù)分析的過程。