線程交互不變量的原子性違例錯誤并發檢測*

李蘭英，孫建達，朱素霞

哈爾濱理工大學 計算機科學與技術學院，哈爾濱 150080

1 引言

目前計算機并發體系結構已成為主流，軟件中也廣泛使用了多線程技術。與傳統的單線程順序執行程序相比，對并發程序中出現的錯誤的分析檢測不但難度高，而且代價大。并發程序有多個線程，多個線程的執行順序依賴于系統調度，由于這種調度是不確定的，在運行并發程序時，即使輸入相同，輸出卻不能保證相同，正確性難以保障。例如2003年的美加大停電（The 2003 Northeast blackout），僅僅由于電力管理系統中的一個小小的并發錯誤，導致美國及加拿大東北部停電近3天，造成了300多億美元的損失[1]。

并發錯誤常見的有數據競爭、原子性違例、時序違例等[2]。對于并發程序來說，程序的原子性比數據競爭和順序違例有更強的正確性保證[3]，并發程序的原子性特征對于判斷其是否正確運行極為重要。若某個線程對于一個共享變量的訪問序列具有整體性和不可拆分性，即原子性，則在這個訪問序列中不能有其他線程對這個共享變量實施寫操作，寫操作會破壞這個訪問序列的原子性，違背程序原子性而導致出錯就屬于原子性違例錯誤。這種錯誤經常出現在一些著名軟件中，例如Apache、MySQL等[4]。Lu等人[5]針對實際應用中的并發錯誤進行了詳細的分析和研究，得出了以下結論[6]：

（1）在所有與數據相關的并發錯誤中，有大約65%的并發錯誤是原子性違例錯誤。

（2）在所有原子性違例的錯誤中，有大約2/3的原子性違例只涉及到單個共享內存。

（3）并發錯誤的出現是因為兩個線程的交互而引起的。

很多研究人員專門針對原子性違例錯誤檢測進行了研究，例如 AtomRace[7]、AVIO[8]和 MC-AVIO[9]等方案。AtomRace在每個共享變量訪問的前后插樁，在運行時根據插樁信息檢測原子性違例。該方法無人工干預，漏檢率較低，但由于使用靜態分析確定原子性區域，導致其擴展性一般，同時由于控制線程調度，其執行開銷較大。AVIO通過對正確測試用例的訓練提取訪問交錯不變量，訪問交錯不變量即線程內未被其他線程的指令交錯的指令對。MC-AVIO通過對測試用例的訓練，得到程序的原子性遷移對，并利用這些遷移對完成檢測[10]。

當前的檢測工具多數是在線檢測。在線檢測通過軟件模擬一個CPU，令程序在其上運行，獲取相關的程序運行信息，例如Valgrind[11]。在線檢測能夠動態檢測并發錯誤，但是其時間開銷較大，而離線檢測方法速度較快，并且易于多線程或多進程技術融合，提高其檢測速度。

在相關的離線并發錯誤檢測的研究中，需要獲取程序運行的相關信息以及程序的運行蹤跡。獲取方法主要分為硬件實現和軟件實現兩類。基于硬件實現的蹤跡提取工具有低開銷、高性能等優點，但需要修改硬件，增加額外成本。基于軟件實現的二進制插樁工具具有信息量大，開銷大，對原有系統性能影響大等問題，但因為其使用靈活方便，無需對系統和硬件做出修改，所以受到廣大科研人員的歡迎[12]。

針對離線原子性違例錯誤檢測中程序運行蹤跡記錄大，冗余多，運行速度較慢的問題，本文對兩類原子性違例錯誤提出了一個基于線程交互不變量的原子性違例錯誤并發檢測算法。該算法首先提取程序的運行蹤跡，去除重復讀、重復寫等冗余數據，并使用基于無序映射的散列表將程序運行蹤跡按照訪存地址快速分塊。利用進程池和棧，離線地并發分析多個獨立的蹤跡塊，快速找出線程交互不變量，并判斷程序中是否出現了原子性違例錯誤。

2 線程交互不變量

不變量就是一些邏輯斷言，用于描述在程序運行時程序的性質保持不變，它經常出現在形式化描述和斷言聲明中[13]。每條語句執行時都會伴隨著讀寫存儲器的操作，而在多線程程序中，有些變量就會在不同線程中被使用，而原子性違例錯誤往往就發生在對這些共享變量的訪問過程中。因此，本文選取程序運行中對內存訪問的依賴關系作為不變量。對內存訪問的依賴關系包括寫后讀（RAW）、寫后寫（WAW）、讀后寫（WAR）和讀后讀（RAR）。這些依賴關系中顯然RAW能夠標識多線程程序是否正確運行，因為寫操作有可能會破壞原子性操作，并且只有在讀取修改后的變量時才有可能發生錯誤。WAW中只有寫操作，并沒有讀取修改后的值，這樣的操作不會影響程序的正確性，當WAW后面又有讀操作，則能夠將WAW拆分為兩個RAW。WAR是讀取變量值后再修改，不會對程序造成影響，只有讀取修改后的數據才可能會出現問題。因此，本文選取對共享變量先寫后讀的依賴作為線程交互不變量，用來標記線程間及線程內的先寫后讀的交互順序[14]。

本文基于線程交互不變量對并發程序原子性違例錯誤進行檢測，采用＜W，R>有序對的方式記錄該不變量，W代表寫操作，R代表讀操作。R只有一種情況，LcRd，代表本地讀操作。所有寫操作的類型都是相對于讀操作的，因此W分為兩類，LcWr和RmWr。LcWr代表和讀操作處于相同線程（本地寫操作），而RmWr代表和讀操作處于不同線程（遠程寫操作）。

本文將線程交互不變量分為兩類：＜LcWr，LcRd>和＜RmWr，LcRd>。＜LcWr，LcRd>表示本地線程向共享變量寫的數據由本地線程讀出；＜RmWr，LcRd>表示遠程線程向共享變量寫的數據由本地線程讀出。如果寫操作和讀操作在同一線程，則發生＜LcWr，LcRd>，如果寫操作和讀操作在不同線程，則發生＜RmWr,LcRd>。例如圖1中，實線表示的是＜LcWr(10)，LcRd(14)>，虛線表示的是＜RmWr(4)，LcRd(14)>。

如圖1所示的模仿銀行存取款的Bank程序，展示了一個可能發生原子性違例錯誤的例子。該程序運行時可能會出現這種情況：主線程main運行到pthread_create時切換到線程ClearMoney中執行，等到ClearMoney線程結束后，main繼續執行。由于nDeposit被ClearMoney線程修改為0，最后輸出結果是0，與預期結果999不符，發生錯誤。注意到代碼第10行對變量nMoney進行了寫操作，代碼第14行對該變量進行了讀操作，形成了＜LcWr(10)，LcRd(14)>，但是在運行過程中，ClearMoney線程改寫了變量nMoney，形成了＜RmWr(4),LcRd(14)>，這兩個線程交互不變量相互交錯，發生了原子性違例，致使程序產生了原子性違例錯誤。雖然其中也包含了WAW依賴，但是由于14行的讀操作，將其拆成了相互交錯的兩個RAW依賴，從而判定錯誤。本文將這種類型的原子性違例錯誤稱為WWR錯誤。

Fig.1 Aprogram named Bank with atomicity bugs圖1 帶有原子性違例錯誤的程序Bank

另一種原子性違例錯誤形式如圖2所示。該程序會產生兩個線程交互不變量，分別為＜RmWr(I1),LcRd(J1)>和＜RmWr(I2)，LcRd(J2)>。其中由于I2的執行，導致本應在J1執行完執行的J2在I2執行后執行，破壞了線程2的if語句的完整性，發生了原子性違例，致使程序出現錯誤。本文將這種在一定范圍內發生了至少兩個＜RmWr，LcRd>類型的原子性違例錯誤稱為ReWR錯誤。

Fig.2 Aprogram segment with atomicity bugs圖2 有原子性違例錯誤的程序片段

但是原子性違例并不一定會導致原子性違例錯誤的發生，有些時候還是必要的，這種原子性違例稱作良性原子性違例。在檢測原子性違例錯誤時要對它們區別對待，否則會出現很多誤報。

如圖3所示為WWR錯誤的反例。J1執行完畢，J2正要執行，但是線程1的I1搶先執行完畢，J1和J2形成了＜LcWr(J1)，LcRd(J2)>，而I1和 J2形成了＜RmWr(I1)，LcRd(J2)>，雖然滿足了WWR錯誤的條件，但是并沒有引發原子性違例錯誤，而是符合了程序員的預期，可以通過類似這種做法保證線程的執行順序，其機制類似于自旋鎖。

Fig.3 Aprogram segment with benign atomicity violations圖3 含有良性原子性違例的程序片段

如圖4所示為ReWR錯誤的反例。I1執行完畢，線程2正常運行，這時I2執行，線程2正常結束。程序運行中會產生兩個線程交互不變量，分別是＜RmWr(I1)，LcRd(J1)>和＜RmWr(I2)，LcRd(J1)>。這樣的結果正是程序員們所期待的，可以通過類似這種做法保證線程的執行順序。雖然滿足了ReWR錯誤的條件，但程序是正確的。

Fig.4 Aprogram with benign atomicity violations圖4 帶有良性原子違例的實例

對于這兩類原子性違例錯誤，由于其特征較為清晰，故本文未采用機器學習的方式檢測這兩類原子性違例錯誤。

3 算法設計

3.1 總體架構

檢測流程如圖5所示，原子性違例錯誤檢測系統按順序依次分為蹤跡提取、蹤跡分析、錯誤檢測3個模塊。蹤跡提取模塊主要是使用Pin工具對測試用例動態插樁，提取出原始蹤跡，然后傳遞給蹤跡分析模塊，重點是在提取過程中對重復讀和重復寫蹤跡的去除。蹤跡分析模塊分析蹤跡提取模塊傳來的原始蹤跡，并對其進行分類，這其中主要利用了基于無序映射的散列表完成分類操作。錯誤檢測模塊將分類后的蹤跡加入任務隊列，進程池動態地為任務分配和調度進程，每個進程獨立運行，在提取線程交互不變量的同時，檢測WWR和ReWR兩類原子性違例錯誤。

3.2 蹤跡提取

蹤跡提取模塊使用自己編寫的Pin工具對測試用例進行插樁，提取出原始蹤跡。Pin是Intel公司提供的一個程序插裝工具，它允許在可執行程序的任何地方插入任意代碼（用C或C++編寫），這些代碼在程序運行時動態添加（修改內存映像）[15]。

本文對原子性違例錯誤進行的檢測主要依賴于對程序運行蹤跡的分析，因此蹤跡中應包含對錯誤檢測有益的信息，其中線程號（TID）是必不可少的，它主要用來標識蹤跡所屬線程，有利于記錄線程間的交互順序。指令計數器（PC）能夠標識指令，用來判斷程序運行狀況，是循環亦或是順序執行。時間戳（T）能夠記錄指令的執行時刻。指令操作（R/W）用來標識該條指令對內存的讀寫操作。訪存地址（ADDR）用來標識該條指令對某個具體的變量進行操作。

Fig.5 System architecture of atomicity violation detection圖5 原子性違例錯誤檢測系統架構

原始蹤跡中會包含許多重復讀、重復寫這樣的數據。當程序中包含了重復操作時，有可能會發生對同一變量連續重復讀寫的情況。

重復讀如圖6所示，當a＜10時，不存在重復讀，但是當a≥10時，程序就會繼續判斷a＜50是否滿足，如果還不滿足，則會繼續判斷a≥50，由此導致連續重復讀取同一變量。這些重復的讀取操作對于提取線程交互不變量沒有益處，記錄全部蹤跡與記錄一條蹤跡的效用是相同的，這樣的數據就是冗余數據，即當線程1的I1指令先于線程2的J1指令執行時，只會提取出＜RmWr(I1)，LcRd(J1)>一條線程交互不變量，記錄全部蹤跡反而會增大算法的搜索空間，降低錯誤檢測效率。因此，當遇到重復讀操作，并且處于同一線程時，算法只記錄第一條讀指令的蹤跡信息。

Fig.6 Program with repeated read圖6 重復讀

重復寫如圖7所示，圖中對指針變量pnCount進行了多次寫操作，同理于重復讀，連續重復的寫操作對于判斷程序是否出現了原子性違例錯誤也沒有益處，故當遇到重復寫操作，且處于同一線程時，只記錄最后一條寫指令的蹤跡信息。

Fig.7 Program with repeated write圖7 重復寫

去除重復讀指令蹤跡的算法如下：首先申請一個變量，用于保存上一次讀指令的蹤跡。第一條讀指令蹤跡保存到該變量并輸出保存。之后每一次新提取的讀指令的蹤跡都與上一次的比較，如果它們的TID和ADDR一致，則不輸出保存當前新提取的讀指令的蹤跡，否則，輸出保存當前新提取的讀指令的蹤跡。最后更新用于保存上一次讀指令的蹤跡的變量。重復以上操作，直到蹤跡提取完畢。

去除重復寫指令蹤跡的算法如下：首先申請一個變量，用于保存上一次寫指令的蹤跡。第一條寫指令蹤跡保存到該變量。之后每一次新提取的讀指令的蹤跡都與上一次的比較，如果它們的TID和ADDR一致，則不輸出保存當前新提取的寫指令的蹤跡，否則，將用于保存上一次寫指令的蹤跡的變量輸出保存。最后更新用于保存上一次寫指令的蹤跡的變量。重復以上操作，直到蹤跡提取完畢。

3.3 蹤跡分析

離線檢測需要獲取程序的運行蹤跡，記錄大量的相關指令信息，在大量的信息中找到錯誤檢測需要的特定數據是十分困難的，因為原子性違例錯誤往往就發生在對某一共享變量的訪問過程中，而訪存地址能很好地標記某一共享變量以及對變量的操作，所以本文將蹤跡以變量的地址為標志，將原始蹤跡分成不同的蹤跡集合，每個集合都代表對某一變量的全部操作，這有利于下一步提取線程交互不變量時減小搜索空間，提高提取效率，也能夠避免因蹤跡文件過大導致的內存溢出。

Hash由于其高效性、不可逆性以及唯一性，能夠滿足當前的需求，最重要的是Hash不會隨數據量的增大而降低搜索效率，使其在數據存儲與訪問中占有重要的地位[16]。它將關鍵字直接映射為存儲地址，達到快速尋址的目的，即Addr=Hash(key)，其中Hash為哈希函數[17]。

散列表按照有無排列順序可分為兩類，一種是普通映射（map），另一種是無序映射（unordered map），無序映射已被C++11標準納為新特性。它們的原理不同，適用范圍也不同，普通映射內部由二叉平衡樹（紅黑樹）實現，在其插入時根據Key值進行排序，并對樹進行旋轉操作，使其滿足紅黑樹的特性，其中的處理十分復雜。當對其進行頻繁的插入操作時，需要頻繁地調整紅黑樹的結構，耗費時間。無序映射內部是一個向量，通過Hash函數決定插入位置，當發生沖突時，采用分離鏈接法在相應的向量元素結點下掛接鏈表來解決沖突。無序映射相比于普通的映射方式省去了紅黑樹調整的時間，因此當不需要對數據排序時，對頻繁的插入和查找，使用無序映射效率更高?；跓o序映射實現的散列表的基本結構如圖8所示。

Fig.8 Hash table based on unordered map圖8 基于無序映射的散列表結構

由于對蹤跡的分析需要頻繁地查找和插入結點，且不需要排序，從而使用基于無序映射的散列表能更好地提升性能，同時為了提升錯誤檢測的效率，除了將蹤跡分類，還會生成一個蹤跡集合的檢索，檢索中包含訪存地址和對應的集合元素數量。

具體算法流程如下：

首先，以共享變量的地址為關鍵字，建立散列表，將蹤跡分到不同的集合中，這些集合相互獨立，如下所示，其中I是測試用例中所有指令的集合。

檢測蹤跡是否分類完畢，如果完畢，則生成檢索，算法結束；否則繼續處理下一條蹤跡。

綜上，經過蹤跡分塊后，原始蹤跡被分為大大小小不同的集合，每個集合都是對某個訪存地址的全部操作。

3.4 基于線程交互不變量的原子性違例錯誤并發檢測

在應用程序運行時，最有可能發生原子性違例錯誤的往往是鄰近的一個或幾個操作，因此在錯誤檢測時，不需要過多考慮全文的關系，只要考慮當前指令蹤跡鄰近的上下文即可。故在提取不變量時，棧的優勢便體現出來，而棧的特點是后進先出，適用于提取線程交互不變量。因此本文利用棧解決不變量提取的問題。由于各個蹤跡集合相互獨立，并發處理每個集合中的元素能夠大幅提高檢測速度。

在錯誤檢測階段，根據第2部分提出的兩類原子性違例錯誤，下面給出基于線程交互不變量的原子性違例錯誤并發檢測算法。

對WWR原子性違例錯誤的分析可知：當兩個不變量發生交錯時，可能會發生原子性違例錯誤。但在如圖3所示的反例中，雖然兩個不變量也發生了交錯，但同一個讀操作指令卻發生在不同的時間點上，可根據這點對是否真正發生了WWR原子性違例錯誤加以甄別。

算法描述如下：算法的輸入是當前的線程交互不變量和不變量棧，不變量棧中存放著當前已檢測過的本蹤跡集合內的不變量。首先判斷當前的線程交互不變量的寫操作與讀操作是否處于同一線程，如果處于同一線程，則形成了＜LcWr，LcRd>形式的不變量，該形式的不變量不會單獨引發WWR類型的錯誤，只有后面跟著＜RmWr，LcRd>形式的不變量才有可能引發錯誤。如果當前棧為空，則未發生錯誤。如果當前棧非空，則取棧頂元素，但不出棧。這么做的原因是在每次得到新的不變量時，都是先檢測WWR錯誤，再檢測ReWR錯誤，如果在檢測WWR錯誤時進行了出棧操作，則有可能會造成ReWR錯誤的漏報。如果當前棧頂元素是＜LcWr,LcRd>且當前不變量是＜RmWr，LcRd>，并且這兩個不變量的讀操作是同一個（PC一致且T一致），則說明發生了WWR類型的原子性違例錯誤，這一步也去除了WWR良性原子性違例的情況。

算法的偽代碼表示如下：

對后文的偽代碼進行如下定義：Invariant表示當前的線程交互不變量；stackInvar表示不變量棧，用于存放當前已檢測過的本蹤跡集合內的不變量；Result表示判斷結果。由于不變量是由一條寫操作的蹤跡和一條讀操作的蹤跡組合而成，故包含了寫操作的線程號Wtid、指令計數器Wpc、時間戳Wt、寫操作W，以及讀操作的線程號Rtid、指令計數器Rpc、時間戳Rt、讀操作R，以及共用的共享變量地址ADDR。

通過對ReWR原子性違例錯誤的分析可知：在一定范圍內，如果存在兩個對同一共享變量操作的不變量，它們的讀操作在同一線程，且在不同指令上（PC不同），如果它們的寫操作與讀操作不在同一線程，例如＜RmWr，LcRd>＜RmWr，LcRd>，則有可能發生了原子性違例錯誤。但在圖4提出的反例中，不變量雖然滿足＜RmWr，LcRd>＜RmWr，LcRd>，它們的讀操作卻是同一指令（PC相同且T不同），根據這點能夠判斷出這段程序包含了循環判斷，因此這段程序是正確的。

算法描述如下：算法的輸入是當前的線程交互不變量和不變量棧，不變量棧中存放著當前已檢測過的本蹤跡集合內的不變量。首先判斷當前的線程交互不變量的寫操作與讀操作是否處于同一線程，如果處于同一線程，則形成了＜LcWr，LcRd>形式的不變量，不會引起ReWR類型的錯誤，結束算法。否則判斷不變量棧是否為空，如果為空，未發生ReWR錯誤，算法結束。如果不變量棧不為空，依次從棧中彈出5個元素，分別與當前的線程交互不變量做對比，如果彈出的元素是＜RmWr，LcRd>，并且由于當前的不變量也是＜RmWr，LcRd>，同時它們的讀操作位于相同線程且不是同一條指令（讀操作的TID相同且PC不同），則說明發生了ReWR原子性違例錯誤，同時這一步也去除了ReWR良性原子性違例的情況。

算法的偽代碼表示如下：

本文的不變量提取與錯誤檢測算法采用Python實現，分別實現了多線程和多進程兩個版本。使用線程池時，運行效率反而比不使用線程池的效率低。原因是由C語言編寫而成的Python的某個機制導致其對多線程的支持并不好，不同線程同時訪問資源時，需要使用保護機制，由C語言編寫的Python中使用的是GIL（解釋器全局鎖），這意味著對于任何Python程序，不管有多少處理器，任何時候總是只有一個線程在執行，解釋器工作時反而因為需要頻繁切換線程導致程序運行緩慢[18]。而進程池與線程池類似，進程池通過動態分配多個進程處理任務，但在多進程下沒有GIL的限制。因此本文采用進程池完成對錯誤檢測算法的并發處理。

算法實現時，對檢錯和進程調度進行了優化。一是利用3.3節提到的蹤跡集合檢索，若檢索對應的蹤跡集合中的元素少于3個，無需對其進行錯誤檢測操作。其原因是：如果WWR原子性違例錯誤發生，則至少集合內會存在3條蹤跡，分別是LcWr、RmWr和LcRd；同理，如果ReWR原子性違例錯誤發生，則集合內至少會存在4條蹤跡，分別是RmWr、LcRd、RmWr、LcRd，所以當元素個數少于3個時，不會發生原子性違例錯誤。二是使各個進程負載均衡，系統在創建進程、銷毀進程和調度進程時會消耗大量時間，其中創建進程和銷毀進程的時間是不可避免的，因此為了提升算法的效率，就要減少過于頻繁的進程調度。當一個集合中的元素較少時，進程調度的時間遠比檢測錯誤的時間長，這導致程序的運行效率不升反降。因此給進程分配任務時，以集合為單位，一次分配多個集合，并記錄所有分配進來的集合的元素總數，當總數到達一定值，即完成對該進程的任務分配。優化之后可以使得各個進程負載均衡，減少因進程的頻繁調度導致的速度下降。

原子性違例錯誤并發檢測算法的關鍵在于對棧的操作，由于每個蹤跡集合相互獨立，每個集合都描述了對某一個程序運行變量的全部操作，以單進程單集合為例進行描述。

算法的偽代碼如下：

其中輸入是一個蹤跡集合traceSet即對某一個共享變量的全部操作。輸出是該蹤跡集合中錯誤的個數nWrongNum以及由線程號、指令計數器、變量地址等構成的出錯信息鏈表lstWrong。中間變量szContent存放一條當前讀寫指令的蹤跡信息，字符串#eof代表蹤跡集合的結束，棧stack中元素存放寫指令的蹤跡信息，函數mkInvariant則是將符合條件的讀寫指令的蹤跡信息拼接成一條線程間交互不變量，棧stackInvar用于存放已檢測過的不變量。

算法描述如下：每次讀取集合內的一條蹤跡，如果讀取到了結束字符串，則關閉當前的蹤跡集合，并清空棧stack和棧stackInvar。否則，如圖9（a）所示，當I4是寫指令時，如果棧為空，則入棧。否則，如圖9（b）所示，如果與棧頂元素I3位于同一線程，則舍棄I3，I4入棧，因為記錄相同線程的寫指令信息并不會影響錯誤檢測所檢測出的錯誤個數，即本算法只記錄蹤跡中能夠標識出的最鄰近發生的原子性違例錯誤個數及其影響的變量。如圖9（c）所示，如果I4與棧頂元素I3位于不同線程，I4入棧。

Fig.9 Status what would happen when I4is write instruction圖9 當I4是寫指令時會發生的情況

Fig.10 Status what would happen when I4is read instruction圖10 當I4是讀指令時會發生的情況

相反地，當I4是讀指令，則會導致棧中元素出棧，當?？諘r，顯然沒有必要檢測該條蹤跡，故舍棄。否則，如圖10（a）所示，判斷I4與棧頂元素I3是否位于相同線程，如果處于相同線程，則提取出線程交互不變量＜LcWr(I3)，LcRd(I4)>，這個不變量十分安全，不必擔心會引起原子性違例錯誤。反之，如果位于不同線程，I3出棧，并提取出線程交互不變量＜RmWr(I3)，LcRd(I4)>，這個不變量十分危險，有可能會引起本文提出的兩種原子性違例錯誤，因此暫時將這個不變量與之前記錄的線程交互不變量比較，如果之前記錄的不變量是＜RmWr(x)，LcRd(y)>，并且這兩個不變量的讀指令PC不同，如圖10（b）所示，則ReWR原子性違例錯誤發生。繼續令棧內元素出棧，如果在這個過程中遇到一個不變量＜LcWr(I2)，LcRd(I4)>，I2與I4位于相同線程，如圖10（c）所示，則兩個不變量相互交錯，發生了WWR原子性違例錯誤。之后清空棧，避免棧中剩余元素與新來元素產生新的依賴關系。如果沒有這樣的一條指令，則直到棧空后，繼續下一條指令蹤跡的處理。

4 實驗評估

本文分別對5個測試用例進行原子性違例錯誤檢測，這5個程序分別是測試程序Bank以及Splash2中的FFT、LU、RADIX和CHOLESKY。

測試環境如表1所示。

Table 1 Testing environment表1 測試環境

蹤跡總量與程序的復雜程度呈正比，程序的復雜程度與變量的數量、運用的數據結構、算法都相關。程序越復雜，所得到的蹤跡總量就會越大。使用本文算法對這5個測試用例進行錯誤檢測，所得到的優化前后蹤跡總量的對比如圖11所示。

Fig.11 Comparative analysis of total number of traces before and after optimization圖11 優化前后蹤跡總量對比

優化后程序蹤跡總量比優化前減少了約30%，而實際用于檢測的蹤跡總量平均要比優化后程序運行蹤跡的總量又減少約14%，即實際用于檢測的蹤跡總量比未優化程序蹤跡總量減少了約40%，這既縮小了磁盤和內存的占用量，又大大減少了錯誤檢測時的搜索空間，且隨著被檢測程序復雜度的提高，減少的蹤跡量會更多，能夠大大提升蹤跡檢測的效率。

編程人員在編寫多線程程序時有時會忘記對共享變量加鎖或者忘記線程同步的事情經常遇到，從而導致的問題也多種多樣，因此本文選擇注入這種類型的錯誤，并對比注入錯誤前后對結果的影響，以排除干擾。注入錯誤的方法是在程序的源代碼中，將加鎖部分去除或進行適當修改，如圖12所示，注釋掉的部分就是注入錯誤的部分。在圖12（a）中對源代碼做出了更改，去掉線程間的同步措施，在圖12（b）中去掉了鎖。

Fig.12 Examples of injecting bug圖12 注入錯誤示例

Table 2 Comparison of test results before and after injecting bugs表2 注入錯誤前后錯誤檢測結果對比

注入錯誤前和注入錯誤后的實驗結果對比如表2所示。在對Bank、FFT、LU(non)、CHOLESKY的檢測中未出現異常，所注入的錯誤都能夠有效地檢測出來，但在對RADIX的測試中，發現檢測結果與注入錯誤的數量不相符，經檢查，是由于除去鎖的部分在程序中多次調用所引起的。通過實驗證實算法能夠有效檢測出原子性違例錯誤。

圖13為利用基于無序映射的散列表對蹤跡進行分類后錯誤檢測與不對蹤跡進行分類的錯誤檢測的效率對比。

兩個算法都在單進程模式下運行。從算法的運行時間上看，隨著蹤跡的增加，對蹤跡分類后的錯誤檢測時間遠遠少于不對蹤跡進行分類的錯誤檢測時間。其原因在于，如果不對蹤跡進行分類，在提取不變量時，就會檢測許多與該共享變量不相關的其他變量的蹤跡，極大地降低錯誤檢測的效率。

Fig.13 Efficiency comparison between trace classification and non-classified detection algorithms圖13 蹤跡分類與不分類的檢測算法的效率對比

圖14為多進程錯誤檢測所需時間的對比。這組對比測試程序均已完成優化（O3級別），從中能夠看出：在當前的實驗環境下，當蹤跡總量較小即測試用例較簡單時，進程數量對于錯誤檢測的時間沒有過多影響，但是當蹤跡總量達到一定數量即測試用例較復雜時，多進程的優勢就能體現出來。由于測試環境限制，當其達到8個進程時，運行效率達到最優，相比1個進程的運行效率有了大幅提高。但當進程個數超過CPU所能同時運行的極限時，進程會發生狀態切換，導致其運行效率下降。

Fig.14 Running time comparison of multiprocess bug detection圖14 多進程錯誤檢測運行時間對比

5 總結

本文針對現有原子性違例錯誤檢測中出現的問題，對于兩類特定的原子性違例錯誤提出了一種基于線程交互不變量的原子性違例錯誤并發檢測算法。本文算法采用Pin提取程序的原始蹤跡并去除冗余；利用基于無序映射的散列表對蹤跡分類，大大縮小了錯誤檢測的搜索空間，避免了蹤跡過大導致的內存溢出；利用?？焖倨ヅ浣换ゲ蛔兞縼順擞浘€程交互；利用多進程技術，同時并發處理每類蹤跡，提升了錯誤檢測效率；對檢錯和進程調度進行了優化，進一步減小了由蹤跡過大所帶來的影響，使得各個錯誤檢測進程負載均衡，同時解決了因進程調度頻繁導致的速度下降問題。實驗結果表明，本文算法能夠較好地規避蹤跡較大的問題并能快速有效檢測出原子性違例錯誤。由于算法使用離線的方式檢測錯誤，會記錄程序的運行信息，通過這些信息能夠實現對錯誤的重演，檢錯和重演相結合能夠提高算法的擴展性和實用性。目前實現的算法還存在缺陷，主要針對WWR和ReWR兩類原子性違例錯誤進行檢測，不能夠檢測到所有原子性違例錯誤，同時原子違例并不能夠說明一定出現錯誤，存在誤報的可能。并且本文算法屬于蹤跡敏感的錯誤檢測算法，要全面檢測所有可能出現的并發錯誤，就需要多次重復執行本算法，這會導致程序執行許多重復操作，降低其運行效率，在以后的研究中會進一步完善算法。