试论增量式数据竞争检测

《试论增量式数据竞争检测》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中国科学技术大学硕士学位论文增量式数据竞争检测姓名：郝允允申请学位级别：硕士专业：计算机软件与理论指导教师：张昱20090501摘要摘要在多线程程序中，当两个线程在没有时序约束下访问同一段内存位置时，就可能导致数据竞争。数据竞争使多线程程序的执行具有不确定性，且难于调试和理解。因此研究开发自动检测数据竞争的精确高效工具是非常有价值的。作为第一个在语言级别支持多线程的编程语言，Java被广泛地使用，因此开展对Java并发程序的分析和优化是非常重要的。本论文以Java程序的数据竞争检测技术研究为选题，在调研现有的静态和动态竞争检测技术的基础上，提出并在实际的Java虚拟机中

2、实现了一种精确有效的在线增量式数据竞争检测算法。论文的主要工作和特色如下：1．基于即时编译器，提出了一种结合锁集和发生序关系的增量式竞争检测框架。该框架兼具静态分析不受程序规模限制、无插桩和动态分析的仅分析运行时相关方法、’精确性高等特点。该框架包括方法内分析和方法间分析两个部分。2．基于增量式竞争检测框架，设计方法内分析算法，为流经编译流水线的每个方法收集方法摘要信息，并动态构建和维护跨线程方法调用图。方法摘要包括对象间的域引用关系、对象访问事件、尚未分析的调用点和由start／join引起的线程时序关系等，为方法间分析提供基础信息。跨线程方法调用图的动态构建和维护既

3、降低了空间开销，也能适应Java语言这种因动态类载入等而导致的“开放世界"环境。3．设计自下而上的上下文敏感的跨线程的方法间分析算法，在分析的同时计算并输出潜在的数据竞争。所设计的方法间分析算法保证每个方法最多只被分析一次，并且仅当一个方法的所有被调用点均被分析后，才将该方法向上结合，保证静态程序正文中的每个调用点只被分析一次。4．基于上述框架和算法，在实际的JavaSE平台Harmony上实现了增量式竞争检测系统。通过对SPECjbb2005等多个基准程序的测试，实验结果表明所提算法具有与O’Callahan和Choi等的动态竞争检测算法类似的精确性，而算法所用的分析

4、时间仅占总编译时间的20／o～4％左右，且无额外的运行时开销。关键词：增量式数据竞争程序分析逃逸分析锁集发生序关系AbstractWhentwothreadsaccessasharedmemorythatatleastoneaccessisthewriteandthetwoaccesseshavenohappens—beforerelation，thedatal'aC,ehappens．Datalaceisseriousprogrammingerror．Furthermore，programs诚mdatalacesarenotoriouslydifficulttodeb

5、ugandunderstandbecausetheycanexhibitdifferentbehaviorswiththesameinputs．SoitiswidelyrecognizedthattoolsforautomaticdetectionofpotentialdatalacescaB．bevaluable：Asthefirstlanguagethatsupportsmulti—threadprogramminginlanguagelevel，Javaisbroadlyused．Soresearchingtheprogramanalysis．andoptimiz

6、ationonJavaconcurrentprogramsisveryimportantandsignificative．ThispaperresearchesthedataracedetectiontechnologiesforJavaprograms．Basedontheresearchesabouttheexistingstaticanddynamicracedetectionalgorithms，anewpreciseandefficientalgorithmonincrementallydetectingpotentialdatal"aCesinJavamul

7、tithreadedprogrmnsispresented．Thispapermainlydepictsanddiscussesthefollowingworks：1．PutsforwardanincrementaldataracedetectionalgorithmframeworkbasedonJust-in-time(JIT)compiler,whichcombinesthelockset-baseddetectionandhappens．before-baseddetection．Ithaseithertheunlimitedpr