学位论文 > 优秀研究生学位论文题录展示

Java程序的对象单赋值分析

作　者: 李健
导　师: 朱传琪
学　校: 复旦大学
专　业: 计算机软件与理论
关键词: 对象单赋值数据竞争检测确定性回放线程局部对象编译
分类号: TP311.1
类　型: 硕士论文
年　份: 2011年
下　载: 37次
引　用: 0次
阅　读: 论文下载

内容摘要

随着对多核技术的深入研究与多核体系结构的广泛应用,多线程程序的开发与维护问题越来越引起人们的重视。其中,多线程程序运行时对内存访问顺序的不确定性常为程序带来数据竞争、死锁等问题。由于上述程序错误发生的不确定性,以及程序出错的位置与引发错误的具体原因往往没有直接关系,所以对多线程程序错误的检测与排除变得非常困难。对于由多线程程序运行时的不确定性引发的问题,学术界提出了多种例如数据竞争检测、确定性回放等方法用于检测与排错。但是,这些方法都面临着相同的性能瓶颈。数据竞争检测算法一般会引入2x～10x的额外运行开销,而确定性回放系统平均额外开销可达10x～100x。巨大的性能开销阻碍了这些方法的广泛应用。数据竞争检测算法与确定性回放算法的主要性能开销来自对程序内存访问的监控：动态数据竞争检测算法需要对程序的内存访问进行监控以找出运行时的数据竞争错误；确定性回放算法需要记录不同线程对内存访问的顺序来确定性的重现程序运行。因此,如何减少上述系统在内存监控上的开销是系统设计者面临的一个共同问题。在多线程应用程序中中存在着大量只被赋值一次的对象。这类对象首先被某个线程写操作赋值,之后被多线程只读访问。我们称这类对象为单赋值对象。虽然单赋值对象在程序运行的生命周期中能够被多个线程访问,但是除第一次的赋值写访问之外,其他访问均为读操作,所以,对单赋值对象的内存访问不需要被数据竞争、确定性回放等系统监控。实验数据表明,单赋值对象内存访问在实际内存访问中占很大比例。分析找出单赋值对象并去除对单赋值对象的内存访问监控可以进一步提高数据竞争检测、确定性回放等系统的性能,从而扩展此类方法的应用范围。本文首先指出了单赋值对象这一问题对数据竞争检测、确定性回放等系统的性能影响,并通过对多个多线程程序测试集的测试证明了单赋值对象内存访问在程序内存访问中占很大比例；然后给出了单赋值对象的形式化定义,并根据这一定义设计了一种基于静态分析的对象单赋值分析算法；最后将这一算法实现在Java语言上,对Java程序字节码进行对象单赋值分析,并将算法的分析结果应用到多种成熟的数据竞争检测系统和一个确定性回放系统中。测试数据表明使用对象单赋值分析算法的分析结果可以有效减少数据竞争检测、确定性回放系统的运行开销,从而扩展系统应用场景。论文的主要贡献包括：·提出了多线程程序运行中存在的单赋值对象问题,并对单赋值对象做出了形式化的定义；·使用静态分析方法构建了对象单赋值分析算法；·将对象单赋值分析算法的分析结果分别应用在基于LockS et、HappenBefor算法的数据竞争检测系统和一个确定性回放系统中,分别减少了39%、75%和62%的额外开销。

全文目录

目录  3-5
摘要  5-7
ABSTRACT  7-9
第一章绪论  9-19
  1.1 多核体系结构与多线程程序  9-10
  1.2 数据竞争检测与确定性回放技术  10-13
    1.2.1 数据竞争检测技术  10-11
    1.2.2 确定性回放技术  11-13
  1.3 本文研究内容  13
  1.4 研究平台  13-18
    1.4.1 Soot优化框架  13-16
    1.4.2 RoadRunner并行程序分析框架  16-18
  1.5 论文的结构安排  18-19
第二章单赋值对象定义与对象单赋值算法设计  19-33
  2.1 单赋值对象  19-22
    2.1.1 线程局部对象  19-21
    2.1.2 单赋值对象概念  21
    2.1.3 单赋值对象内存访问统计  21-22
  2.2 单赋值对象形式化定义  22-24
  2.3 对象单赋值分析算法  24-33
    2.3.1 对象初始化  25
    2.3.2 全局对象根集合初始化  25-26
    2.3.3 线程局部对象分析  26-28
    2.3.4 对象单赋值分析  28-33
第三章对象单赋值分析优化实现  33-49
  3.1 分析优化总体框架  33-34
  3.2 对象单赋值分析phase  34-41
    3.2.1 加入对象单赋值分析phase  34-36
    3.2.2 过程间分析  36-37
    3.2.3 指向分析  37-39
    3.2.4 函数调用图  39-41
  3.3 分析结果表示  41-44
    3.3.1 分析结果表示方法  41
    3.3.2 添加代码属性  41-44
  3.4 RoadRunner框架导入分析结果  44-49
    3.4.1 ASM动态插装库  44-46
    3.4.2 RoadRunner框架改动  46-49
第四章性能评估与数据分析  49-54
  4.1 测试环境与测试集  49
  4.2 测试结果与数据分析  49-54
    4.2.1 基于LockSet算法的数据竞争检测系统测试  50-51
    4.2.2 基于HappenBefor算法的数据竞争检测系统测试  51-52
    4.2.3 确定性回放系统测试  52-54
第五章相关工作  54-56
第六章结论与未来工作  56-58
  6.1 论文的贡献及创新点  56
  6.2 进一步研究工作  56-58
参考文献  58-62
作者简历攻读硕士学位期间完成的主要工作  62-63
致谢  63-64

Java程序的对象单赋值分析

内容摘要

全文目录

相似论文