（计算机软件与理论专业论文）基于即时编译器的java语言同步优化研究.pdf

摘要 摘要 随着新兴并行体系结构的普及，主流应用程序出单线程向多线程转变的趋势 越来越明显。但是，生成高效健壮安全可靠的并行程序并非易事，其中以多线程 间同步策略的设计和实现最为关键。实现多线程间同步的一种主要方式是对共享 数据加锁，锁能安全、简单、有效地实现对共享数据的保护，但锁操作本身的开 销非常大，而且由于其过于悲观保守，在实际应用中会出现大量冗余的锁操作， 这样对整个程序的运行效率会产生极大的负面影响。 为了弥补锁同步的不足之处，本文介绍了多种锁同步的优化策略，重点提出 两种基于锁耦化的同步优化算法，并在丌源的j a v a s e 项目h a r m o n y 上实现这两 种算法。围绕锁同步的优化，本文主要探讨并完成以下工作： l 、在实际的j a v a 虚拟机h a r m o n y 中设计实现一个插桩取样系统 设汁丌发这样的插桩取样系统，旨在收集运行时信息，例如，各种同步操作 在运行过程中实际执行的次数等，帮助调试、分析和评估各类同步优化算法。 2 、在h a r m o n y 中实现s t o o d l e y 等提出的基于锁粗化的同步优化算法1 2 1 i s t o o d l e y 等提出的算法能删除过程内的嵌套同步操作中的内层同步操作以 及合并过程内的相邻同步操作，以减少同步操作的数量。通过在h a r m o n y 中设 计实现它，可以为提出并实现新的同步优化算法提供思路。 3 、提出并实现一种利用即时编译器外提循环内同步操作的过程内同步优化 算法 该算法能将循环中的部分同步操作外提至循环外，大量减少运行时实际执行 的同步操作数，充分挖掘了过程内的同步优化机会。笔者在h a r m o n y 的即时编 译器中以高级中间表示上的优化遍形式实现该算法，实验结果表明它对 s p e c j b b 2 0 0 5 吞吐量的提高可达到1 3 。 4 、提出并实现一种过程间的同步方法优化框架 该优化框架旨在分析出无须同步的同步方法调用点并将其改成对相应同步 方法的非同步版本的调用。笔者在h a r m o n y 中实现了基于该框架的一个算法， 实验结果表明使用该算法对s p e c j b b 2 0 0 5 吞吐量的提高可达到2 o 。 关键词：j a v a 即时编译器多线程锁同步操作同步优化 a b s t r a c t 一一。一 a b s t r a c t a l o n g w i t ht h ea d v e n ta n dp o p u l a r i t yo fn e wp a r a l l e la r c h i t e c t u r e ，i ti sm o r ea n d m o r eo b v i o u st h a tt h ef o r mo fm a i n s t r e a ma p p l i c a t i o n ss h i f tf r o ms i n g l e t h r e a dt o m u l t i t h r e a d s h o w e v e r , i ti sw e l l k n o w nt h a ti tn o te a s yt og e n e r a t ee f f e c t i v e ，s t r o n g ， s a f e ，a n ds o u n dp a r a l l e la p p l i c a t i o n ，a n dt h ed e s i g n a n di m p l e m e n t a t i o no ft h e c o n c u r r e n ts y n c h r o n i z a t i o ns t r a t e g yi st h ek e yp r o b l e m o n eo ft h ep r i m a r yw a y st o i m p l e m e n ts y n c h r o n i z a t i o nb e t w e e n m u l t i t h r e a d si st ol o c kt h es h a r e dd a t a l o c kc a n p r o t e c tt h es h a r e d d a t as a f e l ys i m p l ya n de f f e c t i v e l y , b u tt h eo v e r h e a do fl o c k o p e r a t i o ni t s e l fi sh i g ha n di nr e a l i s t i ca p p l i c a t i o n s ，t h e r ea r e ag r e a td e a lo fr e d u n d a n t l o c ko p e r a t i o n sd u et oi t sp e s s i m i s ma n dc o n s e r a t i o n ，s ot h a tt h ew h o l ep e r f o r m a n c e w i l lb er e d u c e do b v i o u s l y t om a k eu pt h es h o r t a g eo ft h es y n c h r o n i z a t i o nm e c h a n i s mo fl o c k ，w ep u t f o r w a r dt w os y n c h r o n i z a t i o no p t i m i z a t i o na l g o r i t h m sb a s e d o nl o c kc o a l e s c e n c e ，a n d i n t r o d u c es o m eo t h e rs t r a t e g y st oo p t i m i z et h es y n c h r o n i z a t i o nm e c h a n i s mo fl o c ki n t h i sa r t i c l e w ea l s oi m p l e m e n tt h et w on e wa l g o r i t h m si nt h ej u s t i n t i m ec o m p i l e r o fh a r m o n yp l a t f o r m f o c u s i n go nt h eo p t i m i z a t i o no fs y n c h r o n i z a t i o nm e c h a n i s m o f l o c k t h i sa r t i c l em a i n l yd e p i c t sa n dd i s c u s s e st h ef o l l o w i n gw o r k s ： 1 d e s i g na n di m p l e m e n ta ni n s t r u m e n t a t i o n & s a m p l es y s t e mi nar e a l i s t i c j a v av i r t u a lm a c h i n eh a r m o n y w ed e s i g nt h ei n s t r u m e n t a t i o n & s a m p l es y s t e mi no r d e rt oc o l l e c tr u n - t i m e i n f o r m a t i o ns u c ha st h ee x e c u t i n gt i m e so fv a r i o u ss y n c h r o n i z a t i o no p e r a t i o n s ，e t c t h i si n f o r m a t i o nc a nh e l pd e v e l o p e r s s y n c h r o n i z a t i o no p t i m i z a t i o na l g o r i t h m t od e b u g ，a n a l y s ea n da s s e s st h ee f f e c to f 2 i m p l e m e n ts t o o d l e y ss y n c h r o n i z a t i o no p t i m i z a t i o na l g o r i t h mb a s e d o n l o e kc o a l e s c e n c ei nh a r m o n y s t o o d l e y sa l g o r i t h mc a nr e m o v et h ei n n e rs y n c h r o n i z a t i o no p t i m i z a t i o n so f n e s t e ds y n c h r o n i z a t i o no p t i m i z a t i o n sa n du n i f yt h es e q u e n t i a lf o r m so fr e p e t i t i v e s y n c h r o n i z a t i o nw i t h i np r o c e d u r es ot h a tt h en u m b e r o fs y n c h r o n i z a t i o no p t i m i z a t i o n s c a nb er e d u c e d d e s i g n i n ga n di m p l e m e n t i n gt h ea l g o r i t h mi nh a r m o n ym a yh e l pt o p r o v i d en e w i d e a so fb e a e ra l g o r i t h m 3 p u tf o r w a r da na l g o r i t h mt oh o i s ts y n c h r o n i z a t i o no p e r a t i o n sf r o ml o o p s w i t hj u s t i n t i m ec o m p i l e ra n di m p l e m e n t ei ti nh a r m o n y i i i ab s t r a c ! 一一一一_ _ ，- _ - - _ _ - - _ - - - _ _ _ - - - _ - _ - _ _ _ _ _ - _ _ _ 一 t h ea l g o r i t h mh o i s t ss y n c h r o n i z a t i o no p e r a t i o n sf r o ml o o p s ，g r e a t l yd e c r e a s e s y n c h r o n i z a t i o no p e r a t i o n sa t r u n t i m ea n dt h eo p t i m i z a t i o no p e r t u n i t i e sw i t h i n p r o c e d u r e a r ef u l l ye x p l o i t e d w ei m p l e m e n tt h ea l g o r i t h ma sa l lo p t i m i z a t i o np a s so f h a r m o n y sj u s t i n t i m ec o m p i l e r t h ee x p e r i m e n tr e s u l t ss h o wt h a ti tc a l li m p r o v e t h et h r o u g h p u t so fs p e c j b b 2 0 0 5b y1 3 4 p u tf o r w a r da no p t i m i z a t i o nf r a m e w o r kf o rs y n c h r o n i z e dm e t h o d t h ep u r p o s eo ft h ef r a m e w o r ki st of i n do u tt h es y n c h r o n i z e dm e t h o dc a l l s i t e s w h i c ha r eu n n e c e s s a r yt oc a l ls y n c h r o n i z e dm e t h o d sa n dm a k et h e mc a l l t h e n o n s y n c h r o n i z e do n e s w ei m p l e m e n ta l la l g o r i t h m b a s e do nt h ef r a m e w o r ki n h a r m o n ya n dt h ee x p e r i m e n tr e s u l t ss h o wt h a t i tc a ni m p r o v et h et h r o u g h p u t so f s p e c j b b 2 0 0 5b y2 0 o - 4 k e y w o r d s ：j a v a ，j u s t i n t i m ec o m p i l e r , m u l t i t h r e a d s ，l o c k ，s y n c h r o n i z a t i o n o p e r a t i o n ，s y n c h r o n i z a t i o no p t i m i z a t i o n i v 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文口 保密的学位论文在解密后也遵守此规定。 作者签名：塾蕴。塞 卅年彳月1e t 第l 章绪论 第1 章绪论 由于功耗和散热问题，提高时钟频率不再是提升处理器性能的主要可行方式 川。一些新兴的并行体系结构不断产生并普及，主流应用程序由单线程向多线程 转变已经是大势所趋。结构良好的并行程序可以受益于处理器以及线程数目的持 续增长，但是，生成高效健壮安全可靠的并行程序并非易事，其中以并发同步策 略的设计和实现最为关键。协调多个线程的同步策略的好坏直接影响程序的性能 和j 下确性，是提高程序生产率的瓶颈。鉴于这种情况，一系列围绕同步机制的研 究随之展开。实现多线程间同步的一种主要方式是对共享数据加锁，锁是一种悲 观保守的同步控制方式，能安全、简单、有效地实现对共享数据的保护，但锁操 作本身的丌销非常大，而且由于其过于悲观保守，在实际中会出现大量冗余的锁 操作，这样对整个程序的运行效率会产生极大的负面影响。本文以j a v a 语言为 例，着眼于优化改进j a v a 程序中的锁同步调用，以提高程序的运行效率。 本章首先对所需解决的问题作出详细的介绍，接着对当前国内国际上的相关 工作做出分析和比较，最后给出本文的研究内容。 1 1问题描述 j a v a 作为一种多线程程序设计语言，为了保证多线程安全，j a v a 标准库中的 很多类都必须设计成线程安全的，也就是在访问共享数据时显式添加同步操作， 如v e c t o r 、h a s h t a b l e 等，程序可以在多线程环境中简单安全地使用这些库所提供 的功能。程序员除了可以通过调用j a v a 标准库中各个线程安全的类和方法外， 还可以利用j a v a 中的同步方法和同步代码块来实现多线程对共享数据的互斥访 问，以确保程序的正确性。虽然j a v a 中的同步机制( 包括同步方法和同步代码块) 能方便地保证多线程的安全，但是同步会给多线程程序的运行带来非常大的开 销。据研究表明，“同步开销通常占总体执行时间的5 1 0 ” 2 1 ：在对m a r m o t t 3 1 的测试中，“5 个中等大小的单线程程序在同步上花费了2 6 , - 6 0 的时间”，可以 想象同步优化的重要性绝对不可忽视。 同步优化( s y n c h r o n i z eo p t i m i z a t i o n ) 是指降低同步操作的开销，提高程序的 整体性能。为了减小同步操作的开销，一些方法直接改良同步原语( p r i m i t i v e ) 的 实现，比如t h i nl o c k t 7 】和l o c kr e s e r v a t i o n i 引。还有一些方法利用静态程序分析技 术自动分析消除不必要的同步操作f i 睨1 1 。这些程序分析方法大体可以分成两种 类型：1 ) 基于逃逸分析( e s c a p ea n a l y s i s ) t m 谗】，只要在线程t 对对象o 的同步操 作期间没有其他线程t 对o 做同步，那么t 中对o 的同步就可以删除。现有的 第1 章绪论 方法都是对这个同步删除条件的某种保守近似。比如，有的方法【1 0 1 分析程序是否 只有一个线程，如果是单线程程序，则不需要做同步，这种方法的缺点是无法处 理多线程程序。j a v a 应用程序中常有些单线程程序使用j d k 中的帮助线程，这 样，这些程序实际是多线程的，但是帮助线程并不和主线程共享数据；有的程序 分析方法i 1 0 1 会鉴别出那些在程序执行中除了创建线程，不会有其他线程访问的对 象( t h r e a d 1 0 c a l 对象) ，这些对象是不需要同步的。比较精确的逃逸分析一般开销 都很大，而且对单线程或是那些同步数据结构存储在静态变量中的程序处理结果 很差。2 ) 基于锁粗化( l o c kc o a l e s c e n c e ) t 1 9 2 1 1 ，如果线程t 在获得同步锁而未释放 该同步锁期间又获取同一个同步锁，那么第二个同步锁获取是不必要的；如果线 程t 连续多次获得并释放同一个同步锁，那么这多对同步锁操作可以合并成一 对，以减少同步锁操作的数量。如果只进行过程内的分析，分析的开销一般都很 小，能减少的同步锁操作的数目也不多：但是如果进行全局的过程间分析，分析 的开销便会成倍增长，而能减少的同步锁操作的数量未必会有明显的增加。这一 类同步优化算法还有一个不得不考虑的问题就是多个同步锁合并之后同步区域 的范围增大，在多线程的环境下会引起程序并发度的下降，尤其是在线程数非常 多的情况下，对并发度的影响会更加明显。 现有的研究都能从各个角度在一定程度上降低j a v a 多线程程序的同步开销， 但都存在各自的弊端，即使是精确的逃逸分析或者过程间的锁粗化算法也只能用 巨大的开销换取微薄的性能改进。本文所做的研究力求改变这一现状，1 ) 充分挖 掘过程内的锁粗化算法，提出一种自动外提循环中的同步操作的过程内锁粗化算 法，具备过程内锁粗化算法开销小的特点，同时能与其他过程内锁粗化算法结合， 进一步减少同步操作的数量：2 ) 提出一种过程间的同步方法优化框架，该框架旨 在分析出无须同步的同步方法调用点并将其改成对相应同步方法的非同步版本 的调用，使锁粗化算法的优化范围从过程内扩展到过程间，增加更多的优化机会， 但又避免了传统过程间程序分析开销大的缺点。 1 2 相关工作 近年来，同步优化已经在很多j a v a 编译运行系统中实现。目前的对j a v a 同 步优化的研究主要分为三类：改良同步原语的实现、基于逃逸分析的同步优化和 基于锁粗化的同步优化。 1 2 1改良同步原语的实现 设计和实现合理的同步原语对降低同步操作的开销能起到直接的作用，经过 精心设计的同步原语可以减少锁操作的指令数，这类方法不属于程序分析技术， 2 第l 章绪论 但却是理解同步指令的一个非常重要的方式。目前比较经典的原语实现包括瘦锁 ( n i i nl o c k ) 1 7 l 和锁保留技术( l 0 c kr e s e r v a t i o n ) 8 1 两种。 瘦锁( t h i nl o c k ) 在j a v a 虚拟机( j v m ) 中，每个对象包含一个三个字的头，头的后面才是真正 的数据，为了实现瘦锁【7 1 ，需要在对象头中预留2 4 b i t 。可以用各种的编码技术在 对象头中挪出2 4 b i t 保存锁信息以实现瘦锁，通过精心安排这2 4 b i t 的锁区域可以 尽量减少锁操作的指令数，简单、容易维护，一旦一个线程获得一个瘦锁之后， 以后该线程再获得该锁就不需要使用原子操作，但为了保证在多线程环境下各线 程竞争锁的安全性，线程第一次获得瘦锁仍需要原子操作。 锁保留技术( l o c kr e s e r v a t i o n ) 锁保留技术1 8 1 基于线程局部性( t h r e a dl o c a l i t y ) ，即对一个给定的对象上的 锁，一般都会由一个特定的线程来申请和释放，该技术的关键思想是允许一个锁 被一个线程保留，如果一个锁已经被一个线程保留，该线程申请该锁就非常快， 不需要任何原子操作。如果这个锁被另一个线程保留，必须先取消保留，然后申 请该锁。 除了瘦锁( t h i nl o c k ) 和锁保留技术( l o c kr e s e r v a t i o n ) 两种经典的同步原语实 现，还有一些j a v a 虚拟机借鉴操作系统中的s p i nl o c k 和m u t e x 。当两个线程竞 争同一个锁时，其中一个会得到锁，另一个必须阻塞，直到锁可用，如s u n 的 h o t s p o tj v m l 4 1 。实现阻塞有两种显而易见的技术，即让操作系统暂挂线程，直 到线程被唤醒，或者使用旋转锁( s p i nl o c k ) 。旋转锁基本上相当于以下代码： w h i l e ( 1 0 c k s t i l l i n u s e ) ： o b t a i nl o c k ； r e l e a s el o c k ； 旋转锁是c p u 密集型的，显得效率低下，但是如果争夺的锁被持有的时间 非常短，那么旋转锁要比暂挂线程然后再唤醒它更有效率。如果锁只被持有很短 的时间，那么旋转会更有效率；如果锁持有很长时间，那么暂挂会更有效率。由 于没有指定应用程序的锁定时间分布信息，所以多数j v m 只采用其中的一种。 但是，可以做得更好，让j v m 根据以前获得的行为，适应性地在旋转和暂挂之 间进行选择。它可以试用旋转，然后如果在短时间内成功，那么就继续采用这种 方式。另一方面，如果在旋转一定时间后锁获得失败，那么就可以判断这个锁被 “长时间 持有，然后就重新编译j a v a 方法，只使用暂挂。但是像这样的优化 在静态编译环境中是不可能的，因为关于锁使用模式的信息在静态编译时得不 到。 3 第l 章绪论 1 2 2 基于逃逸分析的同步优化 逃逸分析是一种过程间数据流分析技术，它对程序中的对象进行分析，以确 定对象是否逃逸出了某个上下文( 可以是一个方法或线程) ，从而为对象的分配、 同步消除等提供优化的依据。如果通过逃逸分析可以得知一个对象在整个程序中 只被单个线程访问或者被多个线程访问，但只有一个线程存在该对象上的同步操 作，那么基于这个对象的监视器之上的所有同步操作都可以删除。 优点：一旦分析出符合条件的对象，便可以删除该对象上的所有同步操作。 缺点：逃逸分析大都采用非流敏感、编译时的分析方法在很多地方必须保 守处理，导致分析的命中率很低，而且精确的逃逸分析一般开销非常大。 基于逃逸分析的同步优化根据其分析的精度，大致经历了以下几个阶段： 分析出只由创建它的线程访问的对象，删除这些对象上的同步操作。 【1 4 1 5 提出了一个建立在s s a 格式( s t a t i cs i n g l ea s s i g n m e n tf o r m ) 的此类分 析。【1 7 】在i n t e l 的o r p ( o p e nr u n t i m ep l a t f o r m ) 上实现了一个逃逸分析框架用于 同步消除优化中，它提出一些b o t t o m u p 和u p - d o w n 传播算法用于在对象上传播 逃逸状态。【1 2 1 6 的逃逸分析算法引入了一种称为连接i 茎l ( c o n n e c t i o ng r a p h ) 的 程序抽象用以确立对象、对象引用之间的可达性逃逸分析被映射到连接图上的 可到达问题。连接图可以很容易地为每个方法建立相关结构，能在不同的方法调 用上下文中被利用以避免重复计算，并运用其分析结果进行栈中分配与同步消除 的优化。f l l 】提出了一种合并了指针分析和逃逸分析的算法用予j a v a 程序的分 析。该算法基于一种称为指向逃逸图( p o i n t - t oe s c a p eg r a p h ) 的抽象，它不仅描述 了局部变量和对象中的域如何引用其他的对象，还包括逃逸信息。该算法设计成 为可以分析完整的或不完整的程序的任意区域中的对象是否逃逸出这个区域，因 此适合分析动态载入的程序。 分析出被多线程访问但只在一个线程中被同步的对象，对这些对象上的同步 操作也可以删除。 【1 3 】不仅对静态域不可到达的对象作了同步消除，还对整个程序中只被一个 线程访问的静态域可到达的对象也作了同步消除。【1 8 ；j l 入了一种基于等价类 ( e q u i v a l e n c e c l a s s b a s e d ) 的表示用以确立对象、对象引用之间的关系，目标是仅 保留被多于一个线程同步的对象上的同步操作。 逃逸分析基础上的时序分析。 【l o 】在【1 8 】的基础上，对各个线程进行时序分析，对于被多个线程访问并且 在多个线程中被同步的对象，如果不同线程中在该对象上的同步操作存在时间上 的先后顺序，这样的同步操作也可以删除。 4 第l 章绪论 1 2 3基于锁粗化的同步优化 这一类的同步优化方法的目标是扩大某一同步区域的范围，使之与相邻的同 步区域合并，将多个相邻的同步区域合并成一个大的同步区域，以减少同步操作 的数量。如果只进行过程内的分析，分析的开销一般都很小，能减少的同步锁操 作的数目也不多，但是如果进行全局的过程问分析，分析的丌销便会成倍增长， 而能减少的同步锁操作的数量未必会有明显的增加。这类同步优化算法还有一个 不得不考虑的问题就是多个同步锁合并之后同步区域的范围增大，在多线程的环 境下会引起程序并发度的下降，尤其是在线程数非常多的情况下，对并发度的影 响会更加明显。 【1 9 】提出一套锁粗化的变换方式，是编译器进行锁粗化的基础，包括锁删除 变换、锁迁移变换，并提出种锁清除算法，为锁粗化算法在各个方面的应用奠 定了基础。【2 0 提出2 种降低锁丌销的技术：数据锁粗化( d a t al o c kc o a r s e n i n g ) 和计算锁粗化( c o m p u t a t i o nl o c kc o a r s e n i n g ) 。s t o o d l e y 等【2 l 】在即时编译器 ( j u s t i n t i m ec o m p i l e r ) 中分析j a v a 程序的中阳j 表示，删除嵌套同步操作的内层同 步操作，合并同一对象监视器上的多个连续同步操作，实际上就是 1 9 1 的思想在 j a v a 即时编译器中的应用，其工作只局限在一个j a v a 方法的内部，尚有更多的 优化机会可以挖掘。 1 3 研究内容 针对前面介绍的各类同步优化存在的不足，本文的工作以开源的j a v a s e 项 目h a r m o n y 为平台，重点研究基于锁粗化的同步优化算法，提出了一种利用即 时编译器自动外提循环中的同步操作的过程内同步优化算法和一种同步方法优 化框架，能够用过程内分析的低开销获取过程间分析的高收益，解决了锁粗化算 法开销与收益之间的矛盾，并在h a r m o n y 平台上实现了这些想法。主要的研究 内容如下： 1 、在实际的j a v a 虚拟机h a r m o n y 中设计实现一个插桩取样系统 我们设计了一个插桩取样系统，并在h a r m o n y 中实现了该系统，旨在收集 运行时信息，例如，各种同步操作在运行过程中实际执行的次数等，一方面可以 帮助同步优化算法的开发者调试、分析以及评价算法，另一方面可以帮助同步优 化算法的开发者改进和优化算法，甚至可以为开发效果更佳的新算法提供依据。 2 、在h a r m o n y 中实现s t o o d l e y 等提出的基于锁粗化的同步优化算法【2 l 】 s t o o d l e y 等提出的算法能删除过程内的嵌套同步操作中的内层同步操作以 及合并过程内的相邻同步操作，以减少同步操作的数量。本文介绍该算法的算法 思想、实现步骤以及实验分析与评估，目的在于直观地展示一个基于锁粗化的同 5 第1 章绪论 步优化算法，为设计实现新的基于锁粗化的同步优化算法的提供思路，为深入研 究该类同步优化算法奠定基础。 3 、提出一种利用即时编译器外提循环内同步操作的过程内同步优化算法 同步操作如果出现在循环中，会更严重地影响程序的性能。为了降低循环中 同步操作的丌销，本文提出一种利用即时编译器外提j a v a 程序中循环内同步操 作的优化算法，并在h a r m o n y 中实现。该算法在保证程序语义不变的前提下， 大量减少运行时实际执行的同步操作数量，降低同步丌销，并能保证外提变换后 同步代码块不会太大而降低程序的并发度。该算法是一个简单但高效的过程内算 法，开销小，可以与任何其他的同步优化算法结合使用，充分挖掘了过程内算法 的优化机会，实验结果表明该算法对s p e c j b b 2 0 0 5 吞吐量的提高可达到l 3 。 4 、提出一个过程间的同步方法优化框架 同步方法是j a v a 语言中最常见的同步结构之一，本文针对同步方法，提出 一个过程间的同步方法优化框架，该优化框架旨在分析出无须同步的同步方法调 用点并将其改成对相应同步方法的非同步版本的调用，该框架既具备过程内分析 低- 丌销的特点又能保证了过程间分析的高收益。我们在该框架的基础上提出一个 基于锁辊化的同步方法优化算法，并在h a r m o n y 中实现了该算法，实验结果表 明该算法对s p e c j b b 2 0 0 5 吞吐量的提高可达到2 q 。 1 4 论文组织 本文的其余部分是这样组织的： 第2 章介绍一些基本概念，并对h a r m o n y 平台做了简要介绍，详细研究了 h a r m o n y 中与本文工作相关的各个方面。 第3 章介绍了一个辅助虚拟机开发人员调试、分析、评价和改进同步优化算 法的插桩取样系统。 第4 章在h a r m o n y 中实现了s t o o d l e y 等提出的基于锁粗化的同步优化算法， 并对实验结果进行分析。 第5 章给出了一种利用即时编译器自动外提循环中的同步操作的过程内同 步优化算法，并在h a r m o n y 平台上实现，并对实验结果进行分析。 第6 章提出一个同步方法优化框架，并在h a r m o n y 平台上实现这种框架， 并对实验结果进行分析。 第7 章对全文进行总结。 6 第2 章基础j c l l 识 第2 章基础知识 为了方便读者理解本文将要提出的各种同步优化算法，本章介绍本文的同步 优化算法涉及到的一些背景知识，包括j a v a 语言中的同步机制和程序分析技术， 并简要介绍本文所使用的j a v a 虚拟机实现平台h a 姗o n y 。 2 1 j a v a 语言中的同步机制 根据j a v a 语言规范( j a v al a n g u a g es p e c i f i c a t i o n ) 【刚，j v m 系统中存在一个主 存( m a i nm e m o r y 或j a v ah e a pm e m o r y ) ，对于所有线程都是共享的。每个线程都 有自己的本地存储区，本地存储区中保存的是主存中某些变量的拷贝，线程对所 有变量的操作都是在本地存储区中进行，线程之间无法相互直接访问，变量传递 均需要通过主存完成。 j a v a 提供了同步块( s y n c h r o n i z e db l o c k ) 和同步方法( s y n c h r o n i z e dm e t h o d ) ，可 以利用它们实现多线程对主存的互斥访问来确保程序的正确性。同步操作必须借 助监视器( m o n i t o r ) 来完成，监视器是一个抽缘的概念，它可以用对象和类上的锁 来实现。j a v a 中的每一个对象都配有一个内部的监视器，其功能相当于锁。当某 线程要执行一个同步方法或同步块中的代码时，必须先获得指定对象上的监视 器，执行完毕后还需释放所持有的监视器。j a v a 虚拟机规范1 5 】中指出：同步操作 强制实施一个互斥锁，这个互斥锁每次只允许一个线程进入一个同步语句块，直 到已经执行了匹配的解锁操作后才释放锁：并还确保当进入一个同步块时线程的 本地存储区被清空，所有需要用到的变量都从主存中重新载入，当退出一个同步 块时，线程的本地存储区中的内容全部刷新至主存。因此，在一个同步块中，一 个线程所写入的值对于其余所有由同一监控器所保护的同步块的线程来说是可 见的。j a v a 存储模型在缺乏同步的情况下，不会做这种保证。 在字节码级，语言级的同步块变换成由m o n i t o r e n t e r ( j j l l 锁) 指令开始，由 m o n i t o r e x i t ( 解锁) 指令结束的指令序列，在执行该指令序列之前必须执行 m o n i t o r e n t e r 指令以获得监视器，执行完之后必须执行m o n i t o r e x i t 指令以释放监 视器，获得和释放的监视器都在源程序中显式指定：语言级的同步方法也由 m o n i t o r e n t e r 指令开始，由m o n i t o r e x i t 指令结束，在执行同步方法之前必须执行 m o n i t o r e n t e r 指令以获得监视器，在同步方法返回之前必须执行m o n i t o r e x i t 指令 以释放监视器，但是获得和释放的监视器都在源程序中没有显式指定，若是s t a t i c 的同步方法( 即类同步方法) ，监视器为该同步方法所属的类对应的c l a s s 对象的监 视器，若非s t a t i c 同步方法( 即实例同步方法) ，监视器为t h i s 对象的监视器。为 7 第2 章基础知识 便于描述，本文统一用l o c k ( 0 ) 和t i n l o c k ( o ) 表示对对象。的监视器进行加锁和 解锁，将执行同步方法前获得的监视器以及同步方法返回前释放的监视器称为该 同步方法的同步对象。 j a v a 语言的同步模型是与异常机制相结合的。对于程序中的每个同步块( 不 论是对同步方法的调用，还是包含在一对显式同步操作中的代码) ，j v m 都要确 保其有相应的异常处理来支持在同步块运行出现异常时能释放锁。 除了同步方法和同步块之外，j a v a 还提供了如下同步机制用于编程： 1 ) t h r e a d 对象的s t a r t 和i o i n 方法，分别用于启动线程对象和等待线程对象 的结束； 2 ) o b j e c t 对象的w a i t 和n o t i f y 、n o t i f y a l l 方法，分别用于使线程对象进入 阻塞状态和通知唤醒某个或所有处在阻塞状态的线程对象。 2 2 程序分析技术的分类 在编译运行系统中进行的程序分析技术多种多样，并以不同的角度可以有不 同的分类。 1 ) 根据是否考虑控制流程序分析技术可以分为流敏感( f l o ws e n s i t i v e ) 和 流不敏感( f l o wi n s e n s i t i v e ) 两类。程序中出现的控制流有多种情况，除了代码顺 次执行的普通控制流之外，还有循环、分支( 条件跳转、无条件跳转) 等控制流存 在。流敏感的分析会考虑对循环、分支等特殊控制流情况的处理，而流不敏感的 分析将忽略这些特殊的控制流情况。 2 ) 根据是否考虑调用上下文，可以分为上下文敏感( c o n t e x ts e n s i t i v e ) 和上 下文不敏感( c o n t e x ti n s e n s i t i v e ) 两类。前者在分析时会结合当前方法的调用上下 文的一些相关信息进行该方法的分析，而后者在分析时只关注该方法本身的代 码，而不会考虑方法的调用上下文。 3 ) 根据分析是否考虑过程之间的影响可以分为过程问( i n t e r p r o e e d u r a l ) 和过 程内( i n t r a p r o c e d u r a l ) 两类。过程间的分析是在整个程序范围内的分析，其获得每 个过程( 或方法) 的分析结果包括了全局的一些信息，而过程内的分析则仅仅是程 序中一个过程( 或方法) 内部代码上的分析。 2 3开源j a v as e 项目h a r m o n y 简介 h a r m o n y 2 2 1 是a p a c h e 软件基金会在2 0 0 5 年5 月建立的开源j a v as e ( j a v a s t a n d a r de d i t i o n ) 项目，该项目主要包含两个部分的开发：j a v a 虚拟机和j a v a 类 库( c l a s sl i b r a r y ) ，目前已经向外发布了稳定的版本。该项目的目标是：1 ) 在 a p a c h el i c e n c ev 2 的许可之下开发出一个与现有j d k ( j a v ad e v e l o p e r k i t ) 兼容 8 第2 章基础知识 的j a v as e5 的独立实现；2 ) 建立一个丌放的模块化运行时架构，包括虚拟机和 类库之间及其内部的模块化，并通过这个平台，允许对运行时平台感兴趣的人在 此基础上开展相关的开发工作。 h a r m o n y 项目开发的j a v a 虚拟机命名为d r l v m ( d y n a m i cr u n t i m el a y e r v i r t u a lm a c h i n e ) 1 2 3 j ，是j 2 s e1 5 o 虚拟机的完美实现，基本上全用c 和c + + 语 言丌发。d r l v m 的组成结构如图2 1 所示，主要模块有虚拟机内核( v m c o r e ) 、 执行引擎( e x e c u t i o ne n g i n e ) 、执行管理器( e x e c u t i o nm a n a g e r ) 、垃圾收集器 ( g a r b a g ec o l l e c t o r ) 、线程管理器( t h r e a dm a n a g e r ) 。d r l v m 有着良好的模块化设 计，每个功能模块都有着多套实现方案，可以在编译和运行时方便组合，从而在 各种平台上都可组合实现最优的运行效果。【2 4 1 给出了h a r m o n y 平台的构建方 法，详细描述了构建h a r m o n y 的各个步骤。 图2 id r l v m 的主要模块 组成h a r m o n y 的虚拟机( d r l v m ) 的六个组件的基本功能如下： 虚拟机内核( v mc o r e ) ：负责虚拟机各个组件之间交互的核心部分，存储和 管理一些公共资源。 执行引擎( e x e c u t i o ne n g i n ，简称e e ) ：执行字节码的组件，它有两种可选的 类型：即时编译器( j i d 和解释器( i n t e r p r e t e r ) 。即时编译器将字节码编译为本地代 码( n a t i v ec o d e ) 并执行之；而解释器则是读入一条条原始的字节码，并执行相应 的- d , 段c c + + 代码。因此，解释器较为简单，只是解释执行字节码；而即时编 译器除了编译字节码以外，还可以有优化工作。 执行管理器( e x e c u t i o nm a n a g e r ，简称e m ) ：负责管理运行时代码的编译与 重编译。它根据程序概要信息收集器( p r o f i l ec o l l e c t o r ) 所提供的程序概要信息 ( p r o f i l e s ) ，决定方法是否需要由某个特定的j i t 进行重编译。 垃圾收集器( 英文全称，g c ) ：负责程序中对象的分配与回收管理，管理运行 时整个堆空间。 9 第2 章基础知识 线程管理器( t h r e a dm a n a g e r ，简称t m ) ：为虚拟机及类库提供内部的线程实 现函数，将线程实现部分集中模块化管理，使之独立于虚拟机其他部分的实现。 接e l 层( p o r t i n gl a y e r ) ：为不同类型的平台下的底层系统例程提供虚拟机统 一的接口，这些接口包括系统与环境变量信息、本地代码与虚拟机内存管理、共 享库支持、文件信息、i o 、网络、原子操作、同步原语等。 在这些