论文部分内容阅读
程序切片是一种重要的程序分析技术,用于从原有程序中抽取对特定程序点上特定变量有影响的成份以构成新程序,通过分析这种新程序(称为程序切片)达到简化原程序分析的目的。二十多年来,这一技术已在软件调试、测试、维护、度量等软件工程理论研究与实践活动中得到了广泛应用。目前有关顺序程序切片的研究较为成熟,并发程序切片研究因并发程序的不确定性等原因,还存在着许多问题有待解决,其中如何有效地表示并发程序的执行,解决语句间依赖关系不可传递性问题,提高并发程序切片的精度和效率等一直是研究的热点。现有的并发程序切片方法大都采用并发程序流图表示并发程序的执行,并发程序流图是由各并发单元的控制流图通过并行流边或同步边简单连接构成的,它不能显式地捕述并发活动的交织执行,在进行依赖性分析时并行流被简单地作为分支流处理,基于并发程序流图难以从全局进行有效的并发程序依赖性分析。不同并发单元中可并发执行语句间的数据依赖使得并发程序语句间的依赖关系具有不可传递性,直接遍历并发程序依赖图不可避免地引入冗余语句,切片精度较低。目前某些切片方法已解决了部分依赖关系不可传递性问题,但实现代价较高,且未能从根本上解决依赖关系不可传递性问题,切片精度仍有待提高。当并发程序中包含子程序时,除依赖关系不可传递性问题外,采用上下文敏感的顺序子程序间切片方法遍历并发程序依赖图,其切片结果是上下文不敏感的。
本文对传统的可达性分析进行扩充,在提出一种有效的并发程序表示——线程交互可达图tIRG的基础上研究了并发程序切片技术。文中首先对传统的顺序子程序问切片进行改进,然后研究基于线程交互可达图的并发子程序内切片和并发子程序间切片的理论和方法,同时还探讨了线程交互可达图的约简技术,以提高分析效率,最后设计了Ada并发程序切片系统的框架,主要取得了如下的研究成果:
⑴分别提出了一种组合式顺序子程序间切片方法和一种准动态组合式顺序程序切片方法。组合式的子程序间切片方法以子程序为基本分析单位,仪分析与切片标准相关的子程序,通过计算参数间依赖关系以及关于参数的切片实现按需渐增、逐步组合的分析策略,克服了传统的基于系统依赖图的子程序间切片方法需分析所有子程序的不足,提高了分析效率。准动态组合式程序切片方法无需记录任何程序执行信息,直接利用调用栈中的有关信息计算在当前调用串下的切片,切片的精度和效率达到较好的折衷,适用于需快速响应的程序调试。
⑵在讨论语句间依赖关系不可传递性问题以及已有并发程序表示方法应用于并发程序分析方面不足的基础上,提出一种基于线程交互可达图的并发子程序内切片方法。该方法首先基于线程交互可达图从全局对并发程序中的依赖关系进行精确的分析,然后构建一种新的以程序状态和语句二元组为节点的、依赖关系具有可传递性质的并发程序依赖图MSDG,再通过遍历MSDG图计算并发程序切片。采用该方法可解决依赖关系不可传递性问题,获得高精度的并发程序切片,精度和效率较其它高精度并发子程序内切片方法有明显提高。
⑶在充分分析已有并发子程序间切片方法存在问题的基础上,提出一种在保证切片精度不受损失的前提下提高分析效率的三趟式并发子程序间切片方法。三趟式并发子程序间切片方法对不涉及到线程间交互的子程序采用组合式子程序间切片方法,对涉及到线程间交互的子程序则进行内联,采用基于线程交互可达图的并发程序切片方法。该方法较好地解决了依赖关系不可传递性问题和上下文不敏感问题,切片精度较其它并发子程序间切片方法高。
⑷将偏序约简方法扩展到线程交互可达图的约简中,并基于状态信息分别对稳固集和覆盖步图等偏序约简方法进行改进。偏序约简技术是一种十分有效的并发系统状态空间约简技术,约简的并发系统状态空间包含所有的并发程序执行代表。在相关偏序约简理论的基础上,证明了基于朱约简和约简的并发程序可达图所构造的MSDG图在进行并发程序切片计算时是等价的。在提出两种有效的计算与状态相关的变迁依赖方法的基础上,对稳固集技术进行改进;在提出计算与状态相关的传递依赖变迁集方法的基础上,对覆盖步图技术进行改进,改进的偏序约简方法实现代价小,约简效果改善明显。