（计算机软件与理论专业论文）增量式数据竞争检测.pdf

摘要 摘要 在多线程程序中，当两个线程在没有时序约束下访问同一段内存位置时，就 可能导致数据竞争。数据竞争使多线程程序的执行具有不确定性，且难于调试和 理解。因此研究开发自动检测数据竞争的精确高效工具是非常有价值的。作为第 一个在语言级别支持多线程的编程语言，j a v a 被广泛地使用，因此开展对j a v a 并发程序的分析和优化是非常重要的。 本论文以j a v a 程序的数据竞争检测技术研究为选题，在调研现有的静态和 动态竞争检测技术的基础上，提出并在实际的j a v a 虚拟机中实现了一种精确有 效的在线增量式数据竞争检测算法。论文的主要工作和特色如下： 1 基于即时编译器，提出了一种结合锁集和发生序关系的增量式竞争检测 框架。该框架兼具静态分析不受程序规模限制、无插桩和动态分析的仅分析运行 时相关方法、精确性高等特点。该框架包括方法内分析和方法间分析两个部分。 2 基于增量式竞争检测框架，设计方法内分析算法，为流经编译流水线的 每个方法收集方法摘要信息，并动态构建和维护跨线程方法调用图。方法摘要包 括对象间的域引用关系、对象访问事件、尚未分析的调用点和由s t a r t j o i n 引起的 线程时序关系等，为方法间分析提供基础信息。跨线程方法调用图的动态构建和 维护既降低了空间开销，也能适应j a v a 语言这种因动态类载入等而导致的“开 放世界 环境。 3 设计自下而上的上下文敏感的跨线程的方法间分析算法，在分析的同时 计算并输出潜在的数据竞争。所设计的方法间分析算法保证每个方法最多只被分 析一次，并且仅当一个方法的所有被调用点均被分析后，才将该方法向上结合， 保证静态程序正文中的每个调用点只被分析一次。 4 基于上述框架和算法，在实际的j a v as e 平台h a r m o n y 上实现了增量式 竞争检测系统。通过对s p e c j b b 2 0 0 5 等多个基准程序的测试，实验结果表明所 提算法具有与o c a l l a h a n 和c h o i 等的动态竞争检测算法类似的精确性，而算法 所用的分析时间仅占总编译时间的2 0 o 4 左右，且无额外的运行时开销。 关键词：增量式数据竞争程序分析逃逸分析锁集发生序关系 a b s t r a c t a b s t r a c t w h e nt w ot h r e a d sa c c e s sas h a r e dm e m o r yt h a ta tl e a s to n ea c c e s si st h ew r i t e a n dt h et w oa c c e s s e sh a v en oh a p p e n s b e f o r er e l a t i o n ，t h ed a t al a c , eh a p p e n s d a t a l a c ei ss e r i o u sp r o g r a m m i n ge r r o r f u r t h e r m o r e ，p r o g r a m s 诚md a t al a c e s a r e n o t o r i o u s l yd i f f i c u l tt od e b u ga n du n d e r s t a n db e c a u s et h e yc a ne x h i b i td i f f e r e n t b e h a v i o r sw i t ht h es a m ei n p u t s s oi ti sw i d e l yr e c o g n i z e dt h a tt o o l sf o ra u t o m a t i c d e t e c t i o no fp o t e n t i a ld a t al a c e sc a b b ev a l u a b l e ：a st h ef i r s tl a n g u a g et h a ts u p p o r t s m u l t i t h r e a dp r o g r a m m i n gi nl a n g u a g el e v e l ，j a v ai sb r o a d l yu s e d s or e s e a r c h i n gt h e p r o g r a ma n a l y s i s a n do p t i m i z a t i o no nj a v ac o n c u r r e n tp r o g r a m si sv e r yi m p o r t a n ta n d s i g n i f i c a t i v e t h i sp a p e rr e s e a r c h e st h ed a t ar a c ed e t e c t i o nt e c h n o l o g i e sf o rj a v ap r o g r a m s b a s e do nt h er e s e a r c h e sa b o u tt h ee x i s t i n gs t a t i ca n dd y n a m i cr a c ed e t e c t i o n a l g o r i t h m s ，an e wp r e c i s ea n de f f i c i e n ta l g o r i t h mo ni n c r e m e n t a l l yd e t e c t i n gp o t e n t i a l d a t al a c e si nj a v am u l t i t h r e a d e dp r o g r m n si sp r e s e n t e d t h i sp a p e rm a i n l yd e p i c t sa n d d i s c u s s e st h ef o l l o w i n gw o r k s ： 1 p u t sf o r w a r da ni n c r e m e n t a ld a t ar a c ed e t e c t i o na l g o r i t h mf r a m e w o r k b a s e do nj u s t - i n - t i m e ( j i t ) c o m p i l e r , w h i c hc o m b i n e st h el o c k s e t - b a s e d d e t e c t i o na n dh a p p e n s b e f o r e - b a s e dd e t e c t i o n i th a se i t h e rt h eu n l i m i t e dp r o g r a m s c a l ea d v a n t a g eo ft h es t a t i ca n a l y s i so rt h eh i g hp r e c i s i o na d v a n t a g eo ft h ed y n a m i c a n a l y s i s t h ef r a m e w o r ki n c l u d e si n t l a - a n di n t e r - m e t h o da l g o r i t h m s 2 b a s eo nt h ei n c r e m e n t a lr a c ed e t e c t i o nf r a m e w o r k , t h ea l g o r i t h mi nt u r n d o e si n t r a m e t h o da n a l y s i so ne v e r ym e t h o dc o m p i l e db yj i tc o m p i l e ro n l yo n c e a n dc o l l e c t st h e i rs u m m a r i e si n d e p e n d e n to ft h ec o n t e x ta n dd y n a m i c a l l yb u i l d s a n dm a i n t a i n st h em u l t i t h r e a d e dc a l lg r a p h t h em e t h o ds u m m a r yi n c l u d e so b j e c t s f i e l d r e f e r e n c er e l a t i o n s ，a c c e s se v e n t s ，t h eu n a n a l y z e dc a l l s i t e sa n dt h es t a r t j o i n t h r e a dr e l a t i o n se ta 1 t h ei n t e r - m e t h o da n a l y s i si sb a s e do nt h em e t h o ds u m m a r i e s c o l l e c t e di nt h ei n t r a - m e t h o da n a l y s i s d y n a m i c a l l yb u i l d i n ga n dm a i n t a i n i n gt h e m u l t i t h r e a dc a l lg r a p hr e d u c e st h es p a c ec o s ta n dc a na n a l y z et h ej a v ap r o g r a m s w h i c ha r e “o p e nw o r l d p r o g r a m sb e c a u s eo fd y n a m i cc l a s sl o a d 3 b a s e do nt h em e t h o ds u m m a r i e s ，t h ec o n t e x t - s e n s i t i v ei n t e r - t h r e a d a n a l y s i si sp r o p o s e dt oi n c r e m e n t a l l yc o m p u t ep o t e n t i a lr a c ei n f o r m a t i o na n d o u t p u tt h e mi nt i m e n o to n l yd o e st h ea l g o r i t h ma n a l y z ee a c hm e t h o do n l yo n c eb u t a b s t r a e t a l s oi ta n a l y z e se a c hc a l ls i t eo n l yo n c e i fo n l ya l lc a l ls i t e so f am e t h o da l ea n a l y z e d ， t h em e t h o dc a l lb ec o m b i n e d 、析h ei t sc a l l e r 4 b a s e do nt h ef r a m e w o r ka n da l g o r i t h m ，w eh a v ei m p l e m e n t e dt h e a n a l y s i si nt h eo p e ns o u r c ej a v as eh a r m o n y b yt e s t i n g 、析ms e v e r a lb e n c h m a r k s ， s u c ha ss p e c j b b 2 0 0 5 ，i nt h ej v mw i t ht h er a c ed e t e c t i o np a s s ，t h ee x p e r i m e n t a l r e s u l t ss h o wt h a tt h er a c ed e t e c t i o np a s sh a st h es i m i l a rp r e c i s i o nw i t ho c a l l a h a na n d c h o i sa l g o r i t h mo nd y n a m i cr a c ed e t e c t i o n ，a n do n l yc o n s u m e s2 4 o ft h et o t a l c o m p i l a t i o nt i m ea n dh a sn o ta d d i t i o n a lr u n t i m eo v e r h e a d k e yw o r d s ：i n c r e m e n t a l ，d a t ar a c e ，e s c a p ea n a l y s i s ，l o c ks e t , h a p p e n s b e f o r e r e l a t i o n i v 中国科学技术大学学位论文相关声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特另, l j n 以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明： 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：盂臣鱼坠 研年万月万日 第1 章绪论 第1 章绪论 本文介绍了一种新的增量式竞争检测系统，并分别从系统框架、方法内分析、 方法间分析，以及系统实现和实验测试四个方面进行详细讨论。本章首先介绍了 数据竞争检测的研究背景，数据竞争是由于多个线程间没有正确进行同步，使得 多线程对同一共享内存位置存在冲突访问。数据竞争是一类严重的并发编程错 误，导致执行结果的不确定性。因此研究竞争检测技术非常有意义。接着介绍了 近年来在数据竞争检测已有的研究方法和研究成果，并对其进行归纳分类。最后 讨论本文所完成的工作以及所做的主要贡献。 1 1 研究背景和动机 随着多核处理器的普及，如果程序员编写的程序没有针对多核的特点来设 计，那就不能完全获得多核处理器带来的性能提升，因此这种多内核环境极大的 促进了并行编程语言的快速发展。j a v a 语言是第一个在语言级别支持多线程的程 序设计语言，且具有跨平台的优点，是被广泛使用的并发编程语言之一。多线程 程序中，线程问通过共享内存、消息传递等方式进行通信。其中内存共享方式表 示多个线程能访问同一个共享内存单元。当多个线程访问( 分为读访问和写访问) 同一内存单元时，为了避免访问冲突，必须对多个线程的访问进行正确同步。j a v a 语言本身提供了s y n c h r o n i z e d 进行同步，为了了解对j a v a 多线程程序进行数据竞 争检测的必要性，首先需要了解j a v a 语言的特点、j a v a 内存模型以及j a v a 同步 机s j j j a v a 语言包含简单类型( 如b o o l e a n 、i n t 等) 和引用类型两种数据类型，引用 类型包括类类型和数组类型，其值包括对象的引用或者是n u l l 。对象由一组简单 类型或引用类型的域组成。在j a v a 程序中，可能被多个线程并发访问的内存位 置有类的静态域和在堆中分配的对象的域。 根据j a v a 虚拟机规范( j a v av i r t u a lm a c h i n es p e c i f i c a t i o n ) 1 2 1 ，j a v a 程序在运行 时创建的所有类实例或数组都放在同一个堆中。一个j a v a 虚拟机实例中只存在 一个堆空间( j a v ah e a pm e m o r y ) ，因此所有线程都共享这个堆。又由于一个j a v a 程序独占一个j a v a 虚拟机实例，因而每个j a v a 程序都有它自己的堆空间( 或主 存) ，但是同一个j a v a 程序的多个线程却共享同一个堆空间，每个线程都有自 己的工作内存( w o r k i n gm e m o r y ) ，工作内存中保存的是共享堆中某些变量的拷 贝，线程对所有变量的操作都是在工作内存中进行，线程之间无法相互直接访问， 第l 章绪论 变量传递均需要通过主存完成，在这种情况下，就得考虑多线程访问对象( 堆数 据) 的同步问题了。 j a v a 程序的数据共享机制相对于其他的线程间通信机制更加简单。但是这其 中也存在着巨大的风险：数据竞争。在多线程程序中，当两个线程在没有时序关 系约束情况下访问同一个内存位置，且两次访问所加的锁的交集为空，且至少有 一个访问是写访问时，就会发生数据竞争( d a t ar a c e ) 9 1 。数据竞争主要是由于 没有对并发访问的内存位置进行正确的同步造成的。存在数据竞争的程序不是一 个“正确同步”的程序，执行结果具有不确定性，针对同一输入的多次执行结果很 可能不同。为了消除数据竞争，多个线程访问共享的变量必须经过合理的协调， 这样线程才不会相互干扰。 为避免数据竞争，j a v a 提供如下同步机制用于编程： 1 ) t h r e a d 对象的s t a r t 和j o i n 方法，分别用于启动线程对象和等待线程对象 的结束； 2 ) w a i t 和n o t i f y c a l l ) 方法，分别用于使线程对象进入阻塞状态和通知唤醒某 个或所有处在阻塞状态的线程对象。 3 ) s y n c h r o n i z e d ( s t a t i c ) 方法和s y n c h r o n i z e d 语句( 统称同步结构) ，j a v a 中每 个对象对应有一个监视器，线程可以通过同步结构对对象的监视器加锁或解锁， 每次只有一个线程可以持有某监视器上的锁，其他试图对这个监视器加锁的线程 都将被阻塞直到它们获得这个监视器上的锁。 通过上面关于j a v a 语言内存模型和同步机制的介绍，可知对多线程程序必 须进行正确同步以保证对共享数据的正确访问，从而消除竞争。但在实际编写 j a v a 程序时使用同步不当会带来一些严重的问题：过分保守地使用同步( 称为粗 粒度的锁机制) 易于保证程序的正确性，但是不必要的同步带来额外的锁操作开 销( 每一次访问被锁保护的变量时都要获得该锁，确保在同一时刻只有一个线程 可以访问这个变量) ，甚至可能造成死锁，并且降低并发度，进而影响程序性能。 事实上，并不是所有数据都需要锁的保护，只有那些被多个线程访问的可变数据 需要。那些被代码独享地操作的本地( 基于栈的) 变量不被跨线程地共享，因此 不需要同步。同样，过分谨慎地使用同步( 称为细粒度锁机制) 也会产生问题， 虽然减少同步能提高程序的性能，但写出的程序稳定性差且易出错，主要会引起 两类错误：数据竞争错误和活性错误( 指死锁，活锁和饥饿) ，这两类并发程序 的问题很难发现，分析起来也很复杂，目前还没有很好的解决办法。本文主要致 力于研究j a v a 程序的数据竞争检测技术。 2 第1 章绪论 1 2 相关研究 目前，已经有大量关于数据竞争检测方面的研究工作，本小节将按照不同的 划分标准讨论现有的主要竞争检测技术。按照竞争检测的时机，数据竞争检测技 术主要分为动态 3 - - 6 , 2 4 3 2 ，3 3 1 和静态 7 - 1 1 , 1 6 t 3 5 那i 两类。按照竞争检测的依据，竞争检 测又可分为：基于锁集【4 “1 1 ，3 、基于发生序关系( h a p p e n s b e f o r e ) 、或基于二 者结合。基于锁集的检测技术是目前研究最广泛的竞争检测技术。 1 2 1 竞争检测的时机 按照竞争检测的时机，数据竞争检测技术主要分为动态 3 , - 6 , 2 4 , 3 2 ，3 3 1 和静态 1 7 - 1 1 , 1 6 , 3 5 ，3 6 1 两类。动态竞争检测是运行时检测，通过在程序中插桩代码来跟踪程 序的执行，利用程序执行踪迹进行在线或事后分析来识别潜在的竞争。静态竞争 检测是编译时检测，往往需要分析整个程序版本，无需插桩。 动态竞争检测 早期的许多动态数据竞争检测技术都是基于一个叫做e r a s e r 的数据竞争检 测器d 2 1 。e r a s e r 能动态地检测基于锁的多线程程序中的数据竞争。e r a s e r 用二进 制重写技术来监测每个共享内存引用和验证一致的锁行为被观察。作者为d i g i t a l u n i x 实现了e r a s e r 并用它侦测大量程序中的数据竞争。但是它所检测到的数据 竞争中有很多是“假”数据竞争，且由于插桩带来很大的运行时开销c h o i 等讲l 描述了一个针对多线程面向对象程序的、基于 w e a k - t h a n 关系( 用于识别冗余的 内存访问事件，假设有三个访问事件a ，b ，c i 如果a 与b 存在竞争则一定有c 与b 存在竞争，则称c 是 w e a k t h a n a 的，在分析时访问事件a 可不必记录) 的 动态数据竞争检测算法，主要分为静态分析、插桩( 指在程序中插入一段程序或 修改某些数据结构用于获得有用的运行时信息) 、运行时优化和运行时检测几个 阶段，其中静态分析阶段没有插桩开销能保证程序的性能，而动态分析阶段仅分 析和运行时相关的方法减少了假的竞争数，保证了分析的精确性。n i s h i y a m a 等 【3 3 】将基于读障栅( r e a d - b a r r i e r - b a s e d ) 的动态逃逸分析用于减少运行时的数据竞 争检测，并在s u n 的m i c r o s y s t e m 平台上的j a v ah o t s p o t 虚拟机中实现。动态分 析的优点是几乎没有假的数据竞争警告，缺点是随着程序规模的增加，程序插桩 开销不断增加。 动态技术通过插桩获得变量和别名的准确信息，并能准确捕获对共享内存访 问的发生序关系和或锁定信息，因此几乎不会报告假竞争( 即错报) ；但是这类方 法已被证明开销很大，例如，t r a d e 中的大量插桩使运行开销增加了4 x ，1 5 x 【3 l ， 限制了待检测的程序规模；此外，动态技术依赖于程序输入，会漏报一些真正的 竞争。 第1 章绪论 静态竞争检测 目前已经有很多工作致力于静态数据竞争检测技术1 7 1z , 1 6 5 ，3 6 j 。静态竞争检 测是编译时检测，主要分为以下三类：1 ) 流不敏感的基于类型的系统【7 1 ；2 ) 流 敏感的基于锁集的静态的竞争检测【1 0 , 1 6 1 ：3 ) 路径敏感的模型检测器【8 1 。c h o i 等 u 6 l 的检测方法分成了一系列的分析阶段( 逃逸分析阶段、别名分析阶段、竞争检 测阶段) ，随着各阶段的进行，逐渐过滤到不存在竞争的访问，缩小检测范围， 但是他们的算法是上下文不敏感的，不能处理开放式程序，只适用于小型的j a v a 程序。n a i k 等 1 0 l 开放了一种类似的分阶段的检测方法，分为可达对象对检测， 别名对像对检测，逃逸对像对检测，未加锁对象对检测四个阶段，在这是个阶段 使用以下分析：调用图构造，别名分析，线程逃逸分析和锁分析，算法的逃逸分 析和别名分析过程与c h o i 等【1 6 1 的算法类似，但是n a i k 等人的算法是上下文敏感 的跨线程分析，且具有更好的可用性，能够分析开放式程序。 和动态方法相比，静态分析具有不受程序规模的限制，易于分析大型的程序 的优点，但是由于静态分析的不可判定性【l i l ，静态检测算法都是不完备的近似算 法。而且以前的静态分析大都没有考虑线程的时序关系，检测到的竞争中有很多 假竞争，并且都是在分析整个程序之后给出竞争结果，会分析很多无关的程序部 分，造成分析结果中有很多假竞争，精确度不高，且响应性较差。 混合的竞争检测 由前面的介绍可知，动态竞争检测具有很高的精确性，但是插入的监测代码 极大地增加了运行时开销，有的甚至会影响程序原来的执行语义，此外，动态检 监测的结果依赖特定的输入、调度、执行路径，会产生漏报，这个问题对于并发 程序更加突出。而静态竞争检测由于无需插桩，没有运行时开销，因此效率比动 态检测高。但是静态检测受到线程交互、动态数据分配、别名信息的影响，很难 有精确的实现，而且据我们调研所知，已有的静态竞争检测技术都是根据一定的 策略分析整个程序版本之后，再根据竞争条件对收集的信息计算数据竞争，因此 会分析很多无关的代码，影响分析的精确性，而且整个分析需要大量空间来保存 对象的访问事件。 c h o i 等【2 4 】研究了一种针对面向对象的多线程程序的混合的数据竞争检测技 术，他们的算法包括静态数据竞争分析，优化的插桩，运行时访问缓存以及运行 时检测四个阶段。利用前三个阶段的分析和优化，有效降低了动态检测的开销， 达到了效率和精确性的平衡。 4 第l 章绪论 1 2 2 竞争检测的依据 按照数据竞争检测的依据，竞争检测主要有：( 1 ) 基于锁集的竞争检测； ( 2 ) 基于发生序( h a p p e n s b e f o r e ) 关系的的竞争检测；( 3 ) 二者的结合的竞 争检测技术。 基于锁集 目前基于锁集的检测技术是研究最广泛的竞争检测技术【4 , 6 - - n , 3 2 , 3 5 】，当两个线 程在没有保持至少一个公共锁的情况下访问同一个内存位鼍时，可能发生潜在的 竞争 6 , 9 1 。当多个线程对共享内存位置肌的并发访问被一个公共锁，保护，如果 线程要访问历必须获得锁z 。在同一时刻仅有一个线程可以获得锁z ，因此如果 多线程程序严格遵守加锁机制对m 的访问不会产生竞争。 e r a s e r i 3 2 】是典型的基于锁集的竞争检测器。p r a u n 和g r o s s 在e r a s e r 的基础 上进行改进【4 】，他们利用逃逸分析过滤掉那些不会产生竞争的语句。基于锁集的 技术的优点是开销低，缺点是当程序中大量使用非基于锁集的同步原语时会报告 许多假竞争，同时也会漏报一些真正的竞争错误。r a c e r x 3 5 】是针对c 程序的基 于锁集的静态竞争检测工具，主要用于操作系统代码，使用启发式方法捕获被锁 保护的访问，多线程的代码部分和未被锁保护的良性的竞争访问。 基于发生序( h a p p e n s b e f o r e ) 早期的动态竞争检测大多是基于l a m p o r t 的“h a p p e n s b e f o r e ，模型【3 1 2 1 ，通过 捕获不同线程的同步事件的顺序关系来检测竞争。如果两个线程访问一个共享内 存位置，且根据l a m p o r t 定义这两个线程的访问是不满足发生序关系时，则可能 发生潜在的竞争【1 2 1 。由于动态的基于发生序的检测方法是在运行时跟踪程序的执 行顺序因此精确性很高，但是它的分析开销很大，且不能完全捕获线程的交错信 息，如一些基于l a m p o r t 的“h a p p e n s b e f o r e 模型的一些运行时检测工具都限制了 可挖掘的线程交错数目瞰l 。吴萍【1 1 等的静态竞争检测方法中利用程序分析来建立 像s t a r t j o i n 等引起的简单的时序关系，有效减少了假的竞争数目，提高了分析的 精确性。 结合锁集与发生序( h a p p e n s b e f o r e ) c h o i 等人实现了一种混合的动态竞争检测技术，结合了时序分析和锁集算 法 5 1 。本文的分析是静态的基于锁集的算法，并利用程序分析捕获了s t a r t j o i n 引 起的时序关系。另外c h o i 5 l 的分析以事件为中心，本文的分析以对象为中心，结 合了上下文敏感的指针分析和逃逸分析，比仅使用逃逸分析结果更精确。通过实 验对比可知本文的分析精确性和【3 】的动态分析精确性相当，但是在效率上更优。 5 第l 章绪论 在基于锁集的算法中引入时序关系分析可以减少假的竞争数，提高分析的精 确性。图1 1 是一个简单的多线程程序例子的伪代码，例中线程，l 和线程t 2 分别 对o l 和d 2 进行写访问，线程t 2 在线程t l 中启动。 t h r e a d 岛：t h r e a dt 2 ： l o c k ( j 1 ) l o c k ( 厶) w r i t e ( d 1 ) ：w r i t e ( 晓) ： 屯s t a r t 0 ： u n l o c k ( 厶) ： ) u n l o c k ( 砧： 图1 1 多线程程序伪代码 如果o l 和d 2 是不同的内存位置，则不存在竞争访问的问题。现在假设o i = 0 2 ( 指是对同一内存位置o l ( 或d 2 ) 的访问) ，且州= 如( 指两次访问被不同的锁保 护) ，如果不考虑线程 和t 2 之间由s t a r t 引起的时序关系，则竞争检测的结果 是这两个线程可能同时对o l ( 或0 2 ) 进行写，存在潜在的竞争访问。然而，如果加 入线程时序关系分析，由于线程t 2 是在线程，i 对o l 的写访问之后启动的，因此 f l 对d l 的写必定发生在t 2 对d 2 的写之前，这两次写访问不可能并发执行，从而 无论两次访问是否被公共锁保护，都不会产生竞争。所以说在竞争计算时加入时 序关系约束能有效减少假竞争数。 除了基于锁集和基于发生序的等常用的竞争检测技术外，还有一些其他的竞 争检测方法，如基于模型校验的检测和基于类型的检测。模型检测在给定程序的 状态空间的检测上非常有效，且容易生成反例，但是它不适用代码量超过1 0 k 的大型并发程序【8 】o 基于类型的竞争检测主要是针对开放性程序1 7 1 。 1 2 3辅助竞争检测的程序分析技术 在j a v a 程序中，可能被并发访问的内存位置有：类的静态域，堆中分配的 对象的域。本文的竞争检测算法以对象为中心，类的静态域被抽象为特殊的对象。 在多线程程序中，只有被多个线程并发访问的对象才有可能存在竞争访问，如果 可以竞争检测时获知哪些对象真正被多个线程访问，哪些对象仅在一个线程或一 个方法内被访问，则可缩减竞争检测的对象范围，从而降低空间开销。而逃逸分 析是识别对象的生命期状态的常用分析技术，因此在数据竞争检测算法中加入对 象逃逸分析可有效提高分析的效率。 另一方面，对不同方法中的对象，需要确定它们之间的别名关系。获得的对 象别名关系的精确性直接关系到竞争检测结果的精确性，比如，在图1 1 的例子 中，如果o l 和0 2 是不同的内存位置，即不互为别名，则不存在竞争访问的问题。 假设o l 和0 2 互为别名，即线程f l 和t 2 对同一内存位置o l ( 或d 2 ) 的访问。如果，l 和2 互为别名，则这两次访问被相同的锁，l ( 或如) 保护，因此不存在竞争，否则 6 第1 章绪论 如果l i 和2 是不同的内存位置，则由于两次访问被不同的锁保护，两个线程可 能同时对d l ( 或d 2 ) 进行写，存在潜在的竞争访问。因此对d l 和晚，l 与如是否是 别名关系的判断直接影响检测结果的精确性。下面分别介绍逃逸分析技术及应用 和结合逃逸分析的指针分析技术。 逃逸分析及应用 近年来，逃逸分析主要运用于j a v a 编译运行系统的优化工作中，用于计算 对象的逃逸状态( e s c a p es t a t e ) ，并以此作为程序优化工作的依据。逃逸状态反 映了对象的生命期状态，在逃逸分析中，对象的逃逸状态一般分为三类：未逃逸 状态( n o n e s c a p e ) 、方法逃逸状态( a r g e s c a p e ) 和全局逃逸状态( g l o b a l e s c a p e ) 。 其中n o n e s c a p e 、a r g e s c a p e 和g l o b a l e s c a p e 依次表示对象未逃逸出当前方法、 通过参数和返回值逃逸出当前方法但未逃逸出线程、逃逸出线程。 在过去研究中，已经为多线程开发了多个逃逸分析的算法【1 9 - - z 3 1 ，这些算法 使用对象间的可达性信息的近似来计算逃逸信息，其中可达性信息又是对象间的 指向信息的近似。这些算法使用逃逸信息进行栈分配和同步消除优化。然而这些 算法仅分析单线程，仅找到被当前线程访问的对象如果一个对象逃逸出当前线 程，或者对象的一个引用被写进一个静态类变量，或者因为对象变成对另一个线 程是可访问的，该对象即被标记为全局逃逸的这些算法都没有进一步分析那些 访问同一对象的多个线程问的交互关系，从而进一步识别哪些对象虽逃逸出线 程，但是在每个时刻最多只会被一个线程所访问。因此这些算法从根本上来讲是 顺序程序的分析，只不过进行了调整使得在并行线程存在的情况下能以保守的方 式进行操作。 为了达到更好的分析效果或获得更好的分析性能，有些分析工作往往将逃逸 分析与其它的分析相结合，如：w h a l e y 等1 2 0 1 、v i v i e n 等 2 6 1 和s a l c i a n u 等【1 5 】提出 了合并了逃逸分析与指针分析的算法，以获得更为精确的分析结果；c h e r e m 等 提出了一种结合了逃逸分析与效果分析( e f f e c ta n a l y s i s ) 的算法，以获取描 述j a v a 程序堆效果( h e a pe f f e c t s ) 的轻量级方法描述( l i g h t w e i g h tm e t h o d s u m m a r y ) 。 逃逸分析有许多优化应用，它除了可以用于对象内存空间管理优化工作之 外，还可以用于其它诸如多线程等方面的优化工作。在逃逸分析的这些优化应用 工作当中，栈上分配( s t a c ka l l o c a t i o n ) 1 9 , 2 0 , 2 6 , 3 9 , 3 9 1 和不必要同步的消除 ( s y n c h r o n i z a t i o ne l i m i n a t i o n ) 1 5 ，批9 ，3 0 , 3 1 3 引是逃逸分析的两个主要的应用。s o u t e r 等7 j 提出了一种利用逃逸分析进行面向对象软件测试与再测试技术。n i s h i y a m a 等【3 3 1 和l e e 等【2 4 】应用逃逸分析检测多线程间的数据竞争。 7 第i 章绪论 结合逃逸分析的指针分析 r u g i n a 等1 2 2 1 为可能并发更新共享指针的多线程程序陈述了一个新的方法间 的、流敏感的、上下文敏感的指针分析算法。s a l c i a n u 等【1 5 1 基于r u g i n a 等【2 2 1 的 研究开发了一个新的针对多线程的指针和逃逸分析技术。它能分析并发线程间的 交互。不同于以前的分析，该算法能检测那些被多个线程访问但是没有逃逸出某 个特定多线程计算的对象。然而该算法对被多个线程访问的对象仍然执行弱引用 更新( w e a ku p d a t e s ，即只是简单的增加一条指向边并不删除已有的指向边) ，是流 不敏感的分析。w h a l e 等【2 0 】提出了一个合并了指针分析和逃逸分析的算法用于 j a v a 程序的分析。该算法基于一个称为指向逃逸图( p o i n t t oe s c a p eg r a p h ) 的 抽象，它不仅描述了局部变量和对象中的域是如何引用其它的对象的，还包括对 象的逃逸信息。该算法设计成为可以分析完整的或不完整的程序的任意区域中的 对象是否逃逸出这个区域，并得到没有逃逸出被分析区域的对象的完整信息。因 此适合分析动态载入的程序。该算法在j a l a p e n oj v m 动态编译器中实现。r u g i n a 等1 2 s 针对多线程程序陈述了一个方法间的、流敏感的、上下文敏感的指针分析算 法。该算法能够处理并行结构的程序，包括f o r k - j o i n 结构，并行循环，以及基于 条件生成的线程( c o n d i t i o n a l l ys p a w n e dt h r e a d s ) 。v i v i e n 等瞰】描述了一个两 阶段的o f f l i n e o n l i n e 方法间和线程间逃逸分析算法。首先执行一个o f f l i n e 的预分 析，然后执行一个结合o f f l i n e 结果和动态信息的动态o n l i n e 分析，这两个阶段 的分析极大地提高了分析的性能和精确性。该算法的缺点是：是域不敏感的，为 了获得空间和处理时间的高效率该算法牺牲了部分精确性。o f t l i n e 阶段占用大部 分空间，且仅优化热方法( h o tm e t h o d ) 。 1 3 论文内容及主要贡献 在竞争检测的时机上，本文采用了静态检测的方法，但是由于虚拟机对应用 程序边编译边运行的特点，本文的分析也是运行时分析，具有动静结合的特点。 在竞争检测依据上，本文结合了基于锁集和发生序关系的检测方法，通过捕获由 s t a r t j o i n 引起的线程时序关系，在竞争检测时计算访问事件的发生序关系。就具 体竞争检测方法上而言，本文结合了多线程逃逸分析，极大的减少了分析的对象 数。最后本文在所选取的平台上实现了增量式竞争检测系统，并利用 s p e c j b b 2 0 0 5 等多个基准程序进行测试，对实验结果和相关的研究工作进行分析 对比，做性能评估。 本文重点探讨并完成了以下工作： 1 基于即时编译器，提出了一种新的增量式竞争检测框架 提出了一种结合锁集和发生序关系的增量式竞争检测框架，该框架包括方法 8 第l 章绪论 内分析和方法间分析。且兼具静态分析不受程序规模限制、无插桩和动态分析的 仅分析运行时相关的方法等特点，具体如下： 同时具有动态竞争检测和静态竞争检测的优点 利用虚拟机对应用程序边编译边运行的特点，在运行时进行增量式分析和计 算竞争检测，仅分析和运行时相关的程序部分，无需分析整个程序版本，降低了 误报率，且具有动态竞争检测的实时检测的特点。同时算法对方法内指令进行静 态分析，不在应用程序中插桩代码，故不改变程序的运行时开销只增加即时编译 的开销。 结合基于锁集和发生序关系 仅基于锁集的静态竞争检测由于没有考虑线程之间的交互引起的时序关系， 会报告很多假的竞争，导致精确性不高。动态竞争检测常使用发生序关系来比较 事件发生的先后，精确性很高。在本文的增量式竞争检测中，通过捕获s t a r t j o i n 引起的线程时序关系，在访问事件间建立发生序关系，改善了分析的精度。第5 章的实验结果论证了加入时序关系分析极大的降低了误报率。 借助多线程逃逸分析缩减分析的对象数目，提高分析效率。 只有全局逃逸的对象才可能被多个线程访问，才有可能存在竞争。本文算法 借助对象的逃逸信息来减少待分析的对象数。在方法内分析时为对象节点设置逃 逸属性，并利用指向图进行逃逸属性传播；在方法间分析时，通过方法间对象节 点间的映射，向上传播逃逸属性。在分析过程中。对于确定不会逃逸出线程的的 对象节点可以删除其相关信息。 算法不依赖于整个程序调用图，动态维护方法调用图减少空间开销。 由于在册中没有提供整个程序的方法调用图，本文的分析结合程序运行时 信息动态构造和维护多线程调用图，已经分析过的方法调用关系将被删除，这种 动态构建和维护方法调用图的方法不仅能有效降低空间开销，而且能适应j a v a 程序这种因动态类加载等特性导致的“开放世界”环境。 检测结果精确到具体方法的具体指令位置，方面程序员定位错误位置。 本文分析最后报告的数据竞争信息可精确到具体的线程、方法和指令，方便 程序员定位错误位置，具有高度可用性。 2 基于增量式竞争检测框架，设计方法内分析算法，为流经编译流水线的 每个方法收集方法摘要信息，并动态构建和维护跨线程方法调用图。 方法摘要包括对象间的域引用关系、对象访问事件、尚未分析的调用点和由 s t a r t j o i n 引起的线程时序关系等，为方法间分析提供基础信息。跨线程方法调用 图的动态构建和维护既降低了空间开销，也能适应j a v a 语言这种因动态类载入 等而导致的“开放世界 环境。 9 第l 章绪论 3 基于方法的完整方法摘要，设计自下而上的上下文敏感的跨线程的方法 间分析算法。在分析的同时计算并输出潜在的数据竞争 所设计的方法间分析算法保证每个方法最多只被分析一次，并为方法保存一 个初始方法摘要。随着方法间的摘要信息的结合，调用者方法摘要不断被完善， 当一个方法的所有被调用者的方法摘要均被向上结合后，该方法就具有完整方法 摘要。仅当一个方法具有完整方法摘要时，该方法才能沿多线程调用图继续向上 进行方法间信息结合，保证了静态程序正文中的每个调用点只被分析一次。当一 个方法的被调用者尚未被分析，在调用者中保存相应的调用点信息( 相当于调用 上下文信息) 。同一个被调用方法对于不同的调用者，根据被记录的调用点进行 上下文敏感的信息映射和信息结合。在两个方法进行方法摘要结合时增量计算并 输出潜在的竞争信息。 4 在实际平台上实现增量式竞争检测系统，并用多个j a v ab e n c h m a r k s 测 试该系统，通过和已有的研究成果进行对比，证明它的高效性和精确性。 本文以实际j a v a 虚拟机中即时编译阶段的优化遍( 称为竞争检测遍) 形式实 现了增量式竞争检测系统。通过对s p e c j b b 2 0 0 5 等多个基准程序的测试，实验 结果表明所提算法