多線程程序數據競爭檢測和驗證方法研究綜述

禹振　楊振　蘇小紅　王甜甜

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

關鍵詞：多線程；數據競爭檢測；數據競爭驗證

0引言

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

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

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

目前已經提出的數據競爭檢測和驗證方法在不同程度上呈現有一定的不足。探討解析可得結論如下：

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

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

1數據競爭檢測和驗證方法的研究

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

1.1靜態數據競爭檢測

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

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

1.2動態數據競爭檢測

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

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

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

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

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

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