（计算机软件与理论专业论文）多线程并发程序分析及别名算法研究.pdf

中国科学技术大学博士学位论文 摘要 摘要 多线程的并发程序越来越重要，它既是一种常见易用的程序结构，又可以支 持高效的并行计算。并发程序的广泛使用带来了新的优化机会和分析问题，同时 也对传统的针对顺序程序的程序分析方法提出了新的要求。 对并发语义和别名信息( p o i n t s - t o 信息) 的保守分析使得以往的并发程序分析算 法都是精度不高的近似算法。论文的主要工作围绕并发程序中冗余同步操作删除 和数据竞争检测问题提出了精确有效的分析算法。算法设计了高精度的流敏感 ( n o w s n e s i t i v c ) 、上下文敏感n t c x t s e n s i t i v e ) 别名分析，模拟了交互时序对分析 问题的影响。为提高分析效率，论文还提出了以对象为中心，结合e s c a p e 分析缩 小检测范围的竞争检测算法。 由于别名信息极大的影响了算法的效率和精度，论文工作的第二部分是并发 程序分析中的别名算法研究。论文首先探讨了不同设计要素对别名算法质量的影 响，进而针对分析语言和并发结构设计了一种流不敏感、上下文敏感的别名算法 并分别从语义和运行特征提出上下文敏感分析的两种优化方法。 除了程序分析，动态分析和模型检测是另外两种有效的分析手段。动态分析 和静态分析在分析精度、性能和覆盖率上有很好的互补性，论文针对竞争检测讨 论了它们相互结合的一些思路。程序分析和模型检测往往可以检测相同的属性， 分析过程也有相似之处，但是几乎没有对这两种方法适用的分析范围的研究。论 文对比分析了两种方法各自的优缺点，并以活跃变量分析为例说明了某些程序分 析中的数据流分析问题可以转换为模型检测问题，证明了二者在分析结论上的等 价性。 论文工作形成了一个基本的数据流分析框架j 1 阽o l 。在j t o o l 上实现了建立在 算法研究之上的冗余同步删除工具s y n c r e m o v e r 和数据竞争检测工具 r a c e c h e c k e r 。对这些算法实现的实验结果分析验证了算法的精度和有效性。 关键词：并发程序程序分析动态分析模型检测e s c a p e 分析数据竞争 p o i n t s t o 分析别名分析 一 中国科学技术大学博士学位论文 a b s a c t a b s t r a c t m u l t i t l l r e a d e dc o n c t e mp r o g r a m sb e c o m em o r ea n dm o r ei m p o n a n t ，w h i c hi sn o t o n l yac o m m o n ，e 踮y _ t o - u s ep m 野啪c o n s 讥l c t ，b u ta l s os u p p o r t se f n c i e n tp a r a l l e l c o m p u t i n g t h e d e s p r e a da d o p t i o no f m u l t i t h 础证e dc o n c u r r e n tp r o g r a m sh a sb r o u g h t n e w o p t i m i z a t i o no p p o r t u 撕t i e s a n d 锄a l y s i sp r o b l e m s a tt h es a m et i m e n e w r e q u i r e m e n t sd i f f b r e n t 疗o mc o n v e n t i o n a ls e q u e n t i a lp r o g m ma n a l y i sm e t h o d se m e r g e t h ec o n s e r v a t i v e a n a l y s i s o fc o n c u r r e n ts e m a l l t i c sa 1 1 da l i a si n f o m l a t i o n ( p o i m s - t oi n f o 咖a t i o n ) m a k ep r e v i o u sc o n c u r r e n tp r o g r 锄a n a l y s i sa i g o r i t m sa r ea l l 印p m x i m a t ea l g o r i t h m sw i ml o wp r e c i s i o n t h em a j o rw o r ko f t h i sd i s s e r t a t i o nf o c u s e s o nd e s i g n i n gp r e c i s ea n de 币c i e n ta l g o r i m m sf o rr e d u n d a n ts y n c h m n i z a t i o nr e m o v a l a n dd a t ar a c e c h e c k i n g i nm u l t i t h r e a d p r o g r 锄s t h e a l g o r i t h m sd e s i g np r e c i s e f l o w s e n s i t i v e ，c o m e x t s e n s i t i v ea l i 越 a n a l y s i s a 1 1 ds i m u l a t ei n t e r a c t i o n t e m p o m l r e l a t i o ne 丘 e c t t o i m p m v ep e r f o r n l a n c e ，t h et h e s i sp r o p o s e s a no b j e c t - b a s e dr a c e c h e c k e rw i mt h ec o m b i n a t i o n o f e s c 印ea l l a l y s i st oc o 娟n ec h e c k i n gs c o p e b e c a u s et h ea l i a si n f o m a t i o n8 丘 e c t st h eq u a l i t yo f a n a l y s i sa l g o r i t h mg r e a t l y i h e s e c o n dp a no fd i s s e n a t i o ni st h ea j i a sa l g o r i t h r nr e s e a r c hf o rc o n c u r r e n tp r o g r a m s t h e d i s s e r t a t i o nf i r s te x p l o r e st l l ee 疗 e c t so fd i 丘毫r e n td e s i g nf a c t o ri na na l i a sa l g o r i t t h e n p r o p o s e saf l o w - i n s e n t i v i e ，c o n t e x t s e n s i t i v ea l i a sa l g o r i t h r nf b rt h es p e c i n cl a n g u a g e a n dc o n c u r r e n ts t r u c t s b e s i d e sp m g r a r na 1 1 a l y s i s ，d y n a m i c 柚出y s i sa n dm o d e l c h e c k i n ga r ea 1 1 0 t h e rt w o e 矗色c t a n a i y s i sa p p r o a c h e s f o rs o 矗w a r e s 诅t i c a 1 1 a i y i s a n dd y n a m i ca n l a y s i sh a v e c o m p l e m e n ti nt h ep r e c i s i o n ，p e r f b 丌n a n c ea n df a u l tc o v e r a g e t h ed i s s e r t a t i o nd i s c u s s e s s o m ei d e ao ft h e i rc o m b i n a t i o n p r o g r a ma n a l y s i sa n dm o d e l c h e c k i n ga r eo r e nu s e dt o a n a l y z e t h es 锄e p r o p e r t 弘b u t t l l e r ei sal a c ko fr e s e a r c ho n t h e i r 印p r o p r i a t e a p p l i c a t i o nf i e l d s t h ed i s s e n a d o nc o m p a r e st l l e “om e t h o d sp r o sa i l dc o n s w i t ht h e e x a m p l e o fl i v e v a r i a b l e sa n a l y s i s ，w ei l l u s t r a t es o m ed a t a f l o wa n a l y s i sc a nb e t r a n s l a t e di n t oam o d e l c h e c k i n gp r o b l e m ，a l l dw e 触曲e rp r o v e 血ee q u a i 时o fa n a l y s i s r e s u i t s t h ew o r ko fn l ed i s s e r t i o nf o m l sab a s i cd a t a n o wa n a l v s i sf h m e w o r kj t b 0 1 a l l t h er c s e a r c h a l g o r i t i l i n s a r e i m p l e m e n t e d 谢t h s ”c r e m o v e r( a r e d u n d a n t s y n c o p e r a t i o n s r e m o v a l t 0 0 1 ) a n dr a c e c h e c k e r ( a s t a i cd a t r 觚ed e t e c t i o n t 0 0 1 ) t h e e x p e r i m e n t s r e s u l t so na l g o r i t h f ni m p l e m e n t 砒i o n j u s t i 母o u rc l a i m s k e y w o r d s ： c o n c u r r e n t p r o g r a m s ，p r o g m ma n a l y s i s ，d y n 锄i ca n a l y s i s ，m o d e l c h e c k i n 岛e s c a p ea n a l y s i s ，d a t ar 矗c e ，p o i n t s t oa n a l y s i s ，a l i a sa n a l y s i s i l 中国科学技术大学博士学位论文 致_ i 身5 致谢 在论文完成的时刻，回首攻读博士学位的五年时光，谨向我的导师陈意云教 授和张健研究员致以崇高的敬意和衷心的感谢。 陈老师严谨的治学态度、实事求是的学术作风、勤勉敬业的工作精神，不仅 教育我、影响我，更将对我今后的工作和生活产生深远的影响，使我终生受益。 同时，他开明的研究作风也允许我比较自由地选择感兴趣的研究课题，这是论文 得以产生的一个原因。 衷心感谢中科院软件所的张健研究员。张老师为我提供了在软件所的客座机 会。在两年客座期间，我不仅完成了大部分的论文工作，而且接触和了解到更多 的研究领域。张老师严谨的治学态度，渊博的学识和开放的研究思维令我终身难 忘，受益匪浅。 我要感谢在这五年里所有给过我支持和帮助的老师和同学们。感谢我在科大 学习期间和在软件所计算机科学实验室客座期间所有的同学，我们起讨论、研 究，共同度过了许多难忘的岁月。能够和各位在友好和谐、积极迸取的环境中一 起学习和工作也是我的荣幸。 感谢软件所的吴鹏同学，论文6 1 节包含了他的合作工作。 感谢s u n 公司的王健中先生和他的小组成员，和他们的讨论是论文4 5 3 节 和5 4 节产生的部分原因。 特别感谢杨琛。一直以来，我们分享所有的研究心得，经历生活中的每个欢 乐时刻。非常感谢你的无尽支持和信任。一切皆因有你而不同。 最后，谢谢父母的无限关爱。 i 中国科学技术太学博士学位论文 第l 章引言 第1 章引言 1 1 背景和动机 随着计算技术和网络技术的迅速发展，多线程并发程序得到了越来越广泛的应 用。现代体系结构大多具有多粒度并行和多级存储的特点，片上多处理器( c h i p m u l t i p r o c e s s i n g ，c m p ) 架构的出现( 例如：s 嘣n i a g a r a ( 0 l t r a s p a r c ) ，i b m p o w e r 4a n d5 ，i n t e lm o n t e c i t o ( d u a li n t a n i u m2 ) ) 以及多处理器架构上编译技 术的发展，使得高性能计算成为可能。与此同时，网络的广泛应用也带来了很多 固有的多事务结构如w e b s e r v e r 。对于这些应用，多线程比多进程有着更多的优 势：调度的开销较小可以更加方便的共享地址空间。因此为了实现高效并行计 算或是建立不同用户之间的交互，多线程成为广泛采用的程序结构。j a v a 、c # 这 样的网络编程语言的出现更加推进了并发应用。语言级的并发支持使得用户可以 方便的使用同步结构( s y n c h r o n i z e d 方法和块) 和同步原语对共享数据做安全操 作：存在同步操作的t h r e a d - s a f e 库( v c c t o r 类以及部分s w i n ga p i ) 保证用户可 以在多线程环境中安全的使用这些库提供的功能，编写并发程序变得更加简单和 安全了。 并发程序也带来了很多特定的优化和检错问题，这些问题多数和锁的台理操 作彳j 关。粗粒度的保守锁机制容易写出正确的代码但是会带柬不必要的锁操作 或是锁住不需要保护的数据而降低了并发度，进而导致性能较低。同步操作是多 线程程序一个较大的开销，对于多处理器系统，它意味着流水线的断流、相关联 的c a c h e 缺失以及总线的锁定，所有线程必须等待同步结束。因此冗余同步的删 除就成为一个重要的优化问题。另一方面，高度优化的细粒度锁机制有很好的性 能表现，但是这种程序可能会缺乏稳定性，容易出错，比如保护不够就会引起数 据竞争( d a t a r a c e ) ，当同步涉及到多个锁时由于获得锁的顺序而引起死锁 ( d e a d l o c k ) 问题。由于这些问题分析复杂、错误表现隐秘、难以测试，所以大部 分还未能很好的解决。 传统的程序分析针对顺序程序，通过对程序执行状态的抽象和模拟静态的计 算程序点具有的程序属性。对于并发程序来说，程序分析的一个主要困难在于准 确模拟线程交互的影响【1 】，简单的模拟所有交互具有指数级的复杂度，因而建立 有效的抽象和分析算法描述这些影响是并发程序分析的研究重点。静态分析的另 一个不可判定性【2 】来自于对变量值和别名信息的判断【3 】。由于实际的程序分析算 法都是“- 完备的近似算法，分析精度不高，存在很多假错误( f a i s ep o s i t i v e s ) ，田 中国科学技术大学博士学位论文 第1 章引言 此高精度的并发程序分析算法研究很有意义。 精确的分折算法需要很好的设计并且通常会带来时间和空间上的巨大开销， 一个可扩展的有效分析还需要在精度和性能之问取得平衡。设计适合分析问题的 高效算法或是结合其他分柝方法，比如动态分析、模型检测，提高整体分析效率 是算法设计的另个重要研究课题。 1 2 论文工作的内容 高精度的并发程序分析算法和高效别名算法是我们的研究重点。论文工作的 第部分围绕并发程序中冗余同步操作删除和数据竞争检测问题提出了高精度的 分析算法。由于别名分析精度对程序分析精度有极大影响，这两个算法都设计了 高精度的流敏感、上下文敏感别名分析。此外通过静态模拟交互时序进一步提高 了分析精度。为提高分析效率，论文还提出了以对象为中心，结合e s c a p e 分析缩 小检测范围的竞争检测算法。 从两个并发分析问题分析经验中，我们发现精确的别名算法虽然提高了分析 精度，也带来了时间和空间上的巨大开销。要提高整体分析质量还需要设计适合 分析问题、在精度和性能之闻取得平衡的别名算法。因此论文工作的第二部分是 并发程序分析中的高效别名算法。别名分析算法有很多设计要素，对这些要素的 选择直接决定了算法的精度和开销。在并发程序的环境下或是针对不同的分析问 题，这些设计要素的影响是不同的。如何选择这些要素提高算法实现效率是我 们关心的。论文首先探讨了不同设计要素对别名算法质量的影响，进而针对分析 语言和并发结构设计了一种流不敏感、上下文敏感的别名算法。 除了程序分析，模型检测是另一种有效的分析工具。它们往往可以检测相同 的属性，分析过程也有相似之处，但是几乎没有对这两种方法适用的分析范围的 研究。我们对比分析了模型检测和程序分析各自的优缺点并探索两种方法的结合 方式。论文还以活跃变量分析为例说明了某些数据流分析问题可以转换为模型检 测问题，并且证明了二者在分析结论上的等价性。 程序分析和模型检测都需要设计算法或是程序抽象，因此分析成本昂贵、很 难适用到大规模的实际应用。多数工业晁使用的分析工具是动态分析工具。它们 可以在分析成本不高的情况下得到准确的分析结果。静态程序分析和动态分析在 分析精度、性能和覆盖率上有很好的互补性，论文针对竞争检测讨论了它们相互 结合的一些思路。 论文工作形成了一个基本的数据流分析框架h 0 0 l 。j t 0 0 1 由m 盯的一个用 j a v a 编写的j a v a 编译器f l e x 【3 8 】改造而成，它接受字节码作为输入，可以作为一 个基本的分析框架对很多数据流问题做上下文敏感和流敏感的分析。j t o o i 的框架 中国科学技水大学博士学位论文 第l 章 l 百 组成如图1 1 所示：字节码由类装载器加载，经过预分析，形成元组中间表示、调 用图、控制流图等信息。根据分析目标过程内分柝针对中间表示，形成相应的 方法摘要( s u m m a r y ) 。这些摘要信息和别名信息被跨过程分析和跨线程分析使用， 在上下文环境中形成全局的数据流分析结果。最后，分析结果被输出给用户。 图1 1j 1 0 0 1 分析框架 我们结合j t o o l 框架和算法研究实现了两个分析工具：s y n c r e m o v e r 用于删除 保守的冗余同步操作：r a c e c h e c k e r 用于检测由于缺乏足够的锁保护而导致的竞 争错误。对这些算法实现的实验结果分析验证了算法的效率和精度。 1 3 论文组织与主要贡献 论文后续章节组织如下：第2 章是并发问题和分析方法的背景介绍；第3 章和 第4 章分别是冗余同步删除和数据竞争算法研究；第5 章是并发程序中的别名算 法研究：第6 章是程序分析和模型检测的比较分析和等价性研究。 中国抖学技术大学博士学位论文第l 章引言 论文的主要贡献有四部分： ( 1 ) 设计并实现了一个高精度的冗余同步操作的静态删除算法。 ( 2 ) 设计并实现了一个精确有效的、以对象为中心，结合e s c a d e 分析缩 小检测范围的静态竞争检测算法。 ( 3 ) 提出了一种面向并发结构和j a v a 语言的别名分析算法并且从语义和 运行特征提出别名算法的优化实现。 ( 4 ) 结合程序分析和模型检测的经验，初步探讨了程序分析和模型检测 各自适用的分析范围，以活跃变量分析为例说明了某些程序分析中 的数据流分析问题可以转换为模型检测问题，证明了两种方法在分 析结论上的等价性。 中国科学技式大学博士学位论文 第2 掌井发问题和分析方法 第2 章并发问题和分析方法 虽然多线程提供了一个概念上简单的并发抽象，多线程程序的编写依然是一项 挑战性的工作。线程之间通过同步原语发生各种交互，一方面程序员利用这些交 互实现预期任务。另一方面对它们的不当操作也很容易让程序发生一些不可预知 的严重后果。线程交互使得多线程程序在不同的调度模式下出现不同的执行结果， 通常的测试方法很难对程序做彻底分析。这些都促使人们研究更加精确有效的并 发分析方法。 多数并发研究集中在同步结构带来的程序错误检测，如数据竞争、死锁。还有 一些研究针对多线程程序的优化问题。它们有些是多线程程序特有的优化问题， 比如锁结构的优化；也有一些是现有程序优化在并发结构下的调整。 本章首先讨论论文工作针对的两个问题：e s c a p e 分析和数据竞争问题，接着介 绍几种现有的分析方法。由于论文工作主要集中于程序分析和别名算法研究，我 们会重点介绍程序分析和别名算法的一些基本术语和问题。 2 1 并发问题 并发问题按照分析用途分为两类：一类是错误检测：一类是程序优化。数据竞 争和死锁问题是两个经典的并发错误，对它们的研究比较广泛。传统优化技术直 接应用到多线程程序中会出现新的问题：优化可以重排对共享数据的访问顺序， 这种熏排可能对其它并发线程产生影响。一种解决方法是推广标准的优化方式， 刚使在宵足享数掘访问的并发程序中也能保证对程序做安全转换。另一种方法足 确保所做优化保持原程序的语义：首先识别不与其他线程交互的程序区域，然后 只对这些区域做优化。这种方法需要一个预先的跨线程分析而决定哪些语句之 间会发生交互也并不简单。在另一方面，多线程结构的出现也带来了新的优化机 会，例如：通信优化，路障优化，同步优化( 锁删除、锁粒度细化、e s c a p e 分析) 等。 2 1 1 e s c 印e 分析 e s a c a p e 分析最初应用在虚拟机的优化中：分析鉴别出那些逃离当前方法的对 象( 又叫做e s c 印e 对象) ，对那些没有逃离方法的对象( 又叫做m e t h o d 1 0 c a l 对 象) 可以进行栈上分配，从而减轻垃圾收集器的回收负担。e s c a p e 分析应用于并 发程序中可以用来做同步结构的优化【4 ，5 】：分析鉴别出那些在程序执行中除了创 建线程，不能被其他线程访问的对象( t l l r e a d 1 0 c a l 对象，t h r e a d s a f e 对象) 。对 中国科学技术大学博士学位论文 第2 章并发问题和分析方法 t l l r e a d 1 0 c a l 对象的的同步操作是不必要的冗余操作，可以安全删除。此外，还有 少量e s c a p e 分析【6 】鉴别逃离当前分析区域的对象，应用的优化为特定区域上的对 象分配。 我们的分析目标是减小同步开销，通过对传统e s c 卸e 分析的扩展找到那些可 以删除的同步操作。不论应用于什么样的分析目标，e s c a p e 分析的基本工作都是 利用别名分析找到那些通过显式隐式赋值发生状态改变的e s c a p e 对象。 2 1 2 数据竞争 多线程并发程序中的数据竞争( d a t a - r a c e ) 发生在两个或多个线程访问了同 个内存位置而没有时序限制，并且至少有一个是写操作。竞争有时是共享数据和 通讯的一种方式( b e n i g nr a c e ) ，但多数情况下属于程序错误( r a c ee r r o r ) 。存在竞争 错误的程序在相同的输入和相同的同步执行顺序下也可能出现不确定的执行结 果。由于竞争问题分析复杂，表现隐秘难以调试，所以竞争的自动检测工具非 常有意义。 区分良性竞争和竞争错误可以极大提高分析质量，【7 】中总结了并发程序中良 性竞争的主要来源： 共享信道一些程序使用共享数据结构，比如信道在线程之间传递数据。 对信道的访问是需要同步，但是对传输数据的访问则不必同步。由于不 能区分信道结构和在信道上传输的数据，分析工具总会把对线程间消息 的操作当作竞争错误报告。对于这种模式。手工添加一些注释会帮助检 测工具消除掉很多假错误报告。 常量值重写一些程序对共享内存位置用常量值不断重写，这些写操作 不会影响程序行为。 缓存程序中经常会用到缓存技术。一些缓存具备弱语义：同一个对象如 果在缓存中有多份拷贝或是没有拷贝也不被认为是错误。一些程序利用 了这一点，审慎的消除一些缓存操作中的同步，提高程序性能。 推迟初始化一些程序在使用变量前检测内存位置是否被初始化，如果没 有，就用一个预先的固定值初始化该变量。推迟初始化是很常用的优化， 它可以有效的减少资源消耗。如果初始化的值是固定的并且不被改变，那 么对这个共享变量的访问就不需要同步。 异步通知很多程序通过更新共事内存位簧来异步通知其他间歇的轮询这 个位置的其他线程。什么时候读到这个变化并没有决定性的影响。 时间戳一些程序维护一些全局计数值或是时间戳。读取这些值的线程总 是在观察一个固定的增长，并且总能在某个最小时间内观察到这种更 6 中国科学技术大学博士学位论文第2 章并发问题和分析方：；圭 新。对这些值的访问是不需要同步的。 统计值很多程序维护一些内部的统计值，比如池的大小、传输的字节 数、预计的延迟等，用来辅助性能决策。通常这些不正确的统计值不会 影响程序的正确性，即使有小的偏差也不会有很大影响。对这些统计值 的读写是不用同步的。 正如论文4 5 2 节讨论的那样，程序的执行语义还要依赖底层的内存模型。这 些良性竞争模式只是针对典型的j a v a 环境 3 7 】，而未必在所有的j a v a 内存模型下都 安全。基本上多数推迟初始化、常量值重写和异步通知在某些多处理器内存系统 或是激进优化编译器中【8 】都能导致不正确的行为，我们在2 2 4 节会讨论一些它们 出错的情况。 2 2 分析方法 为了减小同步开销或是消除数据竞争，一些方法希望从源头阻止它们的出 现，比如改良同步原语的动态实现，减小同步代价；设计更好的语言和类型系统 确保程序中不会出现数据竞争。但是面对大量的遗留代码，人们更多的是采用检 测的方法。检测方法有程序分析、模型检测、动态分析和模式匹配。它们在使用 难易、分析精度、性能和覆盖率上各有特色。 2 2 1 程序分析 程序分析起源于传统的编译优化技术，例如数据流分析，抽象解释，类型推 导，约束求解。它通过对程序执行状态的抽象和静态模拟计算程序点具有的程序 属性。a l e xa i k e n 认为：“程序分析是一个特殊的定理证明器，它试图得到关于程 序的一些有用信息，这些信息比简单语法属性复杂，但是又没有完全的程序验证 那样复杂”。随着机器性能提高和分析算法的广泛研究，程序分析从最初的优化 技术扩展到程序理解、测试、调试和验证工具当中。由于考虑了所有的执行空 间，程序分析的方法在错误查找时有很高的覆盖率，但是对运行状态的保守估计 会导致很多假错误，在多线程并发语义情况下这个问题更加突出。 为了模拟执行、收集数据流信息，程序分析首先需要构造程序的控制结构 9 ，1 0 】。如果分析局部于单个过程，就是过程内( i n 仃a 巾r o c e d u r a l ) 分析。过程内部 的控制流可以抽象成一个控制流图( c o n t r o l 矗o w 酎a p h ，c f g ) ，c f g 的节点代表 一条语句或是语句组合而成的基本块，边表示控制在语句之间的转换，节点首尾 相连形成有向图。如果分析考虑过程调用语句，就是跨过程( i n t e r - p r o c e d u r a l ) 分 析。过程间的控制流动可以用跨过程的控制流图( i c f g ) 表示，i c f g 由一些互连 的c f o 组成，调用边连接调用节点到被调用过程的入口，返回边连接被调用函数 7 中国科学技术大学博士学位论文 第2 章并发问题和分析方法 的出口到调用过程。过程之间的调用关系还可以另一种简化的调用图( c a l lg m p h ) 表示。调用图中节点表示过程，边表示调用关系。我们的两个分析问题广泛采用 了这些成熟的控制结构并针对线程抽象做了一些适当扩展。 线程是独立的并发控制流。j a v a 中的线程有三种：( 1 ) 主线程：代表程序的开 始运行，也就是由m a i n 方法开始的控制流，这是一个只有一个实例的线程。( 2 ) 运行( n m ) 线程：由线程对象调用n m ( ) 开始的控制流。程序分析可以通过线程对象 分配和对应的r u n 方法确定运行线程，但是运行线程在运行期的实例数目通常很 难或者根本无法在编译期决定。如果一个运行线程有多个分配位置或是同一分配 位置被执行多遍，那么这些线程实例都被假定是并发执行。为了使分析过程更加 清晰，我们用不同的线程节点区分同一线程类的多个分配位置；对于循环体或递 归结构中同一分配位置的多次执行，我们假定存在两个线程实例，这种假设保证 冗余同步删除和竞争分析的结果同样适用多线程的情况。( 3 ) 初始化( i n i t ) 线程： j a v a 中类的初始化隐式调用带来的控制流。和主线程、运行线程不同，初始化线 程不是用户线程，它由虚拟机调用，发生在首次创建类的实例或者首次调用类的 静态方法之前，它的主要工作是对类的静态域做初始化。和主线程一样，初始化 线程也是唯一的。我们的分析假定每个类的初始化线程由主线程发起，但是由于 类的初次使用常常不能被归为某个特定线程，所以无法确定初始化线程对其他线 程的影响。 程序分析沿着控制路径传播信息，形成每个程序点的状态。这些数据信息根 据分析问题定义和收集并随着程序执行发生改变，它们基本上可以表示成一些内 存单元的值或是由此产生的等价关系。数据信息随着程序规模的增大而加大，所 以一般需要对数据做适当抽象。定义分析问题、采用合适的数据结构表示和收集 信息是程序分析的首要步骤，我们的两个分析问题也都是从这里开始解决的。 理想的程序分析具有可靠性( s o l h l d n e s s ) 和完备性( c o m p l e t e n e s s ) ：( 1 ) 可靠性指 的是检测工具在程序有错误时必须报告错误。这个定义并不是要求报告全部错 误，例如：一个竞争检测工具即使没有报告由于其他竞争导致或蕴含的竞争错误 也依然是可靠的。( 2 ) 完备性指的是检测工具只报告真实错误，没有假错误。在保 守分析中，可靠性是容易保证的；但是对分析复杂度和可计算性的研究显示并发 程序同步结构的精确分析是不可行的。【l 】显示对没有过程和递归的r c n d e z v o u s 形 式的同步程序，如果考虑所有可能的交互和执行路径，同步分析是个n p c o m d l e t e 问题。 1 1 对带过程程序的扩展分析显示任何上下文敏感、同步敏感的分析是不 可判定的。因此，实际的并发分析工具都是可能覆盖所有的错误但是会有假错误 的近似算法。由于静态检测是保守分析，我们一般用分析集合的大小衡量分析精 度，一般来说精度越大，分析集合越小。比如在别名分析中，最保守的情况是所 中国科学技术大学博士学位论文 第2 章并发问题和分析方法 有变量互为别名：变量的p o i n t s t o 集合和p o i m e d 勘b y 集合越小，别名分析的精度 就越高。当然分折有时并不完全可靠1 ，这种衡量也可能有不准确的地方。比如竞 争检测中，可能出现检测不了的错误而整体的检测数目却很少。但是一般认为这 种情况还是很少出现的。图2 1 是一个程序分析的检测集合示意。 国t r “ 图2 1 程序分析集合 并发程序分析【1 2 ，1 3 】的一个主要困难在于准确模拟线程交互对数据流分析的 影响。这包括了控制原语形成的控制流交互以及各种隐式显式赋值带来的共享数 据交互。这些交互可能直接或间接的影响到分析结果。对于顺序程序，沿着控制 路径传播信息是合理的，因为每条语句通常只有少数几条控制后继。但对于并发 程序，每条语句的直接后继包括了几乎所有其他并行线程语句，这种直接传播、 模拟所有交互会具有指数级的复杂度。因此首要的问题就是如何减少必须考虑的 路径数目，建立精确刻画线程交互的抽象和分析。 控制流分析一种方法是分析程序中同步结构的使用，找到不会并发执行的任 务区域，然后移出这些区域之间的连接边。这种分析的特点是依赖特定的同 步结构。例如针对并行f o r t r a n 语言中的p o s “w a i t 结构的分析 1 4 ，1 5 ，1 6 】 ( p o s t 、v a i t 结构常常用在访问稠密矩阵的并行循环中，程序使用p o s t 、v a i t 结 构保证一次并行循环迭代中对某个数组元素写发生在其他迭代对该元素读之 前。) ，a d a 的r e n d e z v o u s 结构分析【1 7 ，1 8 ，1 9 。以及j a v a 这样的w a m l o t 母 结构的分析 2 0 ，2 1 】。这些算法的基本思想是将每个阻塞动作( 例如w a i t 或 a c c e p t ) 和对应的其他线程中的触发动作( 例如p o s t 或n o t i f y ) 配对。分析使用 这些信息就可以决定触发动作之前的语句一定会在阻塞动作之后的语句前执 行。 加大分析粒度减小分析复杂度的另一个办法是将线程中相邻指令形成大的分 析块，将这些分析块作为跨线程分析的分析单元 2 2 ，2 3 ，2 4 ，2 5 】。典型的方法就 是将和其他线程不交互的指令合并在一起，在这种情况下，加大分析粒度不 1 这种不可靠可能来自忽略掉的程序抽象或是假定的内存模型。实际上内存模型会让并发程序分析的可靠 性难以判断。我们将在第4 章针对竞争问题讨论分析算法不可靠的来源以及内存模型对分析结果的影响。 中国科学技术大学博士学位论文 第2 章并发问题和分析方法 会影响分析结果。由于交互通常发生在不同线程访问同一数据的情况下，数 据引用让决定哪些指令会和其他线程交互变得极为复杂。一种方法是在分析 的同时插入别名分析决定指令会发生的交互【2 6 ，2 7 】；另一种方法是使用预先 的别名分析结果找到这些交互指令，比如一个不考虑指令交互的流不敏感分 析。此外，如果程序采用特殊的结构化的控制结构，例如并行循环体，并发被 限定在程序的一个小范围中，也可以应用非常精确的分析。 基于冲突的分析基于冲突的分析将分析粒度最大化它们以线程作为分析 单位，考虑这个线程和所有其他线程的交互。被抽取的分析信息从一个线程 的结束处流向所有其他并行线程的开始处。【2 8 的研究表明对于标准的位向量 分析( 例如：活跃变量分析、到达点定义) ，这种方法非常高效而且精度和对 所有的交互明确分析的算法相近。对于更复杂的分析例如p o i m s - t o 分析，基 于这种思想的算法【6 ，2 9 】由于过分的估计交互影响，因此会损失部分精度。 我们的分析是以线程为分析单位的，没有考虑共享数据带来的隐式交互对线程控 制流和数据流信息的影响，比如：线程t 1 ：i f ( g l = = 1 ) t 1 1 e n e l s e a c c e s s9 2 s ”c ( 9 2 ) 和线程t 2 ：i f ( g l = = 1 ) t l l e n a c c e s s9 2 s y l l c ( 9 2 ) ，我们不会考虑由于对全局量9 1 的共 享而对t 1 和t 2 中全局量贮的访问同步操作的影响，分析总会记录t l 和t 2 中的 9 2 访问同步事件。虽然【1 2 】指出这种保守分析对别名分析影响较大，但是对于损 失的精度并没有确定的结论。此外，精确分析必须有一个预先的、辅助的别名分 析找到那些访问同一内存位置的指令，才能刻画这些指令的混合效果。动态内存 分配、线程创建、对象引用和方法调用会使这个确定交互集合的过程更加复杂。 我们的分析部分考虑了控制原语对分析问题的影响，匹配了显式交互原语s t 础和 j o i n 形成的控制顺序。对于w a i t n o t 姆结构，无论w a i t ，n o t i f y 以什么样的顺序执行， 唤醒有没有被丢失，n o t i 句前的事件一定在w a i t 后的事件之前发生，但是由于这对 原语很少出现、对两个分析问题影响不大，所以我们没有做它们之间的匹配。对 于w a i 妇o t i 母a l l 结构，由于无法静态确定获得锁的等待线程，我们也没有做确切的 控制匹配。 影响并发程序分析精度的另一个来源是对别名信息的判断。即使是顺序程 序，别名信息的精确求解都很困难，在并发程序中，它还和交互信息互相影响， 加大了分析难度。 别名分析和p o i n t s - t o 分析是同一问题的不同表述，p o i n t s t o 分析指静态决定引 用指向的内存位置，由于很多时候希望知道两个变量表达式是否指向同一个位 置，所以又叫做别名分析。如果某个变量可以从另一个变量通过域访问或解引用 得到，那么我们就说这两个变量表达式互为别名。多数情况下的别名分析计算的 是m a y 信息，也就是说两个变量表达式是否可能在某条执行路径上互为别名。在 1 0 中国科学技术大学博士学位论文 第2 章并发问题和分析方法 一些特殊情况下需要计算m u s t 信息，也就是说两个变量表达式是否在所有的执行 路径都互为别名。除非特殊说明，论文中所讨论的都是m a y 别名信息。 别名分析自身是一种特殊的数据流分析，同时也是多数数据流分析问题的基 础。它的分析质量直接影响了程序分析的精度和性能，没有精确的别名分析，就 无法提高依赖分析、数据流分析的精度，也就不能做更多优化、调度以及自动并 行化的工作。数据的动态分配，别名信息在控制流上的互相影响使得精确的别名 分析复杂度很高。并发的程序结构中，线程的动态分配和交互更加大了分析的难 度。过去的2 0 年产生了很多的别名算法。第5 章详细探讨了不同设计要素对别名 算法质量的影响，精度和性能之间的平衡以及如何为并发程序分析设计别名算 法。别名算法最重要的两个设计要素是流敏感度和上下文敏感度：流敏感分析沿 着控制路径计算每个程序点的状态，流不敏感分析则将程序语句看作没有执行顺 序的集合从而为整个程序计算统一的分析结果；跨过程的程序分析中如果区分不 同的调用上下文信息，就是上下文敏感分析，反之则是上下文不敏感分析。我们 在对两个并发问题研究中，为了提高分析精度，都采用了昂贵的流敏感和上下文 敏感算法。 2 2 2 模型检测 模型检测( m o d e lc h e c k i n g ) 的基本思想是状态空间的穷尽搜索。它在硬件设 计【3 0 】、通信协议【3 1 】、实时进程 3 2 】的验证方面取得过很大的成功，近年来被广 泛地应用于程序分析方面。其基本过程是先将程序抽象成有限状态迁移系统，用 时序逻辑描述程序应满足的性质；然后通过状态空间搜索检测属性是否得到满 足。 由于对线程及其运行环境抽象的困难，并发程序的模型检测应用起来很困难 3 3 ，3 4 】。但是程序分析和模型检测还是可以检测一些相同的属性，分析过程也有 相似之处，而且在实际应用中还可以互相结合。论文在第6 章针对这两种方法各 自的优势，相互结合的思路和某些验证属性上结论的等价性做了简单探讨。 2 2 3动态分析 纯动态分析不访问程序代码，依靠观察插装( i n s t m m e n t ) 警序产生的事件流分 析程序性质。根据分析发生的时期动态分析又分为o n t h e n y ( 运行中) 分析和 p o s t m o n e m ( 运行后) 分析。动态分析在运行期针对确定的可执行路径检测，拥 有变量和别名的准确信息，因而是一种精确的检测方法。但是多数动态方法对检 测对象往往不加筛选就做插装，监测代码会占用很多的运行时间，“基本都要花 费原有程序开销的3 x 到3 0 ) ( ， 3 5 】。此外，对高层中间表示所做的过多插装还会改 中国科学技术大学博士学位论文 第2 章并发问题和分析方法 变原程序的执行。 动态方法固有的只能检测特定执行，因此和程序分析相比，它会出现更多的 f h l s en e g a t i v e ( 1 1 1 1 d e 玳p o n 漏报) ；一般的动态方法都是不可靠分析，有的动态分 析也会产生假错误( o v e r r e p o n 误报) 。图2 2 是动态分析结果分布示意。 图2 2 动态分析集合 动态分析由于了解运行值可以在分析成本不高的情况下得到准确的分析结 果；但是它的分析结果往往依赖特定的输入，调度，执行路径。这个问题对于并 发程序更加突出。静态分析克服了这个缺点，但是保守抽象会产生很多的假错 误，低精度的静态分析缺乏实用性，而精确的静态分析又都需要很好的设计。一 个很有希望的解决途径是将两种技术结合起来做混合分析，比如说在竞争检测中 利用静态分析指导和限定动态检测的范围。在4 5 3 节我们会进一步讨论混合分 析检测数据竞争的思路。 2 2 4 模式匹配 静态分析和动态分析的代价总让人望两却步，既然程序是程序员开发的并且 很多时候会遵循一定的开发模式，所以人们希望能从模式上对检测错误进行识 别。错误模式的识别是对代码行为的简单匹配，分析效果会随着程序类型以及经 验模型波动，并最终受到别名、堆抽象精度的影响。但它是对精度要求不高的分 析工具的补充，对于特殊模式还能够提供有效识别。比如2 1 2 节介绍的很多良性 竞争，如果不采用特定的模式匹配或是用户不提供注解将很难识别。 3 6 是个采用 模式匹配的分析方法，这个粗略分析产生的假错误比率被控制在