技术视角：迈向实用并发错误检测的飞跃

《Communications of the ACM》：Technical Perspective: A Leap Toward Practical Concurrency Bug Hunting

　　

人们常说并发 bug 就像蟑螂：它们藏在黑暗中，零星出现，而且 notoriously 难以根除。这个 bug 动物园中最占优势的种类之一是数据竞争，当两个线程在没有适当同步的情况下访问同一内存位置时发生。这些 bug 很隐蔽，发生频率低，但往往具有灾难性。但检测它们，尤其是通过实际执行分析进行动态检测，曾被认为代价过高——直到现在。

数据竞争是并发程序中最常见的 bug 来源之一；它们难以捉摸，且已知会导致严重后果。20 世纪 80 年代中期的一个著名事件说明了数据竞争的危险。Therac-25 是一台放疗机，其控制软件包含一个数据竞争，导致直接向患者输送巨大、无防护的辐射剂量。悲剧的是，它导致了至少六名已知死亡和几起严重受伤。

自 C++11 以来，数据竞争在规范良好的 C++ 程序中是不被允许的。存在数据竞争的程序会导致未定义行为。这意味着你，程序员，负责确保对所有共享数据的访问都是无数据竞争的。

我们如何发现数据竞争?

数据竞争检测器是用于识别数据竞争的工具或技术。它们通常分为两大类。静态检测器在不运行程序的情况下分析代码，通过检查程序的抽象控制流和内存访问模型。优势在于检测发生在提前，无运行时开销。但静态数据竞争检测器可能不准确，并且由于对复杂行为的保守分析可能会产生虚假警告。

动态数据竞争检测器在给定执行中寻找冲突的内存访问。它们可以检测到该特定运行中的所有数据竞争，以及在类似执行中可能以不同顺序出现的未同步操作。虽然这种方法不能捕获所有数据竞争，因为它只观察所有可能线程交错的一个子集，但它报告的竞争总是真实的，并且发生在真实、有趣的执行中。动态数据竞争检测的圣杯是一种结合准确性、高覆盖率和最小性能开销的工具：轻量到足以在生产环境中运行而不会明显变慢，但又可靠到每当发生数据竞争时总是发出警告。

为什么这篇论文令人兴奋

配套论文“动态竞争检测与 O(1) 样本”提出了第一个亚线性时间（在执行追踪长度方面）的动态数据竞争检测器：一种基于采样的算法称为 race property tester (RPT)，它通过检查恒定数量的样本（独立于程序或执行大小）来检测大型程序中的数据竞争。

基于采样是什么意思？基于采样的检测器用准确性换取性能。检测器不分析每一个事件，而是对执行的一部分进行采样，希望在这些样本中捕获竞争。最初由 Pacer 检测器提出，这种方法已被证明是提高性能而不显著降低覆盖率的 effective 方法。配套论文酷的地方在于它既提供了保证的最坏情况亚线性执行时间，又提供了覆盖率保证，基于 属性测试 的理论框架。

属性测试是一个概念，用于通过检查对象的很小一部分随机样本来确定给定对象是否具有某种属性，或者远离具有该属性。如果输入满足属性 P，属性测试器总是接受它。如果输入远离满足 P，测试器以高概率拒绝它。如果输入介于两者之间（即“接近”满足 P），测试器可以任意接受或拒绝。应用于数据竞争检测，这意味着如果程序无数据竞争，检测器将始终将其标记为安全。但如果程序足够远离无竞争状态（即可能产生竞争），检测器将以高概率捕获它。

RPT 不试图找到所有竞争。相反，它回答一个二元问题：这个执行可能包含竞争吗？如果是，你得到一个可靠的警告（无误报）。如果不是，你获得信心，认为该追踪接近无竞争状态，并基于精心选择的参数具有严格保证。

它效果如何?

出奇地好。作者实现了 RPT 并将其与竞争检测器 FastTrack 和 Pacer 进行广泛基准测试比较。RPT consistently 达到最低的运行时间，尤其是随着追踪长度增长。此外，RPT 保持高检测率，即使在竞争较少的追踪上。即使采样最少，它也显示出在识别易竞争的内存位置和源代码行方面 consistently 成功。

你为什么要关心?

如果你写过并发代码，你知道调试数据竞争的痛苦。RPT 提供了一种方法，从理论上将动态数据竞争检测从重型发布前测试转变为轻量级持续监控，甚至在生产环境中。从更广阔的角度来看，配套论文还展示了将深奥理论工具（属性测试）应用于高度实用系统问题的 compelling 例子。这是一座值得更多关注的桥梁。至少，这篇论文会让你对不同地思考分析程序执行意味着什么，以及你真正需要观察多少才能知道出了问题。

Erez Petrank ([e-mail]) 是计算机科学与以色列理工学院（位于以色列海法）的 Andrew and Erna Viterbi 讲席教授。