李蘭英，孫建達(dá)，朱素霞

哈爾濱理工大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150080

1 引言

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

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

（1）在所有與數(shù)據(jù)相關(guān)的并發(fā)錯誤中，有大約65%的并發(fā)錯誤是原子性違例錯誤。

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

（3）并發(fā)錯誤的出現(xiàn)是因為兩個線程的交互而引起的。

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

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

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

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

2 線程交互不變量

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

本文基于線程交互不變量對并發(fā)程序原子性違例錯誤進(jìn)行檢測，采用＜W，R>有序?qū)Φ姆绞接涗浽摬蛔兞浚琖代表寫操作，R代表讀操作。R只有一種情況，LcRd，代表本地讀操作。所有寫操作的類型都是相對于讀操作的，因此W分為兩類，LcWr和RmWr。LcWr代表和讀操作處于相同線程（本地寫操作），而RmWr代表和讀操作處于不同線程（遠(yuǎn)程寫操作）。

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

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

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

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

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

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

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

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

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

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

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

3 算法設(shè)計

3.1 總體架構(gòu)

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

3.2 蹤跡提取

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

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

Fig.5 System architecture of atomicity violation detection圖5 原子性違例錯誤檢測系統(tǒng)架構(gòu)

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

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

Fig.6 Program with repeated read圖6 重復(fù)讀

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

Fig.7 Program with repeated write圖7 重復(fù)寫

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

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

3.3 蹤跡分析

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

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

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

Fig.8 Hash table based on unordered map圖8 基于無序映射的散列表結(jié)構(gòu)

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

具體算法流程如下：

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

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

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

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

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

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

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

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

算法的偽代碼表示如下：

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

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

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

算法的偽代碼表示如下：

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

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

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

算法的偽代碼如下：

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

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

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

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

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

4 實驗評估

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

測試環(huán)境如表1所示。

Table 1 Testing environment表1 測試環(huán)境

蹤跡總量與程序的復(fù)雜程度呈正比，程序的復(fù)雜程度與變量的數(shù)量、運(yùn)用的數(shù)據(jù)結(jié)構(gòu)、算法都相關(guān)。程序越復(fù)雜，所得到的蹤跡總量就會越大。使用本文算法對這5個測試用例進(jìn)行錯誤檢測，所得到的優(yōu)化前后蹤跡總量的對比如圖11所示。

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

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

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

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

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

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

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

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

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

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

Fig.14 Running time comparison of multiprocess bug detection圖14 多進(jìn)程錯誤檢測運(yùn)行時間對比

5 總結(jié)

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