ACM通信

科马克·弗拉纳根、斯蒂芬·n·弗洛伊德著
ACM通信，2010年11月，53卷第11期，93-101页
10.1145/1839676.1839699
评论

众所周知，多线程程序容易出现竞态条件。之前的工作开发了精确的动态竞赛探测器，从不报告假警报。然而，这些检查器使用昂贵的数据结构，如矢量时钟(vc)，这会导致显著的性能开销。

本文利用了这样一种见解，即在大多数情况下，风险投资的全面性并不是必需的。也就是说，我们可以用一种自适应的轻量级表示来代替VCs，对于目标程序的几乎所有操作，它都需要恒定的空间并支持恒定的时间操作。实验结果表明，所提出的种族检测算法在不损失精度的前提下，速度是现有精确种族检测器的两倍以上。

回到顶部

1.简介

多线程程序容易出现竞争条件和其他并发错误，如死锁和违反预期的原子性或确定性属性。多核处理器的广泛采用加剧了这些问题，既推动了多线程软件的发展，也增加了现有多线程系统中线程的交错。

当两个线程并发地执行内存访问时，就会发生竞争条件冲突。当读写同一个内存位置且其中至少有一个是写时，访问发生冲突。在这种情况下，执行两个相互冲突的访问的顺序可能会影响程序的后续状态和行为，可能会产生意想不到的和错误的结果。

竞态条件是出了名的有问题，因为它们通常只在罕见的交错上造成问题，使它们难以检测、繁殖和消除。因此，之前的许多工作都集中在检测竞态条件的静态和动态分析工具上。

为了最大化测试覆盖率，竞争检测器使用一个非常广泛的概念，即当两个冲突的访问被认为是并发的。这些访问不需要完全同时执行。相反，中心要求是两个访问之间不存在“同步依赖性”，例如一个线程释放的锁与另一个线程获得的后续锁之间的依赖性。这些不同类型的同步依赖在执行跟踪中的指令上形成部分顺序之前的关系。¹³两个内存访问被认为是并发如果它们不是按照这个before - happens关系排序的。

在本文中，我们关注的是在线动态竞赛检测器，根据其是否报错警，通常可以分为两类。精确的种族探测器从来不会产生错误的警报。相反，它们为观察到的跟踪计算happens-before关系的精确表示，并且当且仅当观察到的跟踪具有竞态条件时报告错误。注意，一个特定程序通常有许多可能的跟踪，这取决于测试输入和调度选择。然而，精确的动态竞赛检测器不会对所有可能的轨迹进行推理，也可能无法识别仅当采用其他代码路径时才发生的竞赛。虽然全面覆盖是可取的，但这是以潜在的错误警报为代价的，因为停止问题的不可预测性。为了避免这些误报，精确的竞态检测器只专注于检测在观察到的痕迹上发生的竞态条件。

通常，精确的检测器表示before - happens关系向量时钟(风险投资),14就像DJIT⁺种族探测器。16然而，矢量时钟的维护成本很高，因为VC对系统中每个线程的信息进行编码。因此，如果目标程序有n线程，每个VC都需要O（n)存储空间和VC操作(如比较)所需的存储空间O（n)时间。由于VC必须为每个内存位置维护并在每次访问该位置时进行修改，因此O（n)时间和空间开销排除了在许多设置中使用基于vc的竞赛检测器。

各种各样的选择不精确的竞赛检测器已经被开发出来，它可以提供更好的性能(有时还可以提供更好的覆盖率)，但在一些没有竞赛的程序中会报告错误的警报。例如，Eraser的LockSet算法18强制执行基于锁的同步规程，如果对特定内存位置的每次访问都没有一致持有锁，则报告错误。然而，对于使用替代同步习惯用法的程序，如fork / join同步或障碍。一些基于lockset的种族检测器包括有限的事件发生前推理，以提高这种情况下的精确度。15，<一个href="#R16">16，<一个href="#R22">22

其他优化包括使用静态分析或动态转义分析3.，<一个href="#R21">21或者使用“手风琴”风投，为线程寿命较短的程序减少空间开销。5的替代方法记录程序事件死后种族身份。1，<一个href="#R4">4，<一个href="#R17">17

尽管这些不精确的工具成功地检测到了竞争条件，但它们产生许多错误警报的潜力限制了它们的有效性。事实上，在一些工具产生的虚假警告中识别真正的错误已经被证明是非常困难和耗时的。即使代码块看起来可疑，由于当前代码维护人员(还)不理解某些微妙的同步规程，它仍然可能是无竞争的。更糟糕的是，当试图“修复”这些工具产生的虚假警告时，可能会添加其他真正的错误(例如死锁或性能问题)。相反，真实的竞争条件可以被忽略，因为它们似乎是假警报。

本文利用的洞察力是，尽管vc提供了一种表示happens-before关系的通用机制，但在大多数情况下，它们的全部通用性实际上并不是必需的。多线程程序中的绝大多数数据都是线程本地的、锁保护的或读共享的。我们的FASTTRACK分析使用happens-before关系的自适应表示，为这些常见情况提供恒定时间和恒定空间开销，而不会损失任何精度或正确性。

更详细的，一个基于vc的种族检测器如DJIT⁺记录最近一次写入每个变量的时间x通过每个线程t。相比之下，FASTTRACK利用所有写入到的观察x是完全按照发生前的关系排序的，假设没有比赛x已经被检测到，并且只记录了关于最后写信给x。具体来说，FastTrack记录写入的时钟和线程标识符。我们将时钟和线程标识符的这一对称为时代。

对线程本地数据和锁保护数据的读操作也是完全有序的，假设没有竞争x已经检测到，FASTTRACK只记录从这些数据最后一次读取的时间。FASTTRACK在必要时(例如，当数据变成读共享时)自适应地从epoch切换到VCs，以保证不损失精度。它还可以在可能的情况下从vc切换回轻量级时代(例如，当读取共享数据随后被更新时)。

使用这些表示技术，FASTTRACK减少了几乎所有被监视操作的分析开销O（n)时间,n目标程序中的线程数是否为O(1)时间。

除了提高性能之外，epoch表示还减少了空间开销。一个基于vc的种族检测器需要O（n)空间的目标程序的每个内存位置，可以迅速耗尽内存资源。相比之下，FASTTRACK减少了线程本地和锁保护数据的空间开销O（n)O（1）.

为了进行比较，我们实现了6个不同的动态竞赛检测器:FASTTRACK和文献中描述的其他5个竞赛检测器。在Java基准测试(包括Eclipse编程环境)上的实验结果表明，FASTTRACK优于其他工具。例如，它比传统的基于vc的赛车检测器提供了近10倍的加速，比DJIT提供了2.3倍的加速⁺算法。与ERASER相比，它还大幅提高了精度，而不影响性能。

回到顶部

2.预赛

2.1.多线程程序的痕迹

我们从一些关于多线程执行跟踪的术语和定义开始。一个程序由许多并发执行的线程组成，每个线程都有一个线程标识符t工业贸易署。这些线程操作变量xVar和锁米锁。一个跟踪的序列捕获多线程程序的执行操作由不同的线程执行。线程的操作t可以执行包括:

• 理查德·道金斯(t, x)而且或者说是(t, x)，它从一个变量读取和写入一个值x
• acq (t,米)而且rel (t,米)，它们获取并释放一个锁米
• 叉(t, u)，它分叉一个新的线程u
• 加入(t, u)，它会阻塞直到线程u终止

的之前的关系(<)是捕获控制和同步依赖关系的操作的部分顺序。特别是关系一个<b认为只要操作一个前进行操作b和适用下列条件之一:

• 程序顺序:这两个操作由同一个线程执行。
• 同步顺序:这两个操作获取或释放同一个锁。
• 叉顺序:第一个操作是叉(t, u)第二个是通过线程u。
• 连接顺序:第一个操作是线程操作u第二点是加入(t, u)。

此外，happens-before关系是传递封闭的:即if一个<b而且b<c然后一个<c。

如果一个之前b，那么我们也这样说B发生在a之后。如果跟踪中的两个操作与happens-before关系无关，则会考虑它们并发。两个内存访问冲突如果它们都访问(读或写)同一个变量，并且至少有一个操作是写操作。使用这个术语，跟踪具有竞态条件如果它有两个并发的冲突访问。

2.2.矢量时钟和DJIT⁺算法

在介绍FASTTRACK算法之前，我们简要回顾了DJIT算法⁺在线种族检测算法，¹⁶这是基于风投的。14一个VC

为系统中的每个线程记录一个时钟。矢量时钟是部分有序的()，并有一个相关的连接操作()和最小元素()．此外，还有助手函数公司_t增加t- VC组件:

在DJIT⁺，每个线程都有自己的时钟，在每次锁释放操作时递增。每个线程t还保持着一个VC C_t这样，对于任何线程u，时钟条目C_t（u)记录线程最后一次操作的时钟u这发生在线程的当前操作之前t。此外，该算法维护了VC L_米对于每个锁m。这些VCs在同步操作上进行更新，这些同步操作在不同线程的操作之间施加了一个happens-before顺序。例如，当线程u释放锁米, DJIT⁺L算法更新_米是C_u．如果一个线程t随后获得米，算法更新C_t是C_tl_米，因为线程的后续操作t在释放操作之后。

为了识别冲突的访问，DJIT⁺算法保持两个vc, R_x和W_x，对于每个变量x。对任何线程t, R_x（t)和W_x（t)记录最后一次读和写的时钟x通过线程t。一个读x通过线程u是无种族限制的，只要它发生在每个线程的最后一次写入之后，即W_xC_u．一个写x通过线程u如果写操作发生在之前对该变量的所有访问之后，即W_xC_u和R_xC_u．

作为一个例子，请考虑中显示的执行跟踪片段<一个href="#F1">图1，其中包括DJIT的相关部分⁺仪表状态:VCs₀和C₁对于线程0和1;风投公司L_米和W_x用于锁的最后释放米最后一个写变量x,分别。我们为每个VC展示了两个组件，但是目标程序当然可能包含额外的线程。一个

在写或者说是(0,x), DJIT⁺更新W_x线程0的当前时钟。在释放rel(0,米),我_米用C更新₀．在获得acq(1,米), C₁与L相连_米，从而捕获上面所示的虚线release-acquire - happens-before边。第二次写，DJIT⁺比较了风险投资:

由于该检查通过，所以这两个写操作不是并发的，也不会报告竞态条件。

回到顶部

3.FastTrack算法

基于vc的竞赛检测器如DJIT的局限性⁺是他们的表现，因为每个VC的要求O（n)和每个VC操作(复制、比较、连接等)所需的空间O（n)时间。

经验基准数据表明，读和写操作占监视操作的绝大多数(超过96%)。FASTTRACK背后的关键见解是，在超过99%的这些读和写操作中，vc的全面通用性是不必要的:可以使用更轻量级的happens-before信息表示。只有一小部分由目标程序执行的操作需要昂贵的VC操作。

我们首先概述我们的分析如何在内存位置上捕获每种类型的竞态条件。竞态条件是:Awritewrite竞态条件(写操作与后面的写操作同时进行);一个writeread竞态条件(写操作与后面的读操作同时进行);或者一个读写竞态条件(读操作与后面的写操作并行)。

检测WriteWrite比赛:我们首先考虑如何有效地分析写操作。在跟踪中的第二个写操作<一个href="#F1">图1, DJIT⁺比较了vc W_xC₁来决定是否有比赛。然而，仔细检查就会发现，没有必要记录整个Vc 4,0，…从第一次写到x。假设没有检测到比赛x到目前为止，那么都写到了x完全由happens-before关系和只有关键信息需要记录的是执行最后一次写的线程的时钟(4)和标识(线程0)。此信息(线程0的时钟4)足以确定后续的写入是否x正在与前面的任何写入进行竞争。

我们指的是一对时钟c和一个线程t作为一个时代,表示c@t。虽然非常简单，但epoch提供了重要的轻量级表示，用于有效地记录事件发生前关系的足够精确的方面。与VCs不同，epoch只需要固定的空间并支持固定时间的操作。

一个时代c@t之前一个VCV（c@tV)当且仅当epoch的时钟小于或等于vector中相应的时钟:

我们使用表示最小纪元0@0。

使用这个优化的表示，FASTTRACK分析来自<一个href="#F1">图1使用更紧凑的工具状态，只记录写入纪元W_x为变量x，而不是整个VC W_x，减少空间开销，见<一个href="#F2">图2．(C而且l在DJIT中记录与C、L相同的信息⁺．)

第一次写信给x， FASTTRACK执行O(1) -时代写W_x: = 4 @0。FASTTRACK随后确保第二次写入不与前一次写入并发O(1) -比较:

总而言之，epoch减少了用于检测从的读写冲突的空间开销O（n)O(1)每个分配的内存位置，并替换O（n)时间VC比较””O(1) -比较”"．

检测WriteRead比赛:在新的表示下检测写读种族也很简单。每次从x与当前风险投资C_t，我们检查读是否发生在最后一次写入之后O(1) -比较W_xC_t．

检测读写比赛:检测读写竞争条件有些困难。写操作在无种族程序中是完全有序的，而读操作则不一定完全有序。因此，对变量的写操作x可能和上次读到的有冲突x由任何其他线程，而不是到目前为止看到的整个跟踪中的最后一次读取。因此，我们可能需要记录整个VCR_x,在这R_x（t)记录最后一次读取的时钟x通过线程t。

然而，在很多情况下，我们可以避免保持一个完整的VC。我们对各种多线程Java程序的数据访问模式的研究表明，读操作通常是完全有序的在实践中，特别是在下列常见情况下:

• 线程本地数据，其中只有一个线程访问一个变量，因此这些访问完全按程序顺序排序
• 受锁保护的数据，其中对变量的每次访问都持有一个保护锁，因此所有的访问都是完全有序的，要么按程序顺序(针对同一线程的访问)，要么按同步顺序(针对不同线程的访问)

只有当数据是无序的时，读通常是无序的read-shared即，当数据首先由一个线程初始化，然后在多个线程之间以只读方式共享时。

FASTTRACK对每个变量的读取历史使用自适应表示，该表示针对完全有序读取的常见情况进行了优化，同时在必要时仍然保留VCs的全部精度。

特别是，如果对变量的最后一次读取发生在所有前面的读取之后，那么FASTTRACK只记录最后一次读取的时间，这足以精确地检测对该变量的后续写入是否与任何读取整个程序历史。因此，对于线程本地和锁保护的数据(它们确实显示完全有序的读取)，FASTTRACK只需要O(1)空间为每个分配的内存位置且仅O(1)每次内存访问的时间。

在不太常见的情况下，读取不是完全有序的，FASTTRACK存储整个VC，但仍然处理的读取操作O(1)时间。因为这样的数据通常是读共享的，所以很少对这样的变量进行写操作，而且它们的分析开销可以忽略不计。

3.1.分析细节

基于上述直觉，我们现在详细描述FASTTRACK算法。我们的分析是一个在线算法，它的分析状态由四个部分组成:

• C_t线程的当前VC是多少t。
• l_米VC的锁是最后释放的吗m。
• R_x是最后一次阅读的时代吗x，如果所有其他读取都发生在该读取之前，或者else是一个记录最后一次读取的VCx由多个线程。
• W_x最后写的时代是到吗x。

分析开始于C_t＝公司_t（)，因为所有线程的第一个操作都不是按照happens-before排序的。此外,最初l_米＝而且R_x＝W_x＝．

图3介绍了FASTTRACK(左列)和DJIT的关键细节⁺(右列)处理目标程序的读写操作。对于每个读或写操作，相关规则按照呈现的顺序应用，直到匹配当前检测状态为止。如果断言失败，则存在竞态条件。该图显示了在第4节描述的程序中观察到的指令频率，以及每个规则的应用频率。例如，我们的基准测试执行的所有内存和同步操作中有82.3%是读取操作，规则[FT READ SAME EPOCH]用于检查其中63.4%的读取操作。昂贵的O（n)时间操作以灰色突出显示。

读操作:前四条规则为分析读操作提供了各种备选方案理查德·道金斯(t, x)。第一条规则[FT READ SAME EPOCH]优化了x在这个时代已经读过了。这个快速路径只需要一个历元比较，并处理超过60%的所有读取。我们使用E_t表示当前时代c@t的线程t,在那里c＝C_t（t)是t当前的时钟。DJIT⁺采用了类似的规则[DJIT]⁺读相同的时代)。

其余三个读规则都通过快速epoch-VC比较检查写-读冲突W_xC_t，然后更新R_x适当。如果R_x已经是一个VC，那么[FT READ SHARED]只是更新该向量的适当组件。注意，来自同一纪元的多个读共享数据的读取都包含在此规则中。我们可以扩展规则[FT READ SAME EPOCH]来处理读共享数据的同纪元读取R_x风投而且R_x（t) =C_t（t)．扩展的规则将覆盖78%的所有读取(与DJIT相同⁺READ SAME EPOCH])，但不会明显提高性能。

如果当前读发生在前一个读纪元之后(其中前一个读可能是由同一个线程或不同的线程进行的，假定是交错同步)，[FT read EXCLUSIVE]只是更新R_x访问线程的当前纪元。对于更一般的情况，当前的读与之前的读是并发的，[FT read SHARE]分配一个VC来记录的时代这两个读，因为任何读都可能随后参与读写竞赛。

在这三条规则中，最后一条规则是最昂贵的，但很少需要(0.1%的读取)，前三条规则提供了通常执行的常量时间快速路径。相比之下，相应的规则[DJIT⁺读)总是执行一个O（n)时间VC比较这些情况。

写操作:接下来的三条FASTTRACK规则处理写操作或者说是(t, x)。规则[FT WRITE SAME EPOCH]优化了x，这适用于71.0%的写操作，而DJIT⁺包含一个可比较的规则。[FT WRITE EXCLUSIVE]为28.9%的写提供了快速路径R_x是一个epoch，该规则检查写操作是否发生在所有之前的访问之后。在这种情况下R_x是一个VC， [FT WRITE SHARED]需要一个完整的(慢的)VC比较，但这个规则只适用于很小的一部分(0.1%)写。相比之下，相应的DJIT⁺规则[DJIT⁺write]需要对29.0%的写操作进行VC比较。

其他操作:图4展示了FASTTRACK如何处理同步操作。这些操作是罕见的，传统的从昂贵的VC操作的角度来分析这些操作是完全足够的。因此，这些FASTTRACK规则类似于DJIT的规则⁺以及其他基于风险投资的分析。

例子:中的执行跟踪<一个href="#F5">图5说明了FASTTRACK如何为读取历史动态调整表示R_x的一个变量x。最初,R_x是,这表明x尚未被阅读。在第一次读操作之后理查德·道金斯(1,x)，R_x成为纪元1@1，记录该读取的时钟和线程标识符。第二次读理查德·道金斯(0,x)在时钟8上与第一次读并行，因此FASTTRACK切换到VC表示8,1，…为R_x记录最后一次读取的时钟x通过线程0和1。两个线程连接后，写入操作或者说是(0,x)发生在所有读取之后。因此，任何后面的操作都不能与其中一个读操作处于竞争状态，而同时又与该写操作处于竞争状态，因此规则[FT write SHARED]丢弃了的读历史x通过重置R_x来，也可以切换x回到epoch模式，从而优化以后的访问x。然后设置跟踪中的最后一次读取R_x到一个非极小期。

回到顶部

4.评价

为了验证FASTTRACK，我们将其实现为多线程Java程序的ROADRUNNER动态分析框架的一个组件。¹⁰ROADRUNNER接受一个编译好的Java目标程序作为输入，并在目标程序中插入检测代码，以生成内存和同步操作的事件流。后端检查工具在目标执行时处理这些事件。FASTTRACK实现扩展了迄今为止描述的算法，以处理额外的Java原语，例如挥发性变量和wait ()，如前所述。8一些基准测试包含了障碍同步的错误实现。9FASTTRACK包含专门的分析来补偿这些错误。

我们将FASTTRACK的精度和性能与在同一框架中实现的其他六种分析进行比较:

• - EMPTY，一个简单的检查器，不执行分析，用于测量ROADRUNNER的开销
• ——橡皮擦,18基于第1节中描述的LockSet算法的不精确竞品检测器
• - GOLDILOCKS，一个基于LockSets扩展概念的精确种族检测器7
• - BASICVC，一个传统的基于VC的竞态检测器，为每个内存位置维护一个读和一个写VC，并对每次内存访问执行至少一次VC比较
• ——DJIT⁺，一款基于vc的高性能竞赛检测器16在第二节中描述
• - MULTIRACE，一个混合LockSet/DJIT⁺种族探测器16

4.1.性能和精度

表1列出了来自Java Grande Forum的各种基准测试程序的大小、线程数和非仪器化运行时间，12标准绩效评估公司，19和其他地方。2，<一个href="#R7">7，<一个href="#R11">11，<一个href="#R21">21所有的计时测量都是10个测试运行的平均值。运行间的变异性通常小于10%。

“仪器化时间”列显示了每个工具下每个程序的运行时间，报告为与未仪器化运行时间的比率。因此，在EMPTY工具下，目标程序的运行速度平均要慢4.1倍。大部分开销是由于将所有目标程序操作通信到后端检查程序。

对于动态竞态条件检查器来说，不同程序的减速变化并不罕见。不同的程序表现出不同的内存访问和同步模式，其中一些对分析性能的影响比其他的更大。此外，插装会影响缓存性能、类加载时间和其他底层JVM操作。这些差异有时甚至会使仪器化的程序比未仪器化的程序运行得稍快一些(如colt)。

最后六列显示了每个检查器产生的警告的数量。这些工具对每个类的每个字段最多报告一个race，对程序源代码中的每个数组访问最多报告一个race。《FASTTRACK》的8个警告都反映了真实的比赛情况。其中一些是良性的(比如tsp, mtrt,jbb)，但是其他的可能会影响程序行为(例如光线跟踪而且hedc)．15，<一个href="#R20">20.，<一个href="#R21">21

橡皮擦的比较:我们对Eraser的重新实现产生了8.7倍的开销，这与建立在未修改jvm之上的类似Eraser实现具有竞争力。15令人惊讶的是，FASTTRACK在某些程序上比ERASER稍微快一些，尽管它执行的精确分析在传统上被认为比较昂贵。

更重要的是，ERASER报告了许多与实际比赛不符的虚假警告。扩展我们的ERASER实现，以推断附加的同步构造，例如fork / join或等待/通知操作,16，<一个href="#R22">22会消除一些虚假的警告，但不是全部。在hedc， ERASER报告了一个虚假的警告，但也错过了FASTTRACK报告的两个真正的竞态条件，这是由于ERASER算法在如何判断线程本地数据和读共享数据方面的(故意的)不合理。18

BASICVC和DJIT⁺比较:DJIT⁺和BasicVC报告的比赛条件与FASTTRACK完全相同。也就是说，所有三个检查器提供相同的精度。然而，FASTTRACK的性能优于其他检查程序。它大约比BasicVC快10倍，比DJIT快2.3倍⁺．这些性能改进的主要原因是减少了风险投资的分配和使用。在所有基准测试中，DJIT⁺分配了超过7.9亿风投，而FASTTRACK只分配了510万。DJIT⁺超过51亿次O（n)时间的VC操作，而FASTTRACK只执行了1700万。在某些程序中，存储额外VCs的内存开销会导致缓存性能显著下降，特别是那些随机访问大型数组的程序。当检查线程数量较多的程序时，这些工具可能会产生更大的开销。

MultiRace比较:MultiRace维护DJIT⁺的插装状态，以及每个内存位置的锁集。16检查器在一个纪元中第一次访问时更新位置的锁集，只有在该锁集变为空后才执行完整的VC比较。这种综合在很大程度上减少了VC操作的数量，但是引入了存储和更新锁集的开销。此外，对线程本地和读共享数据使用ERASER的不可靠状态机会导致不精确。

我们重新实现的MULTIRACE算法表现出与DJIT相当的性能⁺．MULTIRACE的性能(事实上，我们所有其他的检查器也是如此)可以通过采用粗粒度的将对象的所有字段表示为插装状态中的单个“逻辑位置”的分析。16，<一个href="#R22">22

金发女孩比较:金发女孩7是一个精确的比赛检测器，它不使用VCs来捕获发生之前的关系。相反，它为每个内存位置维护一组“同步设备”和线程。该集合中的线程可以安全地访问内存位置，并且线程可以通过执行集合中同步设备所描述的任何操作将自己添加到该集合中(并可能删除其他线程)。

GOLDILOCKS是一种复杂的优化算法，理想情况下需要与底层虚拟机和垃圾收集器紧密集成，这在ROADRUNNER下是不可能的。由于这些困难，在ROADRUNNER中重新实现的GOLDILOCKS在我们的基准测试中产生了31.6倍的减速，但在lufact中耗尽了内存。我们的Goldilocks重新实现错过了三场比赛hedc，因为高效处理线程本地数据的性能优化不合理。7我们相信，通过将GOLDILOCKS和其他工具集成到虚拟机中，可以实现一些性能改进。

4.2.检查eclipse的竞态条件

为了在更实际的设置中验证FASTTRACK，我们还将其应用于Eclipse开发环境中的五个常见操作。6这包括启动Eclipse、导入项目、重新构建大小工作空间以及启动调试器。这些操作的检查开销如下:

ERASER报告了这五个测试中960个不同字段和数组访问上的潜在竞争，这主要是因为Eclipse使用了许多ERASER无法处理的同步习惯用法，例如wait ()而且notify ()、信号量和读写锁。FASTTRACK报告了27个不同的警告，其中4个随后被证实具有潜在的破坏性。9DJIT⁺报告了28个警告，这些警告与FASTTRACK报告的严重重叠，但调度的差异导致一些警告被错过，并发现了一些新的(良性的)比赛。虽然我们对日食的探索还远未完成，但这些初步观察结果相当有希望。FASTTRACK能够以比现有工具更低的运行时和内存开销精确地检查大型应用程序。

回到顶部

5.结论

竞态条件很难发现和修复。精确的竞争检测器避免了识别和消除虚假警告的程序员开销，当在具有复杂同步的大型程序上使用不精确的检查器时，这是特别有问题的。我们的FASTTRACK分析是一种新的精确的种族检测算法，通过跟踪更少的信息，并根据内存访问模式动态调整其happens-before关系的表示，实现了比现有算法更好的性能。我们已经使用FASTTRACK来识别像Eclipse编程环境这样大的程序中的数据竞争，并且还改进了依赖于精确数据竞争信息的其他分析的性能，例如序列化检查器。⁸FASTTRACK算法和自适应历元表示实现起来很简单，在多线程软件的其他动态分析中可能很有用。

回到顶部

致谢

这项工作部分由NSF赠款0341179,0341387,0644130和0707885支持。我们感谢Ben Wood在ROADRUNNER中实现了Goldilocks，并感谢他对本文草稿的评论，感谢Tayfun Elmas、Shaz Qadeer和Serdar Tasiran对Goldilocks的帮助。

回到顶部

回到顶部

回到顶部

回到顶部

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2010 ACM, Inc。