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

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

1 引言

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

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

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

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

（3）并發(fā)錯(cuò)誤的出現(xiàn)是因?yàn)閮蓚€(gè)線程的交互而引起的。

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

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

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

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

2 線程交互不變量

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

本文基于線程交互不變量對(duì)并發(fā)程序原子性違例錯(cuò)誤進(jìn)行檢測(cè)，采用＜W，R>有序?qū)Φ姆绞接涗浽摬蛔兞浚琖代表寫操作，R代表讀操作。R只有一種情況，LcRd，代表本地讀操作。所有寫操作的類型都是相對(duì)于讀操作的，因此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中，實(shí)線表示的是＜LcWr(10)，LcRd(14)>，虛線表示的是＜RmWr(4)，LcRd(14)>。

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

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

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

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

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

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

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

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

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

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

3 算法設(shè)計(jì)

3.1 總體架構(gòu)

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

3.2 蹤跡提取

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

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

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

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

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

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

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

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

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

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

3.3 蹤跡分析

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

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

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

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

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

具體算法流程如下：

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

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

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

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

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

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

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

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

算法的偽代碼表示如下：

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

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

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

算法的偽代碼表示如下：

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

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

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

算法的偽代碼如下：

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

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

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

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

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

4 實(shí)驗(yàn)評(píng)估

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

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

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

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

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

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

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

Fig.12 Examples of injecting bug圖12 注入錯(cuò)誤示例

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

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

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

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

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

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

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

5 總結(jié)

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