使用 O(1) 个样本的动态竞争检测

《Communications of the ACM》：Dynamic Race Detection with O(1) Samples

　　摘要：基于“发生在前”原则的动态分析是检测大规模软件项目中数据竞争的主要技术，因为这种技术不会出现误报。然而，这种分析的成本很高，因为它在每个事件处都需要更新昂贵的向量时钟，这使得它只适用于内部测试。在本文中，我们提出了一种基于采样的随机竞争检测器，在最坏的情况下，它只会处理被分析的执行轨迹中的一定数量的事件。这是首个运行时间 subordinate-linear（即时间复杂度为 o(n)，其中 n 是执行轨迹的长度）的动态竞争检测算法；之前的基于采样的方法（如 Pacer）的运行时间是线性级（即 O(n)）。我们的算法是一种用于检测 HB-竞争的属性检测器——它是可靠的，因为它永远不会报告误报，并且对于与无竞争轨迹在汉明距离上相差较大的轨迹，该算法能以很高的概率检测出 HB-竞争。我们对算法的实验评估以及与最先进的确定性算法和基于采样的竞争检测器的比较表明，该算法确实具有显著的低运行时间，并且能够频繁地检测到竞争。

1. 引言：如果一个并发程序在执行过程中有一对线程连续访问共享内存位置，并且其中一个访问会向共享内存位置写入值，那么就说这个程序存在数据竞争（或简称为竞争）。数据竞争是并发程序中最常见的错误来源之一，也是导致更严重问题（如数据损坏）的原因。通常，没有数据竞争是程序语义定义明确以及编译器优化正确运行的前提。可靠的动态数据竞争检测是一种流行的方法，用于识别并发程序中的此类错误。在这里，人们观察程序的单次执行，分析的目的是确定该执行是否提供了程序中存在数据竞争的证据。最简单和最常用的动态数据竞争检测技术是基于 Lamport 的“发生在前”（HB）偏序理论。其思想是（隐式地）计算观察到的执行事件之间的 HB 偏序，并检查是否存在一对按 HB 偏序排序不一致的共享内存访问。基于“发生在前”原则的数据竞争检测被认为是可靠的——存在 HB 顺序不一致的内存访问是程序存在数据竞争的证据。早期的基于向量时钟的算法已经得到了改进，现在已成为实际应用中的首选数据竞争检测方法。然而，由于每个事件都需要更新昂贵的元数据，因此这种分析的运行时间成本很高。这使得动态竞争检测仅适用于内部测试，并使得数据竞争异常这一原本有前景的应用变得不切实际。一种试图降低 HB-竞争检测分析成本的方法是使用采样。这种方法的非正式思路是从观察到的轨迹中抽取一些事件，并仅分析这些抽样的事件子集以确定程序是否存在数据竞争，期望抽样的子集相对于整个轨迹来说较小，并且如果存在竞争，通常找到竞争就足够了。尽管 Bond 等人提出的 Pacer 算法在实验上被证明比已知的确定性竞争检测算法运行得更快，但它仍然分析了线性数量的事件，在许多情况下并不比确定性算法更快。此外，Pacer 和之前的工作通常提供了关于检测每一对竞争事件概率的数学保证（即它们确保每一对构成数据竞争的事件都能以非零概率被检测到）。然而，在实践中，这种保证可能过于保守且不必要的，因为程序执行往往由于循环、重复的函数调用以及在事件驱动系统中重复调用事件处理程序而表现出高度重复的模式。因此，即使错过了一个竞争对，同样的模式也可能在轨迹的其他部分被观察到和采样到。

本工作的动机是探索一种可靠的竞争检测算法的可能性，即使在最坏的情况下，它也能分析执行轨迹中的 sub-linear 数量的事件，但仍然能在执行轨迹层面提供可证明的精确性保证，而不是针对每一对竞争事件的保证。这样的算法可以使可靠的动态数据竞争检测扩展到内部测试之外。

为了实现我们的目标，我们研究了一种用于 HB-竞争检测的属性检测器的设计。对于决策问题 L，一个（单边的）(?, δ)-属性检测器 A 满足以下要求：对于输入 x ∈ L，A 以 1 的概率回答“是”；而对于与 L 中任何输入“?-far”（即距离较远）的输入，A 以至少 1 ? δ 的概率回答“否”。注意，属性检测器的定义基于输入字符串上的距离度量标准。在属性检测中使用的标准距离度量是汉明距离。因此，将其重新表述并专门用于 HB-竞争检测，我们得到以下定义：一个用于 HB-竞争检测的属性检测器 A 是这样的算法：对于任何无竞争的执行 σ，A 以“是”回答；而对于任何至少需要修改 ? 比例的事件才能得到无竞争执行的执行 σ，A 以至少 1 ? δ 的概率回答“否”。任何可靠且完整的 HB-竞争检测算法按定义也是一个竞争检测器，因为它能够区分无竞争和有竞争的执行。然而，属性检测器的要求较低，它只能近似解决决策问题——对于那些存在 HB-竞争但同时又非常接近无竞争执行的执行，属性检测器没有义务正确地将它们分类为具有 HB-竞争。这种灵活性使得计算机科学家能够设计出极其快速但仍然有用的算法来解决各种决策问题，并在过去 25 年中成为了活跃的研究领域。

在本文中，我们提出了一种 (?, δ)-属性检测器 RPT [race property detector]，用于 HB-竞争检测，它可以证明只检查观察到的程序执行中的固定数量的事件。更准确地说，设 t 是线程数量的上限，h 是并发程序执行过程中任何时刻持有的最大锁的数量。我们的属性检测器仅分析执行轨迹 σ 中的 O～(t+h) 个事件，并且当 σ 与无竞争执行集合“?-far”时，以至少 1 ? δ 的概率正确地将其分类为具有 HB-竞争。这里，O～(·) 表示常数、ln(1/δ) 和 (1/?) 因子的叠加。注意，我们的属性检测器检查的事件数量仅依赖于参数 t 和 h，这些参数通常很小，被视为常数，并且与输入执行轨迹的长度无关。我们指出，RPT 是一个可靠的竞争检测器——每当它标记出存在竞争时，执行确实存在真实的 data race。

我们的属性检测器是一个非常简单、几乎天真的算法；实际上，这种简单性在实现和部署时可能是一个优势。其工作原理如下（也在图 1 中展示）。如果输入轨迹“较短”（在算法 2 中有精确定义），RPT 会直接在输入上运行一个确定性的竞争检测器（如 FastTrack8）。否则，RPT 会从输入轨迹 σ 中均匀随机抽取 r∈O(ln(1/δ)ε) 个子轨迹，每个子轨迹的长度为 k∈O(t+hε)，并检查这些抽样的子轨迹中是否包含 HB-竞争。如果包含，则算法声明 σ 是有竞争的；否则，声明其为无竞争的。为了检查任何抽样的子轨迹是否包含 HB-竞争，我们可以使用任何 HB-竞争检测算法。在我们的实验中，我们使用了 FastTrack 算法，该算法使用基于向量时钟的时间戳技术，并采用了时代优化。

如图 1 所示，使用 RPT 进行竞争检测的挑战在于证明这种简单算法的正确性。这意味着我们需要证明，如果通过运行多线程程序观察到的输入 σ 与所有无竞争执行“?-far”，那么我们的算法将以很高的概率找到 HB-竞争。我们的正确性证明依赖于以下关键观察：我们证明任何与所有无竞争执行“?-far”的轨迹都有许多长度为 O～(t+h) 的子轨迹包含 HB-竞争。因此，通过独立抽取一些不同的子轨迹并使用标准的计数论证，可以很高概率地证明算法的答案是正确的。

我们预期，具有恒定运行时间开销的竞争检测器对于实践者来说将非常有用。鉴于我们的属性检测器的正式保证是参数化的（由 ? 和 δ 决定），自然会有人问如何使用我们的算法。毕竟，从表面上看，我们需要知道观察到的执行 σ 与无竞争执行轨迹集合的距离！RPT 与大多数动态技术一样，主要是一种发现错误的方法。因此，我们的建议是将 ? 和 δ 视为开发者可以根据资源可用性和以往经验逐步减少的可调参数。如果在任何阶段发现竞争，就可以开始调试。另一方面，如果没有发现竞争，即使 ? 和 δ 减少，软件开发者也可以根据支持该算法的数学声明更有信心代码的可靠性。最后，我们的实验结果显示，即使算法中使用的 ? 较差，无法准确反映输入 σ 与无竞争执行集合的实际距离，该算法仍然能相当频繁地检测到 HB-竞争。

我们已经实现了 RPT 并对基准示例进行了性能评估，并将其与最先进的确定性（FastTrack）和基于采样的（Pacer）HB-竞争检测器进行了比较，以验证理论上的承诺是否成立。值得一提的是，我们的技术可以模块化地集成到混合竞争检测技术中，以减少动态分析阶段的运行时间，并且可以从额外的静态分析阶段中受益。我们的初步实验结果表明，RPT 是一种有前途的方法。与 FastTrack 和 Pacer 相比，RPT 在大型轨迹上的运行时间最短。此外，随着执行轨迹长度的增加，RPT 的竞争优势也在增强。实际上，在我们的实验中，随着轨迹长度的增加，RPT 的开销趋于平稳。尽管如此，我们的结果显示 RPT 仍然能频繁地检测到竞争。特别是在考虑包含大量竞争警告的轨迹时——当 FastTrack 报告的竞争警告数量与轨迹长度的比值至少为 10?5 时，RPT 检测到竞争的概率至少与 Pacer 相当，甚至更高。尽管在这些实验中 RPT 使用的 ? 值较大（即为 0.01）。详细的实验结果在第 4.2 节中呈现。

2. 背景和初步介绍：本节介绍了数据竞争检测和属性检测的相关符号和背景知识。

2.1 轨迹和数据竞争：我们工作的重点是动态竞争检测，其中我们监控并发程序的执行轨迹，观察不同线程生成的事件，并分析这些事件以推断存在数据竞争的情况。每个事件都用元组 ?t, o? 标记（简称为 e = ?t, o?），其中 t 是执行 e 的线程的唯一标识符，o 表示与 e 相关的操作。在我们的讨论中，操作 o 可以是：(a) 对内存位置 x 的读/写访问（即 o = r(x) 或 o = w(x)），或 (b) 基于锁的同步——获取/释放锁 ?（即 o = acq(?) 或 o = rel(?)）。我们使用 thr(e) = t 和 op(e) = o 来表示事件 e = ?t, o?。因此，可以将一个跟踪（trace）视为一系列此类事件的序列；出现在跟踪σ中的事件集合被表示为Eventsσ。我们用Threadsσ、Locksσ和Memσ来表示在跟踪σ中出现的线程、锁和内存位置的集合。我们用|σ|来表示σ的长度。

子跟踪。如上所述，跟踪是事件的序列。我们将采用这样的约定：序列中的第一个事件的索引为0。因此，长度为n的跟踪形式为σ=e0e1...en-1。跟踪σ中的第i个事件（即ei）也将表示为σ[i]。子跟踪σ[i,j]=eiei+1...ej?1是从索引i到索引j?1的σ的子序列。当j≤i时，我们约定σ[i,j]为空序列ε。跟踪σ1=e0...en?1和σ2=f0...fm?1的连接结果是长度为n + m的序列e0...en?1f0...fm?1，并将其表示为σ1σ2。

格式良好的跟踪和子跟踪。并发程序的执行除了是上述形式的事件序列外，还满足一些属性。如果同一锁上的临界区不重叠，则跟踪σ=e0...en?1是格式良好的。也就是说，对于每个j<σhb，是eventsσ上的最小二元关系，使得对于任何两个事件e1 ≠ e2 ∈><σhbe2当e1在σ中发生在e2之前，并且满足以下条件之一：（程序顺序）thr(e1) = thr(e2)；（锁同步）e1释放了锁?，而e2获取了该锁（即op(e1)=rel(?)且op(e2) =>< /><σhbe2。如果一对事件（e1 , e2）都属于σ，并且都在共同的位置x上进行内存访问（假设是写入操作），并且至少有一个是写入操作，则称这对事件是冲突的。如果σ中存在这样的冲突对（e1, e2），则称σ存在hb竞争。否则，称σ没有数据竞争。 关于hb偏序的一个重要观察是它是局部确定的，也就是说，一对事件是否按hb顺序排列仅取决于跟踪中这两个事件之间的事件。这在命题1中得到了形式化，并且我们的随机算法将充分利用这一特性。 命题1。设σ=e0e1 · · ·>< />< /><σ[i,j+1]hbej。 2.2 动态数据竞争检测。数据竞争可以通过逐个处理事件、更新元数据并在每个感兴趣的事件处检查竞争来以流式方式检测，如通用概述算法1所示。大多数已知的用于动态检测数据竞争的算法6,8,11,19都遵循这个通用框架，仅在算法维护的数据或函数initmetadata和checkraceandupdatemetadata的实现细节上有所不同。 算法1：动态数据竞争检测的概述 输入：跟踪σ 1. initmetadata() 2. 对于σ中的每个事件e，执行checkraceandupdatemetadata(e) 2.3 属性测试。属性测试器10是一种在承诺设置下解决决策问题的算法。另一种理解方式是，它“近似”地解决决策问题。它通常是一个随机算法。对于由语言l表征的决策问题，属性测试器是一种提供以下保证的算法：对于输入x ∈ l，算法以高概率回答“是”，而对于输入x与l中的任何元素“相距甚远”的情况，它以高概率回答“否”。因此，要精确定义属性测试器，我们需要确定输入空间中元素之间的距离概念。最常用的距离度量是汉明距离。 定义2（汉明距离）。对于字母表σ上的序列u, v ∈ σ?，u和v之间的汉明距离（dh (u, v)）定义如下： dh(u,v)={|{i|u[i]≠v[i]}| if |u|=|v|\ ∞ otherwise\ 对于u ∈ σ?和l ? σ?，dh(u, l)=inf_{v∈L} dh(u, v)。 定义了输入与语言之间的距离概念后，我们可以精确定义属性测试器是什么。在本文中，我们只考虑单边测试器，因此我们将定义专门针对这种情况。 定义3（属性测试器）。对于问题l的（单边）(?, δ)属性测试器是一个随机算法a，它在任何输入x上的输出满足以下属性： (a) 如果x ∈ l，a(x)以1的概率回答“是”。 (b) 如果dh(x, l) ≥ ?|x|，a(x)以至少1?δ的概率回答“否”。 关于定义3的一些观察：对于不在l中但“接近”l的输入x（即dh(x, l) < ?|x|），属性测试器可能会回答“是”或“否”，而不违反其义务。从这个意义上说，属性测试器是决策问题的一个近似算法。其次，由于我们正在考虑单边测试器，我们可以根据测试器的响应得出关于输入的以下结论：如果a(x)=“否”，那么我们可以得出x ? l的结论。另一方面，如果a(x)=“是”，那么我们不能确定x是否属于L。 3. 数据竞争检测的属性测试器。我们的随机算法rpt用于动态数据竞争检测，简单直接（也见图1）： 1. 从观察到的跟踪σ中均匀随机抽取r个长度为k的子跟踪。 2. 如果任何抽样的子跟踪存在数据竞争，则声明σ存在数据竞争。 3. 如果没有抽样的子跟踪存在数据竞争，则声明σ没有数据竞争。 为了完成对rpt的描述，我们需要回答以下问题：算法应该抽取多少个子跟踪（参数r）？抽样的子跟踪的长度（参数k）应该是多少？显然，这些参数的设置是为了确保结果算法是一个数据竞争检测的属性测试器。正确性的论证是算法本身最关键的部分，也是技术上最具挑战性的部分。我们在本节中的描述将使用诸如“许多”、“非常远”、“短”、“长”等模糊术语。这些术语将在我们的正式定理和引理陈述中通过参数来精确定义，但我们在文本中使用这些非正式术语有助于阐明正确性论证背后的主要思想，而不会陷入技术细节中。 在开始概述正确性论证之前，让我们先检查我们的算法模板并确定一些基本事实。首先，请注意，无论我们为参数r和k设置什么值，算法都是可靠的——如果算法声明一个跟踪σ存在数据竞争，那么它确实存在数据竞争。这是因为hb竞争的“局部性”属性在命题1中有所说明——即σ中的事件e1和e2是否属于hb竞争仅取决于以e1开始并以e2结束的σ中的事件。这意味着一个没有数据竞争的执行σ将以1的概率被正确声明。因此，为了建立正确性，我们的任务是找到r和k的值，使得在远离任何没有数据竞争的执行的情况下，算法有很高的概率发现一个存在hb竞争的子跟踪。其次，为了检查一个抽样的子跟踪是否存在数据竞争，我们可以使用任何算法来检测hb竞争。在我们的实现中，我们使用fasttrack，但也可以使用任何hb竞争检测算法，特别是当发现更快的算法时，运行时间会更好。 3.1 正确性论证。现在让我们概述一下我们的正确性论证。它严重依赖于我们的主要定理（定理1），该定理指出，如果输入跟踪σ与任何没有数据竞争的执行（就汉明距离而言）相距甚远，那么存在许多包含hb竞争的短子跟踪。在这个定理中，表征“短”的标准将是k的值。请注意，如果定理1保证存在许多包含竞争的k长度子跟踪，那么分析一个随机选择的k长度子跟踪可以保证我们以非零的概率发现竞争。因此，如果我们多次重复这个实验（即r次），我们可以确保以高概率发现竞争。这里，样本数量r的选择基于单个k长度子跟踪存在竞争的概率。通过首先观察到远离任何没有数据竞争执行的跟踪有许多不相交的子跟踪包含hb竞争，从而证明了主要定理（定理1）。这证明了如果σ与任何没有数据竞争的执行相距甚远，则它有许多不相交的子跟踪。这是引理2的内容，其证明如下：我们展示了如果σ很少有不相交的竞争子跟踪，那么可以通过改变很少的事件将σ转换为没有数据竞争的执行。由于我们知道σ相距甚远，我们可以得出它有许多不相交的竞争。最后，为了证明很少不相交的竞争子跟踪意味着接近没有数据竞争的执行，我们需要引理1，该引理证明了任何两个没有数据竞争的子跟踪σ1和σ2可以通过在σ1和σ2之间插入一个短子跟踪μ来组合成一个更大的没有数据竞争的子跟踪。 在我们概述正确性论证之前，让我们先看一下我们的算法模板并确定一些基本事实。首先，请注意，无论我们为参数r和k设置什么值，算法都是可靠的——如果算法声明一个跟踪σ存在数据竞争，那么它确实存在数据竞争。这是因为hb竞争的“局部性”属性在命题1中有所说明——即σ中的事件e1和e2是否属于hb竞争仅取决于以e1开始并以e2结束的σ中的事件。这意味着没有数据竞争的执行σ将以1的概率被正确声明。因此，为了建立正确性，我们的任务是找到r和k的值，使得在远离任何没有数据竞争的执行的情况下，算法有很高的概率发现一个包含hb竞争的子跟踪。其次，为了检查一个抽样的子跟踪是否存在数据竞争，我们可以使用任何算法来检测hb竞争。在我们的实现中，我们使用fasttrack，但也可以使用任何hb竞争检测算法，特别是当发现更快的算法时，运行时间会更好。 3.1 正确性论证。现在让我们概述一下我们的正确性论证。它严重依赖于我们的主要定理（定理1），该定理指出如果输入跟踪σ与任何没有数据竞争的执行（就汉明距离而言）相距甚远，那么存在许多包含hb竞争的短子跟踪。在这个定理中，表征“短”的标准将是k的值。请注意，如果定理1保证存在许多包含竞争的k长度子跟踪，那么分析一个随机选择的k长度子跟踪可以保证我们以非零的概率发现竞争。因此，如果我们重复这个实验几次（即r次），我们可以确保以高概率发现竞争。这里，样本数量r的选择是基于单个k长度子跟踪存在竞争的概率。主要定理（定理1）本身是通过首先观察到远离任何没有数据竞争执行的跟踪有许多（不一定是短的）不相交的子跟踪包含hb竞争来建立的。这是引理2的内容，其证明如下：我们展示了如果σ很少有不相交的竞争子跟踪，那么可以通过改变很少的事件将σ转换为没有数据竞争的执行。最后，为了证明很少不相交的竞争子跟踪意味着接近没有数据竞争的执行，我们需要引理1，该引理证明了任何两个没有数据竞争的子跟踪σ1和σ2可以通过在σ1和σ2之间插入一个短子跟踪μ来组合成一个更大的没有数据竞争的子跟踪。 在我们提供了论证的概述之后，我们准备介绍一些关键见解。我们首先从一个技术性引理开始，表明对于任何格式良好的子跟踪σ1和σ2，存在一个短子跟踪μ，使得连接的子跟踪σ1 μσ2是格式良好的，并且σ1中的每个事件在hb顺序上都位于σ2中的每个事件之前。这将在后面用来证明在远离没有数据竞争的执行集合的跟踪中，存在许多包含hb竞争的不相交子跟踪。 引理1。设σ1和σ2是在线程t上的格式良好子跟踪。设h是σ1结束和σ2开始时持有的锁的数量的上限。存在一个子跟踪μ(σ1, σ2)，使得|μ(σ1, σ2)| ≤ 4|t | + 2h，并且σ=σ1 μ(σ1 , σ2)σ2是格式良好的。此外，对于任何事件e1 ∈ eventsσ1和e2 ∈><σhbe2。

引理1是使用一个没有数据访问事件的子跟踪μ(σ1, σ2)来证明的。因此，如果σ1和σ2没有数据竞争，那么σ1μ(σ1, σ2)σ2也没有数据竞争。这一观察被充分利用。

在本节的其余部分，让我们固定一组线程t、一组锁l和一组内存位置m。设rf是所有在t、l和m上格式良好且没有数据竞争的跟踪的集合。 引理1是使用一个没有数据访问事件的子跟踪μ(σ1, σ2)来证明的。因此，如果σ1和σ2没有数据竞争，那么σ1μ(σ1, σ2)σ2也没有数据竞争。这一观察被充分利用。>
引理1是使用一个没有数据访问事件的子跟踪μ(σ1, σ2)来证明的。因此，如果σ1和σ2没有数据竞争，那么σ1μ(σ1, σ2)σ2也没有数据竞争。这一观察被充分利用。

在本节的其余部分，让我们固定一组线程t、一组锁l和一组内存位置m。设rf是所有在t、l和m上格式良好且没有数据竞争的跟踪的集合。>也就是说，RF = {σ 是无竞争的 | Threadsσ ? T, Locksσ ? L, Memσ ? M}。注意，对于任何轨迹 σ，dH (σ, RF) ≤ |σ|。这是因为我们总是可以选择一个长度为 |σ| 的 η ∈ RF，例如确保 η 只包含由单个线程执行的事件，或者 η 不包含写事件等。假设 h 是轨迹中任何时刻持有的锁的数量的上限；在最糟糕的情况下 h = |L|，但通常 h 远小于 |L|。最后，让我们固定 m = 4|T| + 2h。

引理 1 允许我们证明，如果一个轨迹 σ 与集合 RF 的距离非常远（用参数 ? 来衡量），那么存在许多不相交的子轨迹 σ，这些子轨迹包含一对处于 HB-竞争中的事件。换句话说，如果 σ 与任何无竞争的轨迹相距很远，那么就有许多不相交的见证者可以证明 σ 存在竞争。

引理 2：设 σ 是一个长度为 n 的轨迹，且 dH(σ, RF) ≥ ?n。存在一个整数 u ≥ εnm 以及一个递增的索引序列 0 = i1 < i2 < i12 <... < i1u < i2u ≤ n，其长度为 2 · u，使得每个子轨迹 σi1j, i2j（1 ≤ j ≤ u）都包含一个 HB-竞争。

从引理 1 证明引理 2 的关键见解是，任何具有少于 u 个短竞争的轨迹都可以通过修改最多 u * m 个事件来转换为无竞争的轨迹。具体来说，正如引理 1 所建立的，对于每个短竞争，我们可以在上一个竞争的第二个事件和下一个竞争的第一个事件之间的段内修改最多 m 个事件，从而消除该区间内的所有竞争（参见图 2 以获取说明，更多细节请参阅 Thokair 等人的工作）。引理 2 保证了存在许多不相交的、有竞争的子轨迹。然而，这本身还不足以得到一个高效的数据竞争检测属性测试器。特别是，引理 2 并没有对其识别的有竞争子轨迹的长度提供任何限制。如果我们不加强引理 2，我们可以在模板算法中对样本长度 k 的唯一限制就是 |σ|，这会使我们的属性测试器不比确定性的竞争检测器更高效。我们的主要定理接下来将证明，对于足够长的轨迹，当轨迹 σ 与任何无竞争的轨迹相距很远时，存在许多长度较短的竞争子轨迹。证明使用了引理 2。这将使我们能够限制 k 并得到很好的渐进式界限。

图 2. 引理 2 的示意图。顶部的执行包含竞争，其中填充的（黑色）圆圈表示参与竞争的事件，红色框标记了可以修改以获得底部所示无竞争执行的长度为 m 的子轨迹。

定理 1：设 σ 是一个长度为 n 的轨迹，且 dH(σ, RF) ≥ ?n。此外，设 n ≥ (12m)/?。那么至少存在 2(?n)/15 个长度为 4m/? 的 σ 的子轨迹，这些子轨迹包含一个 HB-竞争。

定理 1 有助于完成我们的算法 RPT 的描述。我们的属性测试器将选择长度为 4m/? 的子轨迹，这是定理 1 中使用的参数。由于每个起始位置都标识了这样的子轨迹，因此存在 n 个这样的子轨迹。根据定理 1，当 σ 与 RF 的距离为 ? 时，随机子轨迹的长度为 k = 4m/? 且存在数据竞争的概率至少为 2?/15。如果我们选择 r = 15 ln(1/δ)2ε，那么我们不检测到数据竞争的概率最多为 (1-2?/15)r < e^(-ln(1/δ) = δ^3。

让我们通过介绍我们的属性测试器（算法 2）的伪代码来结束这一节。回想一下，该算法从输入 σ 中采样 r = 15 ln(1/δ)2ε 个长度为 k = 4m/? 的子轨迹，并检查这些采样的子轨迹中是否存在 HB-竞争。注意，采样长度为 k 的子轨迹等同于选择一个起始索引 i，并理解采样的子轨迹是 σ[i, i + k]。因此，采样 r 个子轨迹等同于选择 r 个起始索引（第 6 行）。考虑两个重叠的子轨迹 σ[i1, i1 + k] 和 σ[i2, i2 + k]。也就是说，wlog 表示 i1 < i2 < i1 + k。根据 HB 部分序的定义，如果子轨迹 σ[i1, i2 + k] 是无竞争的，那么 σ[i1, i1 + k] 和 σ[i2, i2 + k] 都是无竞争的。因此，我们可以合并重叠的采样子轨迹，而不影响我们检测竞争的能力。因此，在第 7 行，我们合并重叠的子轨迹以获得更少的采样子轨迹集，但采样子轨迹可能比 k 更长。这一步减少了我们的算法将处理的总事件数。在这个初始预处理步骤之后，算法按以下方式继续进行。当一个事件是采样子轨迹的开始时，元数据将重置，以便重新开始竞争检测。此外，每当一个事件在我们的采样子轨迹中时，我们会调用 function checkRaceAndUpdateMetadata，该函数会根据事件执行的操作调用相应的底层竞争检测器处理程序。当一个事件不在我们的任何采样子轨迹中时，不会进行任何检查和元数据更新。

算法 2：用于检测 HB-竞争的属性测试器
参数：?, δ ∈ [0, 1]
输入：轨迹 σ
1. InitMetadata()
2. m ← 4|T| + 2h; k ← 4m/?; r ← 15 ln(1/δ)
3. 如果 |σ| < 12m/?，则
4. 在 σ 上运行 Algorithm 1
5. 否则
6. I ← 从 [0, n – k] 中采样 r 个索引
7. S ← 合并子轨迹 ({σ[i, i + k]}i∈I
8. 对于σ中的每个事件 e，执行
9. 如果 e 是 S 中某个子轨迹的开始，则
10. 重置Metadata()
11. 如果 e 在 S 中的某个子轨迹中，则
12. 检查RaceAndUpdateMetadata(e)

我们注意到 RPT 可以很容易地扩展到诸如原子/易失性访问之类的同步原语，以及诸如 fork-join、wait-notify 或 barriers 等同步原语。这是因为对于这些同步原语，“局部性”属性（命题 1）成立，并且经典的红灯快车算法可以很容易地扩展到这些同步原语（Flanagan 和 Freund 也有类似的观察）。

4. 实验评估

我们通过实现 RPT 并将其与常用的确定性竞争检测算法 FastTrack 以及基于采样的最新竞争检测算法 Pacer 进行比较，来评估我们属性测试器的实际可行性。这些工具各有不同的理念，并解决略有不同的问题——FastTrack 处理轨迹中的每个事件并报告所有 HB-竞争；Pacer 承诺每个 HB-竞争都有相等的、非零的概率被报告；相比之下，RPT 被设计为仅进行足够的采样，以确保当轨迹与无竞争状态相距很远时，我们可以数学上证明至少会报告一次竞争。它们的比较并不是同类比较。因此，本节中的实验并不是为了说明一个工具比另一个工具更好。它们只是为了帮助人们了解 RPT 在实际程序上的可能性能：运行时间是否如理论所承诺的那样低？它多久报告一次竞争？它只在有许多竞争时才工作吗？实际上会出现哪些类型的竞争，是否有某些程序 RPT 总是会失败？如果我们只报告 RPT 的性能，就很难评估其合理性；因此，我们同时报告 FastTrack 和 Pacer 的性能作为基准。

我们的评估使用了来自先前关于竞争检测的研究的基准程序，涵盖了多种编程模型和应用领域。该集合包括广泛使用的 Java 套件，如 DaCapo 和 Java Grande Forum；微基准测试，如 DataRaceBench 和 NAS Parallel Benchmarks；以及 HPC 代理应用程序。我们使用 RoadRunner 收集了 Java 基准的运行轨迹，并使用 ThreadSanitizer 收集了 C/OpenMP 基准的轨迹，在过滤掉少于 1M 事件的轨迹后得到了 149 条轨迹。每条轨迹都使用了先前工作中推荐的参数设置和运行配置，用三种算法进行了分析。对于 RPT，我们选择了组合（? = 0.01, δ = 0.1）。

我们的实验研究包括比这里呈现的更广泛的结果。对于本文，我们专注于一些代表性的实验实例，以捕捉 RPT 的主要性能趋势。完整的评估出现在扩展版本中。

4.1 运行时间

我们对 FastTrack、Pacer 和 RPT 的实现都分析了轨迹日志，并通过简单测量每种算法分析每条轨迹所需的时间来衡量竞争检测的运行时间。对于每种算法和每条轨迹，我们分别测量了 50 次试验（对于 Pacer 和 RPT）和 20 次试验（对于 FastTrack）的平均运行时间。为了更清楚地展示大型基准测试的结果，我们按轨迹长度对这些轨迹进行了分组。对于每个组，我们计算了 FastTrack、Pacer 和 RPT 的加权平均运行时间和加速比（相对于 FastTrack），其中轨迹的权重是其长度的倒数。不出所料，RPT 的运行时间很低；实际上，对于较长的轨迹，它的运行时间最低。正如预期的那样，Pacer 的速度也明显快于 FastTrack。随着轨迹长度的增加，RPT 相对于 Pacer 和 FastTrack 的竞争优势变得更加显著，而 RPT 的运行时间增长较快。

图 3. 权重平均运行时间（顶部）作为轨迹长度（范围）的函数，以及相对于 FastTrack 的加权平均加速比（底部）作为轨迹长度（范围）的函数。

4.2 恒定开销

回想一下，RPT 采样的事件数量是 ?(m)，并且与轨迹长度无关；一个自然的问题是这是否在 RPT 的运行时间中得到了体现。我们研究了从我们的基准测试中收集的两组轨迹来更好地理解这一点。第一组包括所有 m = 70 的轨迹（总共 12 条），第二组包括所有 m = 226 的轨迹（总共 28 条）。每组轨迹的长度各不相同，以帮助理解算法在轨迹长度增加时的开销。对于这两组轨迹，我们在图 4 中绘制了 FastTrack、Pacer 和 RPT 处理元数据所需的开销。这排除了基于采样的算法生成随机数所需的时间。由于 FastTrack 对所有事件都执行元数据操作，我们报告了它所花费的总时间。对于 RPT 和 Pacer，我们只报告了处理所选事件所需的元数据的时间。我们看到，正如预期的那样，RPT 在分析采样部分轨迹时花费的时间是恒定的。另一方面，Pacer 和 FastTrack 随着轨迹长度的增加而花费的时间也在增加。

图 4. 当参数 m 为常数时，更新元数据所需的时间作为轨迹长度的函数。

4.3 精确度

我们想要评估 RPT 在暴露数据竞争方面的表现。由于 RPT 只采样固定数量的事件，因此它必然不会报告每一个动态警告。同时，RPT 的 (?, δ) 保证确保每当观察到的执行足够“有竞争”时，它将以高概率报告一次竞争。在下文中，我们报告了 RPT 的精确度，并将其与 Pacer 的精确度进行了比较。

图 5 显示了 Pacer 和 RPT 检测到至少一次竞争的概率；我们称这就是每个基准的成功率：
成功率 = 至少有 1 个警告的运行次数 / 总运行次数

回想一下，由于 RPT 是一个属性测试器，它只有在分析的轨迹与无竞争执行轨迹集合在汉明距离上相距很远时，才能保证高概率地检测到竞争。这对一条轨迹来说很难测量。因此，我们使用一个代理来近似汉明距离，我们称之为轨迹的竞争性：
竞争性 = FastTrack 报告的警告数量的平均值 / 轨迹长度

轨迹 σ 的竞争性是 σ 与任何无竞争轨迹的汉明距离的上限。换句话说，如果一个执行跟踪（trace）的竞争性（raciness）较低，那么就汉明距离（Hamming distance）而言，它几乎可以被认为是没有竞争性的。然而，这可能是一种低估。我们预计，随着跟踪的竞争性增加，RPT（一种用于检测数据竞争的算法）的成功率也会提高。在图5中，我们根据跟踪的竞争性对它们进行分组，并汇总每个组的成功率；然后，我们根据这些成功率来评估RPT和Pacer（另一种算法）。可以看出，在大多数组中，RPT检测到竞争情况的概率与Pacer的检测概率相当，或者甚至更好。总体而言，我们得出结论：即使跟踪中的警告数量很少（大约是事件数量的10^-7倍），RPT也能以非常高的概率成功识别出存在竞争的情况。回想一下，在我们的实验中，我们运行RPT时使用的?值是0.01，这远大于10^-7。

在实践中，当程序包含数据竞争时，一个对修复错误特别有用的特征是导致竞争性内存访问的具体源代码。由于循环和重复的函数调用，一个包含许多竞争性对的执行跟踪可能只会揭示出少数几个明确的竞争性源代码位置。因此，我们还报告了每个工具识别出的参与竞争的源代码位置的数量，并像之前一样，根据跟踪长度和m对其进行分组，如图6所示。我们观察到，Pacer和RPT都报告了相当多的源代码位置。这显示了基于抽样的方法的有效性。值得注意的是，对于具有更高m值（即更多线程）的跟踪，RPT几乎可以报告基线确定性算法FastTrack标记为竞争性的所有源代码位置。

图6. 源代码位置的数量（按照FastTrack报告的数量进行归一化）作为跟踪长度和m的函数。

4.5 竞争性对之间的距离。RPT只采样短子跟踪，并且只能报告属于同一采样子跟踪中的事件对之间的竞争情况。因此，RPT无法报告相隔较远的事件对之间的竞争情况。跟踪中竞争情况相隔的事件数量较少的情况有多常见呢？如果我们说，在跟踪σ中的竞争对(e1, e2)是“短的”，那么意味着e1和e2之间的距离小于RPT采样的子跟踪的长度。我们根据短竞争数量占总竞争数量的比例对基准测试跟踪进行分组，并将其作为直方图绘制在图7中。我们观察到，在52个跟踪中，短竞争的比例不到25%，而在96个跟踪中（大约是我们测试套件的三分之二），短竞争的比例至少为40%。也就是说，在实践中，短竞争的情况相当常见。

接下来，我们研究了RPT在短竞争数量非常少的跟踪上的表现，即少于5%的跟踪。这样的跟踪有29个（大约是我们测试套件的五分之一）。令人惊讶的是，即使在这种情况下，RPT的成功率也非常高。平均而言，在这些跟踪中，RPT至少有84%的时间能够检测到一次竞争。在29个跟踪中的21个跟踪中，RPT100%的时间内都能检测到竞争，在另外25个跟踪中，RPT至少有一半的时间内能检测到竞争。在其中一些例子中，短竞争的比例不到0.01%。在剩下的四个例子中，有一个跟踪RPT从未检测到竞争，在另外三个例子中，短竞争的比例为0.003–0.02%，而RPT在这些跟踪中大约有20–25%的时间内能检测到竞争。特别是在那个RPT从未检测到竞争的例子中，没有短竞争情况，Pacer在其对该跟踪的所有运行中也没有检测到任何竞争。

5. 超出短竞争的检测范围

目前，RPT的竞争检测能力仅限于短竞争：它只能检测那些在同一子跟踪中发生的竞争，除非子跟踪重叠，否则无法捕获跨越多个子跟踪的竞争。这种设计选择的原因是，检测任意长度的竞争需要采样两次竞争事件之间的每次锁访问，从而违背了常数开销的保证。实际上，我们的实验表明，我们测试基准中的许多竞争都是短竞争，这使得当前的设计对于许多工作负载都是有效的。然而，在某些情况下，该算法可能会错过大部分竞争，特别是当大多数竞争都是长竞争时。

我们指出，RPT可以与其他用于检测 HB-竞争（HB-races）的算法结合使用。当与FastTrack结合使用时，由于RPT采样了?(m)个事件，而FastTrack在每个事件时执行O(T) 的元数据更新，因此会产生一个常数开销。我们最近的工作引入了对RPT采样策略的改进，使其能够在不牺牲概率保证的情况下检测跨采样子跟踪的竞争。关键思想是，如果采样了给定执行跟踪中的S次内存访问事件以及所有同步事件，那么FastTrack算法可以被修改为只更新S|T | 次元数据，从而能够可靠地检测到所有采样的内存访问事件之间的竞争。通过使用更高阶的元数据和辅助数据结构，改进后的算法避免了大多数同步事件的O(T) 元数据更新开销，实现了O(ST^2) 的开销。需要注意的是，RPT采样了?(m)次内存访问事件，这意味着可以以?(mT^2) 的开销可靠地检测到所有跨采样事件的竞争，同时保持了RPT的常数开销保证。尽管我们还没有将这一改进集成到我们的实现中，但理论结果表明这种扩展是可行的，并将扩大RPT对它们事件相距较远的数据竞争的适用范围。因此，整合这一改进为未来的研究提供了自然的方向。

首次发表

本文的原始版本题为“使用O(1)次采样进行动态竞争检测”，发表于2023年1月的ACM编程语言会议论文集中。

张敏健（Minjian Zhang），新加坡南洋理工大学（进行这项研究时任职于美国伊利诺伊大学厄巴纳-香槟分校）。
Mosaad Al Thokair，沙特阿美公司（Saudi Aramco），沙特阿拉伯。
Umang Mathur，新加坡国立大学（National University of Singapore）。
Mahesh Viswanathan，美国伊利诺伊大学厄巴纳-香槟分校（University of Illinois at Urbana-Champaign）。