多线程程序数据竞争检测和验证方法研究综述

禹振　杨振　苏小红　王甜甜

摘要：随着软件规模的日益增长，多线程并发程序带来的缺陷也很快蔓延开来。数据竞争作为多线程并发程序中常见的问题，经常会导致程序不能正常运行，或更为严重地导致程序直接崩溃。数据竞争产生的条件往往都比较隐蔽和苛刻，不仅需要特定的输入，而且还需要特定的线程执行交错。因此，数据竞争很難被检测出来。本文介绍了多线程数据竞争检测和验证相关的研究现状，并对已有的数据竞争检测和验证方法在检测能力以及检测效率等方面做出比较、分析以及归纳。同时，对未来数据竞争检测和验证相关的研究方向进行了展望。

关键词：多线程；数据竞争检测；数据竞争验证

0引言

在这个多核硬件的时代，充分利用硬件带来的优势，并发程序也大受欢迎并已进入广泛应用中。时下，常见的Microsoft Windows或是Linux Ubuntu操作系统，或是Google Chrome网页浏览器等均采用了多线程并发技术。比较流行的编程语言，如C/C++，Java和Python等也对并发程序有着良好的支持。

虽然多线程并发技术为人们提供了使用上的遍历以及优质畅快的用户体验和软件交互，但是编写多线程并发程序也是令许多开发者苦恼的事。在多线程并发程序中，由于对共享内存空间访问的隐蔽性以及并发线程执行调度的随机性，导致并发线程之间产生一些不确定的相互作用和影响。这些都给并发程序的分析带来了现实严峻的挑战，而且很容易导致多线程并发程序在设计上存在一些缺陷。这些缺陷往往较难调试和诊断，并且可能最终导致并发程序在运行的过程中出现崩溃，从而造成严重的后果。

在并发程序的安全性缺陷中，主要包括：数据竞争、原子性违背、顺序违背和死锁。具体地，数据竞争是指对同一个共享内存空间，存在若干并发访问，并且至少有一个是写访问。原子性违背是指原来必须原子性执行的指令序列，在并发交错的干扰下，其执行的效果不与任何原子性指令序列的执行效果相同，各个线程需保持的一致性遭到其他并发线程写操作破坏。顺序违背指的是一指令（组）没有按照预期执行，总是在另一（组）指令之前或是之后执行。死锁指的是某个线程集合中每一个线程都在等待该集合中的另一个线程释放占有的互斥性资源，从而导致整体陷入循环等待状态。研究分析可知，数据竞争在上述常见的4种并发缺陷中占的比例较大，并且大部分是导致原子性违背和顺序违背的根源。在图1a）原子性违背实例中，L2和L3，以及L1和L3中对共享索引变量buf_index的访问分别构成数据竞争：而在图1b）顺序违背实例中，L1和L2对共享变量mThread的访问构成数据竞争。因此，如何准确并且有效地检测多线程并发程序中的数据竞争缺陷即已成为颇具研究价值的重要课题。

目前已经提出的数据竞争检测和验证方法在不同程度上呈现有一定的不足。探讨解析可得结论如下：

静态检测方法只需要分析程序源码，但是缺少程序运行时的信息，导致报告的数据竞争大部分都是误检。动态检测方法监视程序在执行过程中的行为，收集必要的信息来判断哪些访问操作构成数据竞争，但是受限于线程执行交错的不确定性以及收集到信息的不完整性，该方法依然会生成很多误检和漏检。动静结合的方法虽然能够弥补各自方法的一些缺陷，但是在源程序运行过程中引入了大量的性能开销，同时并没有真正显著提升数据竞争检测的精度。数据竞争验证方法虽然能够精准地找到数据竞争，但是该方法同时会造成大量的漏检并且验证效率也比较低。

本文在综合论述以往研究的基础上，对已经存在的数据竞争检测和验证方法进行了分析和比较，同时归纳提炼了这些方法的优缺点。最后，讨论给出了后续对于数据竞争检测和验证方法在未来研究的重点展望。

1数据竞争检测和验证方法的研究

迄今为止，已经研究提出了很多数据竞争检测和验证的方法，主要分为3类：静态数据竞争检测方法，动态数据竞争检测方法以及动静结合的数据竞争验证方法。下面针对各类研究成果给出完整论述和设计解析。

1.1静态数据竞争检测

静态数据竞争检测主要是进行锁集分析，从而检测数据竞争。常用的静态数据竞争检测工具包括Warlock、RacerX、RELAY和Locksmith。其中，RacerX利用流敏感和过程间分析检测数据竞争和死锁；Locksmith首先使用标签流约束和抽象控制流图约束信息来进行锁集分析，然后使用标签流约束、抽象控制流图约束和上下文敏感约束展开共享变量的分析，最后结合线性分析，检测出数据竞争；RELAY通过控制流图和程序调用图，采用自底向上的分析方式，首先进行过程内锁集分析并缓存在函数标签中，然后开启过程间锁集分析，等到所有的线程相关的函数全部分析完毕，再判断相关的共享变量是否产生数据竞争。RELAY由于其扩展性堪称优良，能够应用在百万级别代码量的程序上，因此，在实际使用过程中获得了高度认可与广泛接受。

尽管静态数据竞争检测只需要分析程序源码、监测效率高并且基本不会有漏报，但由于其忽略了程序执行过程中的一些happens-before关系，因此静态数据竞争检测方法得到的绝大部分都不是真正的数据竞争。

1.2动态数据竞争检测

动态数据竞争检测算法主要分为基于lockset的算法、基于happens-before关系的算法以及两者混合的hybrid算法三种。下面即顺次概述各类方法的设计过程实现。

Savage等人提出基于lockset的动态数据竞争检测方法Eraser，该方法在程序执行过程中维护每个线程当前的锁信息，同时更新共享变量持有的锁信息，当共享变量不再受到锁保护的时候，报告数据竞争。

Von和Elmas等在Eraser的基础上对基于lockset算法的动态数据竞争检测方法进行了精细和扩展，使得能够更加精确和有效地检测对象级别的数据竞争。

Netzer和Perkovic等基于Lamport的happens-before关系提出了使用逻辑时钟来动态地检测数据竞争。Happens-before关系是在多线程并发程序执行的所有事件上的一种偏序关系。该关系要求同一个线程内部按照时序逻辑顺序执行，而在线程间程序的执行依赖于同步机制。一旦对一个共享内存空间的访问违背了happens-before关系，那么就会产生数据竞争。

Pozniansky、Flanagan、Cai以及Ha等相继提出了改进后的基于happens-before关系的动态数据竞争检测方法。其中，Djit算法使用vector-clock的形式记录线程和共享内存空间访问的逻辑时钟，同时每一个时间帧中只记录第一个对共享内存空间的读/写访问。FastTrack认为在一个没有数据竞争故障的程序执行过程中，对共享内存空间的写访问是有序的，而只有多个线程对同一共享内存空间进行读访问才可能是并发进行的。因此对于写访问可以采用轻量级的epoch形式的逻辑时钟，而只有并发的读访问才会依然采用vector-clock形式的逻辑时钟。Loft在FastTrack的基础上提出一些场景来进一步减少基于vector-clock的赋值和比较操作。iFr对FastTrack实施特别简化，不再需要遍历vector-clock的每一项进行分析，而只是关注left-most和right-most两项，从而将读写访问操作的数据竞争检测复杂度降低到了O（1）。

Poznianskv、Jannesari、Serebryan、Nethercote、Xie和Yu等分别提出了基于hvbrid的动态数据竞争检测方法。MultiRace首先利用改进的lockset算法找到可疑的数据竞争，然后利用Diit+算法集中检测可行的语句对是否真正是并发的。Helgrind+将线程顺序执行的操作序列约束在一个segment中，segment能够反映线程和线程的逻辑时钟。Helgrind+则先SHI进行happens-before关系的分析找到所有潜在并发的segment，而后利用lockset算法验证共享内存空间的访问是否可由公共的锁提供保护。ThreadSanitizer同样使用segment来表示一个线程中连续执行的内存访问事件（不包括同步事件）。Segment中第一个事件包含当前segment中所有事件的上下文信息，同时维护2个锁集合分别表示保护读/写持有的锁集合LS和LS ThreadSanitizer設计配置了2个segment集合，SS和SS-分别表示并发的读/写segment集合。任何对共享内存空间的访问都会更新并迭代遍历这2个segment集合，利用lockset算法实现数据竞争。Acculock在开发中使用了epoch形式的逻辑时钟进行happens-before关系的分析，以此为基础再利用Iockset算法给出验证。同时Acculock再次根据lockset的包含关系卓具实效地减少了冗余操作的分析。而且，MultiLock-HB又对Acculock算法中的固有缺陷切实引入了改进，提升了检测数据竞争的能力。SimpleLock和SimpleLock+则是分别使用标量变量lockcnt和布尔变量iszero来对lockset算法融合了优化改进，加快了可疑并发操作是否被公共锁保护分析的过程。