多线程程序中的数据竞争检测与局限性分析

© 2013 O.- K. Ha.出版社：Elsevier B.V.信息工程研究院负责评选和同行评议可在www.sciencedirect.com在线获取ScienceDirectIERI Procedia 4（2013）174 - 1802013年电子工程与计算机科学数据竞赛河玉均 *国立庆尚大学工程研究所，501 Jinju Dae-ro，Jinju 660-701，Repubblic of Korea摘要数据多线程程序中的竞争是典型的访问共享内存由并发线程的交错引起的位置。很难判断一个程序是否会遇到数据竞争，因为程序有很多可能的执行，而且很多数据竞争都是硬来繁殖 因此，应该使用一系列自动检测器来采用用于监视和分析程序执行的复杂技术。不幸的是，我们不能仅仅依赖于一个动态检测器的定位结果，因为每个动态检测器表现出不同的限制，即使他们提供了显着的优势，通过他们的每一个技术。本文介绍了调查的优点和局限性表现出的代表性的四个动态检测器的基础上同步原语。© 2013作者。由Elsevier B. V.在CC BY -NC-ND许可下开放获取。信息工程研究院负责评选和同行评议关键词：数据竞争，动态数据竞争检测，多线程程序1. 介绍多线程程序通常用于普遍存在的多核或多处理器系统。数据竞争[1]在多线程程序中，多线程程序代表了最臭名昭著的一类软件缺陷，这些缺陷通过并发线程的交错而导致临界区的当两个或两个以上* 通讯作者。联系电话：+82-55-772-1370。电子邮件地址：jassmin@gnu.ac.kr。2212-6678 © 2013作者由Elsevier B. V.在CC BY-NC-ND许可下开放获取。信息工程研究所负责的选择和同行评审doi：10.1016/j.ieri.2013.11.025Ok-Kyoon Ha / IERI Procedia 4（2013）174175并发线程访问共享存储器位置而没有显式同步，并且它们中至少有一个是写。检测多线程程序中的数据竞争是很重要的，因为它保证了程序的可靠性，如果程序是免费的数据竞争。很难判断一个程序是否会遇到数据竞争，因为程序有很多可能的执行，而且很多数据竞争很难重现。因此，自动化的工具，采用先进的技术来监控和分析程序的执行被用来定位数据的竞争，而不是手动识别的错误进行调试。数据竞争检测器通常使用静态和动态技术之一。静态技术通过分析程序信息来报告源代码中的数据竞争，而动态技术则从程序的执行信息中定位数据竞争。静态检测器是可靠的，但不精确，因为它们报告了太多的误报。动态检测器是精确的或不精确的，但不可靠，因为它们不能保证在程序的给定执行中至少定位一个数据竞争的存在，如果存在的话。动态检测器采用基于跟踪的事后分析方法或动态方法，其报告程序执行中发生的数据竞争。事后分析方法分析跟踪的信息或在执行后重新执行程序。动态方法基于三种不同的分析方法：锁集分析、之前发生分析和混合分析。锁集分析通过检查锁定规则的违反来报告被监视程序的数据竞争，并且happens-before分析通过基于逻辑时间戳（诸如向量时钟）的使用来比较当前访问和所维护的先前访问之间的happens-before关系来报告它们之间的数据竞争。 锁集分析是简单的，可以实现低开销。然而，锁集分析可能会导致许多误报，因为它忽略了非常见锁的同步原语，如信号/等待，fork/join和屏障。happens-before分析是精确的，因为它不会报告误报，并且可以应用于所有同步原语。然而，由于性能开销，它很难有效地实现。混合方法试图减少纯锁集分析的主要缺点，并获得比纯happens-before分析更好的性能。几种动态数据竞争检测技术以其显著的优势在自动化工具中被执行。检测器中使用的这些技术有一些局限性，因为它们只分析具有单个输入的程序的动态执行。大多数动态检测器试图通过考虑在程序的实际执行中获得的同步操作的顺序来覆盖这些限制，例如fork-join、锁、信号等待和屏障，但是它们仍然提供有限的优点（例如，支持特定的同步原语，提高执行开销的效率或精确性等）。本调查考虑了四种具有代表性的动态探测器，Eraser[2]，Djit+ [3]，FastTrack[4]和AccuLock[5]，以介绍其技术特性和局限性。2. 橡皮擦Eraser [2]是第一个动态检测器，它检查违反锁定规则的情况，称为锁集分析，它规定任何两个不同的线程访问具有公共锁的共享内存位置。为了检测数据竞争，擦除器维护在共享存储器位置x的程序执行期间由所有线程持有的锁Cx的候选集合。每当不同线程上的任何两个访问通过至少一次写入访问共享内存位置，并且这两个访问不受公共锁保护时，此检测器就会定位数据竞争。形式上，给定两个访问ei和ej，176Ok-Kyoon Ha / IERI Procedia 4（2013）174种族_E（e，e）种族E（ei）种族（一）i（t t）i j xThread1Thread1W1 X=fork（）线程2R1 =xfork（）线程2R2=xW 2x=(a)（b）第（1）款Fig. 1. (a)不含MSM的Eraser的假阳性;（b）含MSM的其中Cx通过将自身与当前线程持有的锁集相交来维护一组锁。Eraser使用内存状态机（MSM），它由Virgin、Exclusive、Shared和Shared组成修改状态。共享存储器位置x在首次分配时没有锁集并且还没有被任何线程访问时被设置为原始状态。一旦x被特定线程独占访问，它就进入Exclusive状态。如果同一个内存位置被任何其他线程读取或写入，则状态分别更改为共享或共享修改。在新线程上对x的写访问将状态从独占或共享更改为共享修改。在Shared-Modified状态下，通过检查Race_E（）的条件来报告数据竞争。图1显示了Eraser的误报。图1（a）和（b）分别描述了纯Eraser的假阳性情况和Eraser与MSM的假阳性情况。在图1（a）中，Eraser报告数据竞争{W1-R2}，因为线程1上的写访问W1不保护任何锁，并且读访问R2发生在没有锁的不同线程2上，因此Cx= Cx。然而，实际上，W1从来没有与R 2组成数据竞争，因为显而易见的事实是，R2总是在W1之后通过fork操作发生。在图1（a）的情况下，具有MSM的Eraser不报告误报，但它仍然产生其他误报。在图1（b）中，当线程1上的读访问R1发生时，状态进入独占。当对新线程2进行写访问W2时，状态从独占变为共享修改。最后，检测器通过检查最终状态下Race_E（）的条件来报告数据竞争{R1-W2}。然而，由于与图1（a）的情况类似的原因，它也是假阳性Eraser很简单，并且比其他使用happens-before分析的检测器开销更少。然而，橡皮擦不能保证程序没有数据竞争。此外，它会产生太多的误报，因为它只考虑锁操作，而忽略了其他同步原语，比如图1所示的fork/join操作。因此，Easer不能保证在给定的程序执行中找到至少一个数据竞争的存在，如果存在的话。Ok-Kyoon Ha / IERI Procedia 4（2013）1741773. Djit+和FastTrackDjit+ [3]是一个高性能的动态数据竞争检测器，它使用基于矢量时钟的happens-before分析，FastTrack [4]是最有效的动态检测器，它使用happens-before分析来改进Djit+。happens-before分析使用Lamport的happens-before关系的表示[6]来确定两个线程段之间的逻辑并发。通过该关系，如果线程t必须发生在一个相对于u的线程中，则该线程是为u而发生的，而不是由t_u来决定的。 如果t不满足u，我们说t与u并发，用t表示||联合向量时钟（VC）被广泛用于精确地分析happens-before关系，因为VC可以通知线程的执行顺序以及线程操作和对共享存储器位置的访问的同步顺序。这两个检测器都报告数据竞争，包括对共享内存位置x的当前访问和对同一内存位置的早期访问，这些访问在多线程程序执行期间被维护在一种特殊的数据结构中，称为访问历史。只要两个并发线程段上的任何两个访问至少通过一次写入访问x，这些检测器就会定位数据竞争。形式上，给定分别来自线程段ti和tj的两个访问序列ei和ej，Race_D（e，e）种族（eiwriteewritee）种族（二）i我是说，||t j对于共享内存位置x，Djit+使用Rx和Wx条目定义访问历史，Rx和Wx条目分别记录对x的所有读和写访问的向量时钟。FastTrack使用Rx记录所有并发读访问的向量时钟或x的最后一次读访问的epoch时钟，Wx仅记录x的最后一次写访问的epoch，其中epoch是线程段的轻量级标识符，该线程段使用FastTrack代替重量级VC的一对时钟值和线程段id。Djit+和FastTrack不会像图1所示的Eraser那样报告误报，因为在对它们的分析可以应用于所有同步原语（包括fork/join操作）之前，基于VC的发生了。然而，Djit+显然需要O（n）空间来维护每个线程的VC和访问历史，并且它还需要O（n）时间来进行VC操作（例如连接，复制，比较等）。FastTrack通过利用轻量级的epoch，将Djit+中几乎所有VC操作的运行时间和空间开销从O（n）降低到O（1），以检测数据竞争。但是，利用FastTrack中的VC操作来分析具有大量并发线程的程序的执行，仍然存在着大量的运行时间和空间开销。178Ok-Kyoon Ha / IERI Procedia 4（2013）174螺纹1螺纹2螺纹 1获取（L1）释放（L1）获取（L1）W2x=释放（L1）获取（L1）获取（L2）X=释放（L2）获取（L2）W2x=释放（L2）获取（L1）W 1 X=释放（L1）R3=x释放（L1）(a)（b）第（1）款图二. (a)FastTrack的假阴性病例;（b）AccuLock此外，采用基于VC的happens-before分析的动态检测器，如Djit+和FastTrack，可能会导致误报，因为它们只分析具有单个输入的程序的动态执行。图2（a）显示了FastTrack的假阴性情况。在图2（a）中，如果线程1在线程2之前获得锁L1，FastTrack将报告W1和W2之间的数据竞争，因为Race_D（）的条件满足，因此W1||W2.然而，如果获取锁L1被保留，FastTrack将报告没有数据竞争，因为W1和W2是由关系之前的happpen所决定的。因此，这两个检测器也不能保证在程序的给定执行中定位至少一个数据竞争的存在。4. AccuLock自从FastTrack被引入以来，已经设计了一些检测器，通过利用epoch的轻量级来结合锁集分析和happens-before分析。AccuLock [5]是首次尝试使用组合方法来实现与FastTrack相当的性能和有限的误报。该检测器将一种新的高效锁集算法应用于FastTrack，以使用潜在数据竞争（称为竞争）的概念来强制执行线程锁定规则，其中任何两个并发读/写事件访问共享内存位置而不使用公共锁。检测器提供了对使用线程锁定的线程交错的敏感性的覆盖，因为它排除了利用从向量时钟获取和释放的锁观察到的happens-before关系的子集（例如，图2（a）中所示的FastTrack的假阴性情况）。但是，AccuLock仍然会报告使用多线程锁定的程序的误报，这是由于其扩展的锁集分析。因此，该检测器也不能保证在程序的给定执行中定位至少一个数据竞争的存在。例如，在Fig.2（b），如果Thr e ad 1 a对于Thr e ad 2 a请求锁L2请求锁L1 b，则保持W1-W2-R3，并且AccuLock将报告它们之间没有数据竞争。然而，如果保留了获取顺序，则该检测器将肯定地报告W 1和R 3之间的竞争，尽管发生了W2与W1和R3之间的竞争的明确事实，以供分析。这种失败是由于在其新的锁集分析中执行的锁集相交造成的，该分析旨在权衡效率的不精确性。Ok-Kyoon Ha / IERI Procedia 4（2013）1741795. 结论检测多线程程序中的数据竞争非常重要，因为它保证了程序的可靠性。很难判断一个程序是否会遇到数据竞争，因为程序有很多可能的执行，而且很多数据竞争很难重现。因此，应该使用一系列自动检测器来定位数据竞争，这些自动检测器采用复杂的技术来监视和分析程序执行。然而，每个动态检测器表现出不同的局限性，即使他们提供了显着的优势，通过他们的技术。表1.每种动态检测器同步原语探测器技术Fork-Join Locks Sign-Wait BarrierEraser Lockset分析误报Djit+分析前发生误报快速跟踪分析前发生的情况错误否定错误AccuLock Hybrid分析？？假阳性？？本文提出了一个调查的优点和局限性所表现出的四个动态检测器，代表每一个动态检测技术，如锁集分析，之前发生的分析，和混合分析。表1总结了每种动态检测器的优点和局限性。该表强调了我们不能仅仅依赖于动态检测器的定位结果。然而，幸运的是，研究人员正在开发克服现有动态检测器的局限性（例如，Google研究团队将开发新版本的ThreadSinizer [7]，旨在重建一个实际精确的动态检测器）。因此，我们需要仔细选择动态检测器来调试数据竞争，通过考虑它们的优点和局限性。确认本研究由韩国教育科学技术部资助的韩国国家研究基金会（NRF）的基础科学研究计划（2012-0007434）支持。引用[1] R. H. B. Netzer和B. P·米勒。什么是竞赛条件？：一些问题和形式化。ACM Lett.程序.Lang.Syst.1992; 1：74-88.[2] S.萨维奇，M。Burrows，G. Nelson，P. Sobalvarro，and T.安德森擦除器：多线程程序的动态数据竞争检测器。ACM Trans. Comput. 1997; 15：391-411.[3] E. Pozniansky和A.舒斯特多线程C++程序中的高效动态数据竞争检测。SIGPLAN不。2003; 38（10）：179-190.[4] C. Flanagan和S. N.弗罗因德FastTrack：高效精确的动态竞态检测。ACM的通信。2010; 53（11）：121-133.[5] X. Xie和J.雪AccuLock：准确有效地检测数据竞争。在第九届会议上，180Ok-Kyoon Ha / IERI Procedia 4（2013）174IEEE/ACM代码生成和优化国际研讨会（CGO），第201-212页，华盛顿特区，美国，2011年。[6] L.兰波特分布式系统中的时间、时钟和事件顺序。ACM的通信。1978; 21：558-565.[7] K. Serebryany和T.伊斯霍扎诺夫ThreadSanitizer：实践中的数据竞争检测。In Proceedings of二进制仪器和应用研讨会（WBIA），第65-71页，美国纽约州纽约市，2009年。