数据竞争^[1]是常见的多线程程序安全性缺陷^[2-4]之一，同时也是导致其他多线程程序安全性缺陷的主要根源。数据竞争检测方法目前主要分为4类：静态数据竞争检测方法、动态数据竞争检测方法、动静结合的数据竞争检测方法以及基于采样策略的检测方法。静态数据竞争检测方法通过程序源代码的锁集分析来检测数据竞争；动态数据竞争检测方法目前主要利用happens-before关系、lockset算法来检测数据竞争；动静结合的检测方法采用先静态分析和后动态验证的方式来检测数据竞争；基于采样策略的检测方法则是采用开销较小的基于采样策略的方法来高效检测大规模并发程序中的数据竞争。

Dinning等^[5]和Perkovic等^[6]基于Lamport的happens-before关系^[7]提出了使用向量时钟来动态检测数据竞争。Savage等^[8]提出了基于lockset算法的动态数据竞争检测工具Eraser，该方法在程序执行过程中维护每个线程当前的锁集信息，同时更新共享变量持有的锁集信息，当共享变量不再受到锁保护时，报告出现数据竞争。Pozniansky等^[9]提出了改进的基于happens-before关系的动态数据竞争检测方法Djit+，该方法只记录线程和共享内存空间访问的向量时钟中第1次对共享内存空间的读/写访问。Pratikakis等^[10]开发了数据竞争静态检测工具LOCKSMITH，LOCKSMITH首先使用标签流约束和抽象控制流图约束信息来进行锁集分析，然后使用标签流约束、抽象控制流图约束和上下文敏感约束进行共享变量的分析，最后结合线性分析，检测出数据竞争。Voung等^[11]发布了一种静态数据竞争检测工具RELAY，该工具利用流敏感和过程间分析检测数据竞争和死锁。Serebryany等^[12]提出了基于happens-before关系与lockset算法两者结合的动态数据竞争检测方法，该方法首先找出所有不具备happens-before关系的同步对，然后判断这些同步对是否受到同一锁保护。Yang等^[13]提出了一种动静结合的数据竞争检测方法，首先利用静态检测工具分析所有可能存在的数据竞争，然后对那些可能存在的数据竞争进行动态验证。Guo等^[14]为降低检测开销，针对大规模程序提出了一种基于对共享内存进行采样的策略检测数据竞争，开发了工具AtexRace。

上述方法都是在函数或语句层面进行数据竞争检测，在一定程度上降低了开销，但同时造成了大量的误报和漏报，并且其中大多数方法需要确定的线程调度。针对上述方法的问题，本文提出了一种数据竞争随机森林(random forest for data race, RFDR)^[15]指令级检测模型。指令级检测能消除大量的漏报及误报，并不需要确定的线程调度，但指令级检测由于数据量过大会造成大量的开销，因此本文引入随机森林模型来降低检测开销，在提高检测精度的同时提升检测效率。

本文首先对被测程序进行动态二进制插桩，利用lockset算法和happens-before关系检测数据竞争。然后，将检测结果作为训练样本集，以多线程数据竞争的5个相关属性作为特征来训练随机森林指令级检测模型。为了方便描述，本文将happens-before关系和lockset算法相结合的算法称为hybrid算法。传统的基于hybrid算法的数据竞争检测方法存在一些缺陷，由于无法识别一些常见的隐形同步对^[16-17]，导致产生一系列的误报，因此本文提出了一种改进的基于hybrid算法的数据竞争指令级检测方法来针对性地剔除一些常见的隐形同步对。由于数据竞争最终都可以归结到两条线程交织，因此本文只分析来自两条不同线程的指令形成的指令对，以简化检测工作。

1 数据竞争指令级检测算法 1.1 数据竞争检测

根据数据竞争的定义，动态数据竞争检测方法需要用到动态插桩的方式，需要在动态插桩过程中得到指令所在线程ID、指令所访问的内存地址、指令的读写操作这3项属性特征。当两条指令的线程ID不同却访问相同内存地址时会发生数据竞争。这种根据两条指令的线程ID和访问内存地址来报告数据竞争的方法在剔除漏报的同时也带来了大量的误报，因为在复杂的实际情况当中，有些线程间存在着确定性的先后关系或受到同一锁保护等情况，并不存在数据竞争。图 1中线程T1对共享变量global的访问发生在线程T2之前，并且global在两个线程的访问当中受到了同一个锁的保护，因而不会造成数据竞争，若仅根据上述3种特征进行判断，这一对访问将被误报为数据竞争。

1.2 基于hybrid算法的数据竞争指令级检测

为了避免根据定义检测的误报出现，本文引入hybrid算法来对数据竞争进行指令级检测。首先，对多线程程序进行动态二进制插桩，并剔除所有没有访问内存的指令，在插桩过程中遍历当前指令与之前运行过的指令两两之间形成的指令对。然后，利用happens-before关系找出所有非同步指令对，再利用lockset算法来判断非同步指令对的锁保护状态，若非同步指令对不受同一锁保护，则为数据竞争。

当程序中某条线程对共享变量进行访问时，还需对共享变量此时锁保护状态进行检测。在多线程程序当中经常会用到互斥锁mutex_lock和读写锁rwlock^[18]。当共享变量获得互斥锁时，只允许当前线程对其进行访问，其他线程等待；当共享变量获得读写锁时，若读写锁为读模式，则允许其他线程对共享变量进行读访问，但无法进行写访问，若读写锁为写模式，则不允许其他线程对共享变量进行任何访问。因为读写锁处于读模式时，其他线程是可以进行读访问的，不构成线程间的同步关系，所以本文忽略对读写锁处于读模式时的监测，只对当前指令是否获得互斥锁或读写锁为写模式的情况进行监测和记录。当利用happens-before关系检测到的非同步指令对没有受到同一互斥锁或读写锁保护时，报告数据竞争。

1.3 剔除隐形同步对

隐形同步对是指由if等约束条件造成的不容易被发现的同步对。图 2中显示了基于hybrid算法的数据竞争指令级检测算法会将隐形同步对误报为数据竞争的一种情况。若仅基于hybrid算法，则会报告数据竞争指令对INS〈S2, S1〉和INS〈S3, S1〉，但实际上S3不可能发生在S1之前，因此S3与S1不是真实的数据竞争，INS〈S3, S1〉是误报。

为了避免这种误报，需要进一步剔除指令中的隐形同步对。本文分析了被测程序的汇编源码，在大量实验中发现，共享变量的汇编源码一般为“eax”，这可能是由于在整个程序中共享变量为第1个划分的内存空间所导致的。由于if语句的汇编源码为“cmp”，因此只需分析汇编源码中是否存在“cmp eax”字样来检测隐形同步对。由于并不是if语句与其他线程对共享变量的访问会导致误报，而是if语句所包含的语句体会导致误报，因此本文取前10条指令所对应的汇编源码进行遍历。如果前10条指令的汇编源码中存在字符串“cmp eax”并且该指令被报告为数据竞争，则本文将与其构成数据竞争的指令对视为隐形同步对，而非真实的数据竞争。

1.4 改进的hybrid数据竞争指令级检测算法

基于数据竞争的定义，利用happens-before关系和lockset算法，采用汇编源码隐形同步对的剔除方式，本文提出了一种改进的hybrid算法来指令级检测数据竞争，算法流程如下：

步骤1  设被测并发程序的指令数为inscount，线程数为n。利用二进制插桩工具Pin对被测并发程序P中每条访问内存地址的指令进行动态插桩。指令编号为num，第1条访问内存地址指令的num为1，后续指令以此类推。记录每条指令的指令地址ip、访问内存地址addr、读写操作op、所在线程编号tid、锁保护状态lockset、前10条指令的汇编源码以及对应的源码assembly行号line。

步骤2  针对被测并发程序中某个被访问的共享内存S，创建向量时钟矩阵VS_n×n=[t₁ t₂ …t_i … t_n]^Τ。其中：t₁=[t₁₁ t₁₂ … t_1n]，表示线程1的向量时钟；以此类推，t_n=[t_n1 t_n2 …t_nn]表示线程n的向量时钟，第i个线程的向量时钟t_i=[t_i1 t_i2 … t_in]。t_ij(j=1, 2, …, n)表示线程i所记录的线程访问共享内存S的时间戳，初始值设为0。

步骤3  判断条件num=inscount，若该条件成立，进入步骤11，否则每执行一条指令，其指令编号num=num+1，遍历当前指令INS与之前的所有指令。设置k初始值为1，若线程i中的指令访问共享内存S，则增加自己的时间戳t_ii=t_ii+1。当线程i与线程j同步执行时，线程i释放共享内存S后, 线程j开始访问共享内存S，线程j更新自己的向量时钟t_jj=t_jj+1，并且同时将两个线程向量时钟的值更新为

$ \left\{ {\begin{array}{*{20}{l}} {{\mathit{\boldsymbol{t}}_i} = \left[ {\max \left( {{t_{i1}}, \;{t_{j1}}} \right)} \right.}&{\left. {\max \left( {{t_{i2}}, {t_{j2}}} \right) \cdots \max \left( {{t_{in}}, {t_{jn}}} \right)} \right]}\\ {{\mathit{\boldsymbol{t}}_j} = \left[ {\max \left( {{t_{i1}}, \;{t_{j1}}} \right)} \right.}&{\left. {\max \left( {{t_{i2}}, {t_{j2}}} \right) \cdots \max \left( {{t_{in}}, {t_{jn}}} \right)} \right]} \end{array}} \right., $

即此时两个向量时钟中每个维度的较大值。当线程i与线程j不同步执行，线程j更新自己的向量时钟t_jj=t_jj+1，其他值不变。若被测程序运行过程中出现新的共享内存G，则创建新的向量时钟矩阵VG_n×n，并设置初始值为0。

步骤4  判断k是否等于当前指令的编号num，如果等于，则跳回步骤3，如果不等于，则进入步骤5。

步骤5  若当前指令INS的读写操作op为读操作，则进入步骤6；若为写操作，则进入步骤7。

步骤6  如果第k条指令INS的读写操作op为读操作，则k=k+1，跳回步骤4；若第k条指令的读写操作为写操作，则进入步骤7。

步骤7  若当前指令与第k条指令的访问内存地址addr一致并且两者所在线程tid不同，则进入步骤8;否则k=k+1，跳回步骤4。

步骤8  设当前指令所在线程为e(e=1, 2, …, n)，第k条指令所在线程为q(q=1, 2, …, n)，判断线程e的向量时钟t_e与线程q的向量时钟t_q是否存在偏序，若存在，则k=k+1并跳回步骤4，否则进入步骤9。

步骤9  判断当前指令与第k条指令的lockset是否相同，是则k=k+1并跳回步骤4，否则进入步骤10。

步骤10  判断当前指令与第k条指令的汇编源码中是否存在字符串“cmp eax”，若存在则k=k+1并跳回步骤4；否则报告当前指令与第k条指令造成数据竞争，输出两条指令的ip、addr、tid以及line，然后k=k+1并跳回步骤4。

步骤11  结束。

2 RFDR模型 2.1 数据采集

图 3描述了两条指令发生数据竞争的过程，即当两条指令满足数据竞争定义及hybrid算法产生数据竞争的条件并且为非隐形同步对时, 报告数据竞争。

根据基于指令级数据竞争产生过程，需要根据指令所在的线程ID、指令访问的内存地址和指令的读写操作来判断两条指令是否满足数据竞争定义，再根据指令的向量时钟以及其此时的锁保护状态来判断是否满足偏序关系以及是否受到同一锁保护，进而利用前10条指令的汇编源码来判断是否为非隐形同步对。本文在动态二进制插桩的过程中，需要收集的指令数据有：指令所在线程ID、指令所访问的内存地址、指令访问内存的读写操作、指令的向量时钟、指令的锁集合、前10条指令所对应的汇编源码。本文将利用这6项指令数据来构建指令对的各项特征。

2.2 指令对数据构建及数值化

由于数据竞争来自不同线程的不同指令，因此需要分析来自不同线程的指令形成的指令对。表 1为对多线程程序进行动态插桩时随机抽取的9条指令。其中：隐形同步对一项表示程序中前10条指令是否存在字符串“cmp eax”，存在为0，不存在为1；“W”和“R”分别表示写操作和读操作。在来自两条不同线程的指令中，第3条与第6条、第3条与第7条、第3条与第9条指令对满足数根据竞争条件，但这些指令对之间可能存在某种确定的先后关系或受到同一个锁保护，并且可能为隐形同步对，因此它们不一定是真实的数据竞争，需要进一步分析它们的向量时钟与锁保护状况以及汇编源码来确定。

表 1中第3条指令与第6条指令的向量时钟分别为(0, 1, 0, 0)和(0, 0, 1, 0)，由于它们既不大于也不小于对方，不存在偏序关系且没有受到同一个锁保护，以及两者在程序中的前10条指令所对应的汇编源码不包含字符串“cmp eax”，因此这一对指令为数据竞争。第3条指令与第7条指令不存在明确的先后关系并且没有受到同一个锁保护，但第7条指令所在程序中的前10条指令所对应的汇编源码包含字符串“cmp eax”，因此视为隐形同步对，这一对指令不是真实的数据竞争。第3条指令与第9条指令的向量时钟因为存在着偏序关系并且受到同一个锁保护，因此它们也不是真实的数据竞争。

表 1中线程ID为1的5条指令与线程ID为2的4条指令可形成20对指令对。为了便于下一步建模操作，本文将指令对数据进行数值化，建立数据竞争检测的特征属性。

●   P:指令对，7-1表示表 1中第7条指令与第1条指令所形成的指令对，第7条指令为当前指令，第1条指令发生在第7条指令之前。

●  P_m:指令对中两条指令访问的内存地址是否一致，不一致为0，一致为1。

●  P_o:若两条指令中至少有一条为写操作则为1，否则为0。

●  P_v:两条指令的向量时钟是否满足偏序关系，不满足为1，满足为0。

●  P_l:如果两条指令没有受到同一个锁保护则为1，否则为0。

●  P_a:若指令对中当前指令在程序中的前10条指令所对应的汇编源码不包含字符串“cmp eax”则为1，否则为0。

●  P_r:为类标号属性，若该指令对会发生数据竞争则为1，否则为0。

本文将表 1中的初始数据进行预处理，转换成表 2，并利用指令对P的P_m、P_o、P_v、P_l与P_a这5项特征来训练模型。

2.3 训练RFDR模型

随机森林是集成学习方法模型，通过将多棵决策树整合成森林，合并起来进行分类预测以解决决策树算法样本改动易造成树结构的剧烈改变的缺陷。常用的决策树算法有ID3、C4.5和CART。ID3算法以信息增益来度量属性的选择；C4.5算法对ID3进行了优化，采用信息增益比作为划分属性的标准，在一定程度上对取值比较多的特征进行惩罚，避免了ID3出现过拟合的情况，提升了决策树的泛化能力；CART在每一次迭代中选择Gini指数最小的特征及其对应的切分点进行分类，Gini指数描述的是数据的纯度，与ID3和C4.5不同的是，CART每个节点只会产生2条分支，最后形成一棵二叉树。ID3与C4.5通过剪枝策略来权衡树的分类精度与泛化能力，而CART直接利用全部数据发现所有可能的树结构，降低了系统开销。本文选择采用CART算法来构造决策树。

图 4为根据表 2所示的某被测程序的样本集各项特征的Gini指数绘制出的决策树。由于在P_m、P_o、P_v、P_l与P_a 5项特征中，P_m的Gini指数最小，因此选择特征P_m作为最优特征，P_m=0为最优切分点，然后继续选取除P_m外Gini指数最小的特征继续进行切分。按照这种切分方式将所有特征切分后，完成决策树的构造。

本文根据集成学习的思想基于随机森林建立多棵决策树，构造RFDR模型，如图 5所示。RFDR包含多个由Bagging(并行)集成学习技术训练得到的决策树，这些树由所有样本集和特征中随机采样的子集构成。当输入待分类的样本时，由于之前已经将数据数值化，因此可将最终输出的分类结果取各个决策树输出的平均值。考虑到平均值很可能介于0到1之间，因此设定一个阈值0.5，平均值大于等于0.5视为1，小于0.5视为0。

RFDR解决了决策树性能瓶颈问题，对噪声和异常值有较好的容忍性，对高维数据分类问题具有良好的可扩展性和并行性。此外，RFDR是由数据驱动的一种非参数分类方法，只需通过对给定样本的学习训练分类规则，并不需要先验知识。由于样本和特征随机采样的过程保证了随机性，因此不会出现过拟合。

3 实验分析

在Intel公司发布的动态二进制插桩工具Pin的基础上，本文利用其应用程序接口(application programming interface, API)开发出基于RFDR模型的检测工具AIRaceTest。Pin工具具有功能强大、易用、可移植性好等特点，同时提供了简单易用的接口函数，利用Pin工具的指令级插桩能够精准获得程序执行过程的动态数据。

由于目前还没有较为完善的用于训练数据竞争检测模型的样本集，因此本文从GitHub[https://github.com/arnabd88]选取了一些经典多线程程序的动态二进制插桩结果作为训练样本集。这些多线程程序中含有复杂多样的数据竞争及隐形同步对，通过插桩采集数据来训练模型较为合适。模型训练完成后，本文选择Parsec基准程序3.1^[19]和Google data-race-test [https://code.google.com/p/data-race-test/]中的一组多线程程序Unittest对AIRaceTest进行检测精度和开销两方面评估。Parsec基准程序3.1和Unittest分别由13个和5个多线程程序组成，这些程序包含一些隐形同步对，并且存在大量难以检测的数据竞争。本文所有的实验都是在Ubuntu16.04上采用4核中央处理器和2 GB内存进行的。

3.1 实施过程

图 6描述了AIRaceTest的体系结构。AIRace- Test由一个Pin二进制插桩工具和一个随机森林模型组成，Pin工具对多线程程序进行动态插桩来检测数据竞争，再根据数据竞争检测结果及检测过程中提取的数据来建立随机森林模型，最后用建立好的模型对多线程程序的动态二进制插桩数据进行分类预测，报告数据竞争。

本文还在Pin工具上实现了Eraser^[8]、Djit+^[9]以及Thread Sanitizer^[12]3种动态数据竞争检测工具。其中，Eraser主要在动态执行过程中使用lockset算法进行数据竞争检测，Djit+在动态执行过程中使用happens-before关系进行数据竞争检测，Thread Sanitizer则在动态执行过程中结合lockset算法和happens-before关系进行数据竞争检测。本文采用AIRaceTest、Eraser、Djit+以及Thread Sanitizer 4种检测工具对Parsec基准程序3.1和Unittest进行数据竞争检测，并将实验结果进行对比和分析。

3.2 模型参数选择

本文从GitHub上选取了CIVL-CS6110、Pro & Con、OpenMP、DRS-3以及TCL_P600这5个多线程程序的指令级检测结果合并作为样本集来训练RFDR模型。这些程序中都包含了隐形同步对，总代码行数为3 589，有对应源码的总指令数为9 051，来自两条线程的指令所形成的指令对数为6 650 361。

在训练RFDR模型的过程中，交叉验证折数以及决策树数量对模型分类精度和开销有一定的影响，交叉验证折数过小或决策树数量过少会造成模型分类精度较低，交叉验证折数过大或决策树数量过多会造成模型计算开销较大。随着交叉验证折数或决策树数量的增长，模型分类精度会逐渐增高然后达到一个平衡值，因此首先寻找理想的交叉验证折数以及构建随机森林的决策树数量。

图 7为将决策树数量固定为10、交叉验证折数从2到20逐渐递增时模型精度的变化情况。当交叉验证折数值较小时，模型精度随着交叉验证折数的增长出现了上下波动，这是由于数据分布不均匀造成，当交叉验证折数达到10时，模型精度达到最高值0.876并处于稳定状态，不再随交叉验证折数的增加而继续上升，因此该样本集训练RFDR模型的交叉验证折数最佳取值为10。图 8为交叉验证折数取值为10时，模型精度随着决策树数量递增的变化情况。当决策树数量达到80时，模型精度达到最优值0.921并处于稳定状态，因此该样本集训练RFDR模型的决策树数量最佳取值为80。

利用上述5个GitHub中的多线程程序的动态二进制插桩结果作为样本集训练RFDR模型，选择交叉验证折数与决策树数量分别为10和80时，模型精度达到最高值0.921并且不会造成多余的开销。下面分析模型检测精度和开销的实验中，交叉验证折数与决策树数量分别设置为10和80。

3.3 检测精度分析

为了描述各种方法的检测精度，定义TP为检测工具报告出真实数据竞争数量，FP为误报数量，FN为漏报数量。图 9显示了AIRaceTest、Eraser、Djit+以及Thread Sanitizer 4种检测工具对多线程程序Unittest的数据竞争检测结果，Unittest的真实数据竞争数量为45。从TP来看，AIRaceTest检测出了全部真实数据竞争。

从FP来看，Eraser报告出了许多不存在的数据竞争，因为Eraser忽视了许多确定性的同步原语；Djit+由于使用了happens-before关系来检测数据竞争，因此误报不多；Thread Sanitizer尽管使用了happens-before关系与lockset算法来检测数据竞争，但无法识别许多隐形同步对，误报较多；AIRaceTest在采用happens-before关系与lockset算法结合检测数据竞争的基础上针对性地剔除了一些隐形同步对，因此误报较少。

从FN可以发现，Djit+容易受到线程调度的影响，因此漏报较多；Eraser与Thread Sanitizer都是在语句层面对数据竞争进行检测，也会遗漏部分数据竞争；AIRaceTest在happens-before关系与lockset算法结合的基础上，遍历了所有不在同一线程的指令所形成的指令对，没有遗漏数据竞争。可见，AIRaceTest数据竞争检测更加精确。

为了进一步评估AIRaceTest的性能，本文选择Parsec基准程序3.1作为测试程序。这套基准程序由13条多线程程序组成，其中包含了各种产生数据竞争的情况，能比较全面地对检测工具进行评估。

表 3中显示了AIRaceTest、Eraser、Djit+以及Thread Sanitizer 4种检测工具对Parsec基准程序3.1中检测出数据竞争的6条多线程程序的检测结果。在对bodytrack和fluidanimate的检测中，由于Eraser、Djit+与Thread Sanitizer的检测方式没有定位到指令级，而bodytrack中存在着共享变量在函数中循环读写的情况，因此AIRaceTest能检测出在对共享变量进行循环访问中每一次数据竞争的产生，而Eraser、Djit+与Thread Sanitizer只是将共享变量的循环访问视为一次数据竞争，并且Djit+由于受到线程调度的影响产生部分漏报。

在对dedup与swaptions的检测中，Eraser与Thread Sanitizer产生了一些误报，因为共享变量在主线程中进行初始化之后传递给了子线程，并且初始化时没有受到任何的锁保护，所以Eraser与Thread Sanitizer中使用的lockset算法在初始化时报告了数据竞争，但事实上共享变量在主线程中初始化之后传递给子线程是有着明确的先后关系的，不会造成数据竞争。

x264和streamcluster中存在着由if条件造成的隐形同步对，Eraser与Thread Sanitizer两种方法无法对其进行有效剔除，产生了一些误报，AIRaceTest在动态插桩过程中检测了每条指令的汇编源码，并将其作为一项特征来建立随机森林模型，因此有效剔除了由if条件语句造成的隐形同步对，避免了此类误报。由于x264中的线程数量较多，Djit+受到了线程间不确定性调度的严重影响，因此产生了大量漏报，而AIRaceTest遍历了所有来自不同线程间的指令所形成的指令对，不受线程间不确定性调度的影响，漏报较少。

综上所述，由Unittest与Parsec基准程序3.1实验分析结果可得，Eraser、Djit+与Thread Sanitizer 3种检测工具误报率分别为30.2%、12.8%与19.7%，误报率平均值20.9%，漏报率分别为19.4%、25.3%与11.0%，漏报率平均值18.9%；AIRaceTest误报率为10.3%，漏报率为6.6%。相比于其他3种检测工具的误报率及漏报率的平均值，AIRaceTest的误报率及漏报率分别降低了10.6%和12.3%。

3.4 开销分析

本文将AIRaceTest、Eraser、Djit+与Thread Sanitizer 4种检测工具进行开销方面的对比分析，图 10和11分别显示了AIRaceTest、Eraser、Djit+与Thread Sanitizer 4种检测工具检测Parsec基准程序3.1中vips、bodytrack、streamcluster、dedup、ferret与x264这6个多线程程序的时间及内存开销，这6个多线程程序的线程数分别为4、10、17、25、35和64。

图 10为AIRaceTest、Eraser、Djit+与Thread Sanitizer检测这6个多线程程序时间开销走势图。Djit+与Thread Sanitizer方法检测时间开销随着线程数的增加快速增长，这是因为这两种方法都使用到了happens-before关系来进行检测，当线程数较多时，线程间调度较为复杂，需要频繁地切换线程状态，无法在整个程序运行期间保证程序的并行性，导致检测时间较长。Eraser采用的lockset算法计算过程较为复杂，耗时较多。AIRaceTest的检测机制是指令级的，不受线程调度的影响，不需要频繁地切换线程状态，且AIRaceTest利用随机森林模型高效处理大量数据的优势节省了一些时间，在线程数较多时，AIRaceTest的检测时间少于Eraser、Djit+与Thread Sanitizer的平均检测时间，时间开销降低了约41.8%。

图 11为AIRaceTest、Eraser、Djit+与Thread Sanitizer检测这6个多线程程序的内存开销走势图。当线程数较多时，Djit+与Thread Sanitizer检测方法占用的内存较大，并且随着线程数的增加增长速率较快，这是因为Djit+与Thread Sanitizer需要分配大量的内存空间来记录新线程的向量时钟，Thread Sanitizer需要同时记录各线程的向量时钟和所有并发历史访问的锁集合状态。Eraser需要分配内存空间去监测并计算锁保护状态，线程数越多计算量越大，但不需要为新线程分配新的内存空间，只需在程序开始时分配一片内存空间记录锁保护状态即可。AIRaceTest只需记录各线程的向量时钟和锁保护状态，不需要分配空间来控制线程调度和计算锁保护状态，并且剔除了无对应源码的指令，最后用随机森林模型来分类预测数据竞争，所需内存开销较少，相对于Eraser、Djit+与Thread Sanitizer内存开销的平均值，AIRaceTest内存开销降低了约22.4%。

综上所述，由Parsec基准程序3.1中的6个线程数不同的多线程程序的检测结果可知，AIRaceTest检测并发现程序数据竞争的效率较高，受线程数的影响较小，稳定性较好。

4 局限性分析

目前，RFDR存在优势的同时也存在着一些局限性：1)虽然绝大多数的隐形同步对是由if语句造成的，但并不是所有的隐形同步对都如此，因此会出现部分误报，下一步工作中将尝试识别并剔除更多类型的隐形同步对。2)本文用于训练RFDR模型的特征较少，下一步工作中将尝试找出更多造成数据竞争的特征来训练模型，提高模型分类预测精度。3) AIRaceTest的训练样本集的选择在一定程度上影响到构建模型的质量，现有的多线程程序数据竞争检测基准程序缺乏，下一步将尝试构造更多多样的、公开的数据竞争检测基准程序。

5 总结

本文提出一种改进的hybrid数据竞争指令级检测算法，构建了多线程程序数据竞争检测模型RFDR，并基于该模型实现了检测工具AIRaceTest，通过利用happens-before关系与lockset算法指令级检测的数据竞争结果和检测过程中得到的数据竞争各项特征来建立随机森林模型，然后对所有指令对是否会产生数据竞争进行分类预测。AIRaceTest基本上消除了漏报，同时剔除了一些隐形同步对，降低了误报。在效率方面，AIRaceTest利用随机森林模型能高效处理大量数据的优势，并且利用指令级检测不受线程调度影响的特点，大大降低了时间与内存开销。对Google data-race-test和Parsec基准程序3.1的数据竞争检测结果证实了AIRaceTest的精度和效率高于其他常用检测工具。