多線程程序數(shù)據(jù)競爭檢測和驗證方法研究綜述

禹振　楊振　蘇小紅　王甜甜

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

關鍵詞：多線程；數(shù)據(jù)競爭檢測；數(shù)據(jù)競爭驗證

0引言

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

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

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

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

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

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

1數(shù)據(jù)競爭檢測和驗證方法的研究

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

1.1靜態(tài)數(shù)據(jù)競爭檢測

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

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

1.2動態(tài)數(shù)據(jù)競爭檢測

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

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

Von和Elmas等在Eraser的基礎上對基于lockset算法的動態(tài)數(shù)據(jù)競爭檢測方法進行了精細和擴展，使得能夠更加精確和有效地檢測對象級別的數(shù)據(jù)競爭。

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

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

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