增加數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)效率的混合算法

梁帥帥 李蘭英

摘? 要：針對(duì)多線程程序同時(shí)讀寫(xiě)同一塊內(nèi)存產(chǎn)生的數(shù)據(jù)競(jìng)爭(zhēng)，已有的檢測(cè)方法漏檢率和誤檢率較高，文章結(jié)合靜態(tài)RELAY法和動(dòng)態(tài)Eraser鎖集法，利用數(shù)據(jù)流的靜態(tài)法對(duì)共同鎖集的判斷和動(dòng)態(tài)法對(duì)共同鎖集的保護(hù)，有效地降低誤檢率和漏檢率。為減少因重復(fù)交織出現(xiàn)的冗余，提出使用重復(fù)檢測(cè)器減少重復(fù)檢測(cè)的數(shù)據(jù)競(jìng)爭(zhēng)，提升了檢測(cè)性能，降低了檢測(cè)開(kāi)銷(xiāo)。

關(guān)鍵詞：數(shù)據(jù)競(jìng)爭(zhēng);動(dòng)靜態(tài)檢測(cè);重復(fù)檢測(cè)器

中圖分類(lèi)號(hào)：TP311.5? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-4706（2020）17-0069-03

Abstract：In view of the data competition generated by multi-threading programs reading and writing the same memory at the same time，the existing detection methods have high miss detection rate and false detection rate. This paper combines the static RELAY method and dynamic ERASER lock set method，uses the static method of data flow to judge the common lock set and the dynamic method to protect the common lock set，so as to effectively reduce the false detection rate and missed detection rate. In order to reduce the redundancy caused by repeated interleaving，the use of duplicate detector to reduce the data competition of repeated detection is proposed，which improves the detection performance and reduces the detection overhead.

Keywords：data race;dynamic and static detection;repetitive detector

0? 引? 言

程序中并發(fā)性bug越來(lái)越多，常見(jiàn)的bug有四種類(lèi)型：死鎖、數(shù)據(jù)競(jìng)爭(zhēng)、原子性違背和順序違背。數(shù)據(jù)競(jìng)爭(zhēng)指在非線程安全的情況下，多線程對(duì)同一個(gè)地址空間進(jìn)行寫(xiě)操作，需花費(fèi)大量時(shí)間進(jìn)行調(diào)試和修復(fù)，很多學(xué)者提出了很多檢測(cè)方法，靜態(tài)檢測(cè)方法主要使用RELAY[1]、Locksmith、RacerX等;本文所述動(dòng)態(tài)檢測(cè)主要使用鎖級(jí)法、先發(fā)生于算法。

因很難確定程序操作實(shí)際影響到哪些內(nèi)存、被訪問(wèn)的值是局部范圍還是全局范圍、是否通過(guò)參數(shù)傳遞到函數(shù)中，RELAY、Locksmith等方法能調(diào)用上下文敏感分析來(lái)確定訪問(wèn)內(nèi)存的實(shí)際位置，但每個(gè)位置上持有哪些鎖，程序操作獲取和釋放了哪些鎖，這些鎖是否有可能通過(guò)參數(shù)傳入的結(jié)構(gòu)派生而來(lái)的都無(wú)法確定。RELAY、Locksmith等方法在兩個(gè)不同訪問(wèn)處，鎖持有的鎖集的交集進(jìn)行判斷是否為可疑數(shù)據(jù)競(jìng)爭(zhēng)。Flanagan等人的先發(fā)生于算法提出更新時(shí)鐘向量，通過(guò)時(shí)鐘向量狀態(tài)判斷相關(guān)讀寫(xiě)訪問(wèn)信息。

為提升并發(fā)缺陷相關(guān)方向的效率，降低漏檢和誤檢率，加強(qiáng)程序的正確性和可操作性，校內(nèi)相關(guān)國(guó)家自然基金課題也對(duì)并發(fā)缺陷數(shù)據(jù)競(jìng)爭(zhēng)進(jìn)一步研究，根據(jù)學(xué)者提出的算法，本人進(jìn)行復(fù)現(xiàn)、改進(jìn)。研究時(shí)基于數(shù)據(jù)流分析和鎖集REALY方法，先進(jìn)行上下文敏感分析，計(jì)算函數(shù)相對(duì)鎖集和保護(hù)訪問(wèn)集，然后判斷相關(guān)鎖集是否有交集，再使用Eraser[2]方法對(duì)相關(guān)鎖集進(jìn)行保護(hù)，如果有可疑的數(shù)據(jù)競(jìng)爭(zhēng)將被進(jìn)行刪除，隨后再根據(jù)檢測(cè)過(guò)程中檢測(cè)出的可疑競(jìng)爭(zhēng)所在位置的程序段進(jìn)行分步驟重復(fù)檢測(cè)，本文動(dòng)靜結(jié)合檢測(cè)方法減少了動(dòng)態(tài)檢測(cè)的漏檢率和靜態(tài)檢測(cè)的誤檢率，并解決了一些數(shù)據(jù)競(jìng)爭(zhēng)重復(fù)檢測(cè)的問(wèn)題。在檢測(cè)并發(fā)缺陷后，使用重復(fù)檢測(cè)器再一次進(jìn)行篩選，時(shí)間、空間開(kāi)銷(xiāo)會(huì)有所減少。

1? FPX的算法描述

首先靜態(tài)RELAY法對(duì)符號(hào)執(zhí)行的局部和全局傳入值跟蹤內(nèi)存位置中包含的值，使用元變量x∈X表示局部和全局，符號(hào)值的集合V表示符號(hào)分析計(jì)算的值，整數(shù)init（x）是x的局部值;must（x）表示一個(gè)必須指向x的值;may（x）表示一個(gè)可能指向x中的任何左值。符號(hào)執(zhí)行跟蹤每個(gè)程序點(diǎn)上的符號(hào)映射，并使用函數(shù)更新這個(gè)符號(hào)映射。簡(jiǎn)單賦值x：= e的函數(shù)，將當(dāng)前映射中的e計(jì)算為一個(gè)符號(hào)值，然后更新映射中的x。對(duì)于通過(guò)指針進(jìn)行的賦值，也就是?x：=e，函數(shù)將x計(jì)算為一個(gè)符號(hào)值v1，將e計(jì)算為一個(gè)符號(hào)值v2，存儲(chǔ)中更新哪些x取決于值v1。

鎖集的結(jié)果存儲(chǔ)為XLock（f）∈L，表示函數(shù)末尾的相對(duì)鎖集。將鎖和解鎖操作為鎖集函數(shù)調(diào)用，修改鎖集函數(shù)調(diào)用e（a）。lock（l）函數(shù)為（{l}，{ }）的相對(duì)鎖集摘要，unlock（l）函數(shù)為（{ }，{l}）的相對(duì)鎖集摘要，相對(duì)鎖集產(chǎn)生的摘要表從開(kāi)始執(zhí)行到返回的鎖集中的變化。查找調(diào)用f后的相對(duì)鎖集，將更新后的鎖集信息傳入的相對(duì)鎖集[3]。鎖集分析完成對(duì)給定函數(shù)的所有程序點(diǎn)的相對(duì)鎖集的計(jì)算，保護(hù)訪問(wèn)使用這些信息來(lái)計(jì)算函數(shù)執(zhí)行的保護(hù)訪問(wèn)集合。保護(hù)訪問(wèn)集合是一個(gè)triple a=（x，L，k），x值被訪問(wèn)，l∈L是當(dāng)前鎖的訪問(wèn)，k代表鎖的類(lèi)型即讀鎖或?qū)戞i;訪問(wèn)設(shè)置更新（s，L）。

當(dāng)處理完函數(shù)中的所有語(yǔ)句后，最后的保護(hù)訪問(wèn)集將成為函數(shù)的訪問(wèn)摘要。最終能計(jì)算出該線程的入口函數(shù)的保護(hù)訪問(wèn)集，對(duì)于共享變量v的來(lái)自不同線程T1和T2的2個(gè)保護(hù)訪問(wèn)（o，，k）和（o′，，k′），其中，o是左值被訪問(wèn)，L+是進(jìn)程所獲取的鎖的集合，L-是進(jìn)程所釋放的鎖的集合。獲取保護(hù)它們的鎖集的交集，如果交集為空，則這2個(gè)訪問(wèn)就構(gòu)成一個(gè)可疑的數(shù)據(jù)競(jìng)爭(zhēng)。使用靜態(tài)檢測(cè)的數(shù)據(jù)競(jìng)爭(zhēng)誤檢率高，所以使用動(dòng)態(tài)檢測(cè)降低誤檢率，如下述使用Eraser鎖集算法動(dòng)態(tài)檢測(cè)在靜態(tài)檢測(cè)鎖集和保護(hù)訪問(wèn)集結(jié)果的基礎(chǔ)上對(duì)共享變量的保護(hù)訪問(wèn)應(yīng)受到共同鎖集的保護(hù)，并不斷更新鎖集向量時(shí)鐘[4]的信息，通過(guò)線程調(diào)度發(fā)現(xiàn)真實(shí)數(shù)據(jù)競(jìng)爭(zhēng)，然后剔除數(shù)據(jù)競(jìng)爭(zhēng)，從而降低誤檢率。

Eraser lockset algorithm

Input：thread t's lock set and sharevarable v's candidate lock set

Output：null or a race warning

Let Lt be the set of locks held by thread t;

For each shared variable v，CL（v） stands v's candidate locks

namely the set of locks consistently protecting v.Initially， CL（v） is set to be all locks;

Let prev be the previous access to v before the current access to v.Initially，prev is nil;

Let mode（x）be a map from access x to its type，namely READ or WRITE;

foreach access a to v by thread t do

CL（v）←CL（v）∩Lt;

if CL（v）=0&&?。╩ode（a）=READ&&mode

（prev）=READ） then

return a race warning（v，prev，a）;

return;

算法檢測(cè)后有大量的數(shù)據(jù)競(jìng)爭(zhēng)重復(fù)檢測(cè)，在上述動(dòng)靜態(tài)檢測(cè)后加一個(gè)檢測(cè)器，來(lái)過(guò)濾重復(fù)檢測(cè)，描述如下：檢測(cè)器由多個(gè)步驟組成，最重要的步驟是預(yù)測(cè)步驟和驗(yàn)證步驟。預(yù)測(cè)步驟檢查動(dòng)態(tài)的執(zhí)行，基于動(dòng)態(tài)檢測(cè)模式預(yù)測(cè)潛在的重復(fù)數(shù)據(jù)競(jìng)爭(zhēng);驗(yàn)證步驟主動(dòng)控制線程調(diào)度[5]，驗(yàn)證許多重新執(zhí)行中的數(shù)據(jù)競(jìng)爭(zhēng)。第一步可能會(huì)產(chǎn)生許多重復(fù)的數(shù)據(jù)競(jìng)爭(zhēng)，給第二步帶來(lái)許多重復(fù)的新執(zhí)行，這將影響并發(fā)性數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)的效率。在第一步中預(yù)測(cè)潛在的競(jìng)爭(zhēng)（兩個(gè)數(shù)據(jù)競(jìng)爭(zhēng)），如果S1->S3->S2之間的潛在競(jìng)爭(zhēng)已經(jīng)被檢測(cè)，則無(wú)需再次檢測(cè)S1->S3和S3->S2之間的其他兩個(gè)潛在競(jìng)爭(zhēng)。比如S1-> S3->S2的實(shí)例iS1->iS3->iS2表示兩個(gè)線程之間的三個(gè)內(nèi)存訪問(wèn)事件，S1->S3的實(shí)例iS1->iS3表示兩個(gè)線程之間的兩個(gè)內(nèi)存訪問(wèn)事件，而實(shí)例iS1->iS3無(wú)需檢測(cè)，因?yàn)榱硪籭S1->iS3->iS2已經(jīng)包含了這個(gè)實(shí)例。如果S1->S3和S3-> S2在檢測(cè)時(shí)沒(méi)有進(jìn)行重復(fù)檢測(cè)，那么效率會(huì)得到明顯提高。檢測(cè)器算法描述如下：

Dynamic detector after Eraser detect Event 1、Event 2、Event 3.

Let detect the set of lock by FPX

For search Datarace in the set lock and detect repeat

If search （Event 1—>Event 3）∩（Event 1—>Event 2—> Event 3） = Event 1—> Event 3

Return Event 1—>Event 2—>Event 3

Break repeat lock

Elseif Event 2—>Event 3∩（Event 1—> Event 2—>Event 3） = Event 2—> Event 3

Return Event 1—>Event 2—>Event 3

Break repeat lock

Return Event 1—>Event 2—>Event 3

2? 實(shí)驗(yàn)結(jié)果分析

RELAY算法能檢測(cè)數(shù)據(jù)競(jìng)爭(zhēng)，誤檢率高，但相對(duì)于一般檢測(cè)方法漏檢率低，檢測(cè)出程序中的數(shù)據(jù)競(jìng)爭(zhēng)即報(bào)錯(cuò)。針對(duì)誤檢問(wèn)題動(dòng)態(tài)使用Eraser鎖集算法，因?qū)︽i集的時(shí)鐘向量信息不斷更新，最終獲取時(shí)鐘信息判斷數(shù)據(jù)競(jìng)爭(zhēng)，因此誤檢率較低。

對(duì)相關(guān)論文重新實(shí)現(xiàn)了這些檢測(cè)工具和算法。對(duì)比實(shí)驗(yàn)在同一環(huán)境下進(jìn)行，保證了實(shí)驗(yàn)結(jié)果具有可比性。對(duì)FPX、RaceChecker和RaceFuzzer進(jìn)行驗(yàn)證，結(jié)果如表1所示，其中前三列表示檢測(cè)工具RaceChecker、FPX、RaceFuzzer檢測(cè)出的數(shù)據(jù)競(jìng)爭(zhēng)對(duì)數(shù)目，RC、FPX、RF表示RC和FPX、RaceFuzzer檢測(cè)過(guò)程中的潛在可疑的數(shù)據(jù)競(jìng)爭(zhēng)對(duì)數(shù)。為評(píng)測(cè)和對(duì)比分析FPX對(duì)目標(biāo)程序的性能影響，在fft、lu、radix等程序上分別運(yùn)行來(lái)檢測(cè)驗(yàn)證RaceFuzzer[6]、RaceChecker和FPX。

表2是在動(dòng)靜態(tài)檢測(cè)方法檢測(cè)前的重復(fù)數(shù)據(jù)競(jìng)爭(zhēng)數(shù)量和使用重復(fù)數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)器檢測(cè)后的數(shù)據(jù)競(jìng)爭(zhēng)數(shù)量對(duì)比表，其中檢測(cè)工具檢測(cè)程序5 000行左右，在檢測(cè)器下，檢測(cè)重復(fù)數(shù)據(jù)競(jìng)爭(zhēng)前和檢測(cè)重復(fù)數(shù)據(jù)競(jìng)爭(zhēng)后的數(shù)據(jù)對(duì)比。

為了更能清晰地看出重復(fù)檢測(cè)器檢測(cè)效率的提升，如圖1所示，沒(méi)有檢測(cè)前的數(shù)據(jù)競(jìng)爭(zhēng)數(shù)量和使用重復(fù)檢測(cè)器后的數(shù)據(jù)競(jìng)爭(zhēng)的數(shù)量效率對(duì)比，在多種檢測(cè)方法下，針對(duì)三種不同的檢測(cè)器重復(fù)檢測(cè)出的數(shù)據(jù)競(jìng)爭(zhēng)數(shù)目有所減少，開(kāi)銷(xiāo)效率提升4%，但還存在一些問(wèn)題有待繼續(xù)研究，例如檢測(cè)器檢測(cè)的數(shù)據(jù)競(jìng)爭(zhēng)，在必要條件非常高的時(shí)候，有檢測(cè)器的開(kāi)銷(xiāo)是否比沒(méi)有檢測(cè)器的開(kāi)銷(xiāo)還要大。