（计算机应用技术专业论文）并发程序切片技术研究.pdf

摘要 程序切片是一种重要的程序分析技术，用于从原有程序中抽取对特定程序点上特定变量有影响的成 份以构成新程序，通过分析这种新程序( 称为程序切片) 达到简化原程序分析的目的。二十多年来，这一 技术已在软件调试、测试、维护、度量等软件工程理论研究与实践活动中得到了广泛应用。日前有关顺 序程序切片的研究较为成熟，并发程序切片研究因并发程序的不确定性等原因，还存在着许多口j 题有待 解决，其中如何有效地表示并发程序的执行，解决语句间依赖关系不可传递性问题，提高并发程序切片 的精度和效率等一直是研究的热点。 现有的并发程序切片方法人都采用并发程序流图表示并发程序的执行，并发程序流图是由各并发单 元的控制流图通过并行流边或同步边简单连接构成的，它不能显式地描述并发活动的交织执行，在进行 依赖性分析时并行流被简单地作为分支流处理，基1 ：并发程序流图难以从全局进行有效的并发程序依赖性 分析。不同并发单元中可并发执行语句间的数据依赖使得并发程序语句闻的依赖关系具有不可传递性， 直接遍历并发程序依赖图不可避免地g l 入冗余语句，切片精度较低。目前某些切片方法已鳃决了部分依 赖关系不可传递性问题，但实现代价较高，且未能从根本上解决依赖关系不可传递性口j 题，切片精度仍 有待提高。当并发程序中包含子程序时。除依赖关系不可传递性问题外，采用上下文敏感的顺序子程序 问切片方法遍历并发程序依赖图，其切片结果是上下文不敏感的。 可达性分析对并行流进行顺序化处理，所生成的可达图可从全局捕述并发程序行为。为解决上述问 题，本文对传统的可达性分析进行扩充。在提出一种有效的并发程序表示线程交互可达圈t i r o 的基础上研究了并发程序切片技术。文中首先对传统的顺序子程序问切片进行改进，然后研究基j 线程 交互可达图的并发子程序内切片和并发子程序间切片的理论霸【方法。同时还探讨了线程交互可达图的约 简技术，以提高分析效率，最后设计了a d a 并发程序切片系统的框架，主要取得了如下的研究成果： 分别提出了一种组合式顺序子程序问切片方法和一种准动态组合式顺序挫序切片方法。组合式的 子榉序间切片方法以子程序为基本分析单位，仪分析与切片标准相关的子程序，通过计算参数间 依赖关系以及关于参数的切片实现按需渐增，逐步组合的分析策略，克服了传统的基于系统依赖 图的子稃序问切片方法需分析所有于程序的不足，提高了分析效率。准动态组合式样序切片方法 无需记录任何程序执行信息，直接利用调用栈中的有关信息计算在当前调用串下的切片，切片的 精度和效率达到较好的折衷，适用于需快速响应的张序调试。 在讨论语句间依赖关系不可传递性问题以及已有并发科序表示方法应用于并发程序分析方面不 足的基础上，提出一种基于线程交互可达图的并发子程序内切片方法。该方法首先基于线程交互 可达图从全局对并发程序中的依赖关系进行精确的分析，然后构建一种新的以程序状态和语句二 元组为节点的、依赖关系具有可传递性质的并发程序依赖图m s d g ，再通过遍历m s d g 图计算 并发程序切片。采用该方法可解决依赖关系不可传递性问题，获得高精度的并发程序切片，精度 和效率较其它高精度并发子程序内切片方法有明显提高。 在充分分析已有并发于程序间切片方法存在问题的基础上，提出一种在保证切片精度不受损失的 前提下提高分析效率的三趟式并发子程序间切片方法。三趟式并发子程序间切片方法对不涉及到 线程间交互的子程序采用组合式子程序问切片方法，对涉及剑线程问交互的子程序则进行内联， 采用基于线程交互可达图的并发程序切片方法。该方法较好地解决了依赖关系不可传递性口j 题和 上下文不敏感问题，切片精度较其它并发子程序问切片方法高。 将偏序约简方法扩展剑线程交互可达图的约简中，并基丁状态信息分别对稳闱集和覆盖步图等偏 序约简方法进行改进。偏序约简技术是一种十分有效的并发系统状态空间约简技术，约简f l 勺并发 系统状态空间包含所有的并发群序执行代表。存相关偏序约简理论的基础上，证明了基r 朱约简 和约简的并发程序可达图所构造的m s d g 图在进行并发拌序切片汁算时是等价的。存提出两种 有效的计算与状态相关的变迁依赖方法的基础上，对稳l 剞集技术进行改进；在提出计算与状态相 关的传递依赖变迁集方法的基础上，对覆盖步图技术进行改进，改进的偏序约简方法实现代价小， 约简效果改善明显。 关键词：并发程序、程序切片，依赖性分析、可达性分析、偏序约简 a b s t r a c t p r o g r a ms l i c i n gi sa ni m p o r t a n tt e c h n i q u et oa n a l y z ep r o g r a m s i ti su s e dt oe x t r a c tc o m p o n e n t sf r o m p r o g r a m sw h i c hm i g h ti n f l u e n c eg i v e nv a r i a b l e sa tas p e c i a lp r o g r a mp o i n t ，a n dm a k ean e wp r o g r a mw h i c hi s c a l l e db ys l i c e t h e nw ec a na n a l y z es l i c ot os i m p l i f ya n a l y s i sf o ro r i g i n a lp r o g r a m s d u r i n gt h el a s tt w e n t y y e a r s ，p r o g r a ms l i c i n gh a sb e e nw i d e l yu s e di nt h e o r yr e s e a r c ha n dp r a c t i c ea c t i v i t i e si ns o f t w a r ee n g i n e e r i n g , s u c ha ss o f t w a r ed e b u g g i n g , t e s t i n g , r r m i n t e r l a n c e , n x a s u 地e t c s of a r , r e s e a r c ho ns l i c i n gs e q t 圮n t i a lp r o g t m m i sm a t u r e u n f o r t u n a t e l y , d u et on o n d e t o t m i l l i s t i cb e h a v i o r so fc o n c u r r e n tp r o g r a m s t h e r ea t es t i nm a n y p r o b l e m sa b o u ts l i c i n gc o n e n r r e n tp r o g r a m s ，i n c l u d i n gh o wt oe f f e c t i v e l yr e p r e s e n te x o e u t i o n so fc o n c u r r e n t p r o g r a m s ，s e t t l e i n u a m i t i v i t y p r c h l e m o f d q m a d e n c e r e l a t i o n o f s t a t o n a m m , a n d i m p r o v e p r e c i s i o n a n d e t t i c i e n e y o f s l i c i n ga n d e r e p r e s e n t l yc o n e n a c r e n tp r o g r a mf l o wg r a p hi su s e dt on 加蚋嚣te x e c u t i o n so f c o n e t m e n tp r o g r a m si nm o s ts l i c i n g n m b o d s a si ti sc o n s t r u c t e db ys i m p l yc o n n e c t i n ge a c hc o n t r o lf l o wg r a p ho f c o n c u r r e n tu n i tw i t hi x i r a l l e lf l o wo r s y n c h r o n i z a t i o n e d 鹃c o n e t m 蜘t p r o g r a m f l o w g r a p h c a n n o t d e s c r i b e i n t e r l e a v i n g o f c o n c t m e n c y e x p l i c i t l y p a r a l l e l f l o wi st r e a t e da sb r a n c hf l o wi nc o n c t m e n tp r o g r a mf l o w 卿h w h i c hm a k e si td i f f i c u l tt oa n a l y z ed e p e n d e n c eo f c o n t i n e n t p r o g r a m s g l o b a l l y a n d 伽鲥s e l y i n a d d i 石a ld a t a d e p e n d e n c e b e t w 嘲s t a t e m e n t s e x e c u t e d c o n c m r e n t l y l e a d st ow e l l - k n o w ni n t r a n s i t i v i t yv t o b l e mo f d e p e n d e n c er e l a t i o no f s t a t e m e n t s r e d u n d a n ts t a t e m e n t sw i l lb ea d d e d t o s l i c eb yd i r e c t l yt r a v e r s i n gc o n g m r tp r o g r a md e p e n d e a c eg r a p h a _ 1 t h o n g hs o m ea p p r o a c h e sh a v es e t t l e d i n t r a n s i t i v i t yp r o b l e mp a r t i a l l y , t h e i rc o s t sa r eh i 曲a n di n t r a n s i t i v i t yp r o b l e mh a sn o ts o l v e dt h o r o u g h l y w h e n c o n c u r r e n tp r o g r a m sa r eo o i 珥，o s e do fs u b p r o g r a m s ，r e s u l t so b t a i n e db yt r a d i t i o h a le e n t e x t - s e 胁s i t i v em e t h o df o r s l i c i n gs e q u e n t i a lp r o g r a m sa r ec o n t e x t - i n s e n s i t i v e p a r a l l e lf l o wi ss e r i a l i z e di nr e a c h a b i l i t ya n a l y s i sa n dr e a c h a b i l i t yg r a p hd e s c r i b e sb e h a v i o mo f c o n c u r r e n t p r o g r a m sg l o b a l l y f o rt h o s ea b o v ep r o b l e m s ，t h i sp a p e re x t e n d st r a d i t i o n a lr e a e h a b i l i t ya n a l y s i sa n dp r o p o s e s a l le f f e c t i v er e p r e s e n t a t i o nf o rc o n c u r r e n tp r o g r a m s t h r e a d e di n t e r a c t i o nr e n c h a b i l i t yg r a p h ( t m g ) b a s e do n t l r g , t e c h n i q u e sf o rs l i c i n gc o n c u r r e n tp r o g r a m sa r es t u d i e d t l l i sp a p e rf i r s ti m p r o v e st h et r a d i t i o n a ls l i c i n g m e t h o df o ri n t e r - p r o c e d u r a ls e q u e n t i a lp r o g r a m s ，t h e ns t u d i e st h e o r i e sa n dm e t h o d sf o rs l i c i n gi n t r a - p r o c e d u r a l a n di n t e r - p r o c e d u r a lc o n c u r r e n tp r o g r a m s t oi m p r o v ee m e i e n e y , t h i sp a p e ra l s od o e ss o l n or e s e a r c h0 1 1 r e d u c t i o nf o rt h r e a d e di n t e r a c t i o nr e a c h a b i l i t yg r a p h l a s t l yi tp r o p o s e sad e s i g nf r a m e w o r ko fs l i c i n gs y s t e m f o r a d a c o n c u r r o f l t p r o g r a m s 1 1 1 e m a i n c o n t r i b u t i o n s o f t h i s p a p e r a r e l i s t e d 勰f o l l o w s ： t l t i sp a p e rp r e s e n t sac o m b i n a t i o n a ls l i c i n ga p p r o a c ha n daq u a s i - d y n a m i cs l i c i n ga p p r o a c hf o r i n t e r - p r o c e d u r a ls e q u e n t i a lp r o g r a m sr e s p e c t i v e l y f o rt h ec o m b i n a t i o n a ls l i c i n ga p p r o a c h , s u b p r o g r a m i sb a s i cu n i to fa n a l y s i s o n l ys u b p r o g r a m sr e l a t e dt os l i c i n gc r i t e r i af i r ea n a l y z e d b yc o m p u t i n g d e p e n d e n c er e l a t i o n si np a m n l e t e r sa n ds l i c ew i t hr e s p e c tt op a r a m e t e r , t h i sa p p r o a c ha v o i d st oa n a l y z e a l ls u b p r o g r a m sw h i l et h e ya r er e q u i r e di nt r a d i t i o n a ls l i c i n gm e t h o d t h e r e f o r e 。t h ec o m b i n a t i o n a l s l i c i n ga p p r o a c hm 3 t ，r o v e ss l i c i n ge t t i c i e n c y f o rq u a s i - d y n a r m cs h e m ga p p r o a e ga n ym o r m a t l o n a b o u tt h ee x e c u t i o no f p r o g r a mi sn o tr e q u i r e dt ob er e c o r d e d b yt a k i n ga d v a n t a g eo fi n f o r m a t i o ni n c a l ls t a c kw ec a nc o m p u t eas l i c ei nc u r r e n tc a l ls t r i n g 。w h i c hi sag o o dt m d c o f fo fp r e c i s i o na n d c 蚯c i e n c ya n di ss u i t a b l ef o rd e b u g g i n ga c t i v i t i e sn e e d i n gq u i c kr e s p o n s e a f t e rd i s c u s s i n gi n m m s i t i v i t yp r o b l e ma n dd i s a d v a n t a g e si nr e p r e s e n t a t i o n sf o rs l i c i n gc o n c u r r e n t p r o g r a m s ，t h i sp a p e rp r e s e n t sa t la p p r o a c ht os l i c i n gm t r a - p r o e e d u r a lc o n e n r r e n tp r o g r a m sb a s e do l l t h r e a d e di n t e r a c t i o nr c a c h a b i l i t yg r a p h i nt h i sa p p r o a c h , d e p e n d e n c ea n a l y s i so f c o n c u r r e n tp r o g r a m si s a n a l y z e dg l o b a l l ya n dp r e c i s e l y , a n dt h e nan e wd e p e n d e n c eg r a p hc a l l e dm s d gi sc o n s t r u c t e d i n m s d g , v e t 蛔g i sa2 - t u p l ec o n l p o s e do fp r o g r a ms t a t ea n ds t a t e m e n t ，a n dd e p e n d e n c er e l a t i o ni s t r a n s i t i v e t h e nb yt r a v e r s i n gm s d gw ec a ns o l v ei n t r a m i t i v i t yp r o b l e ma n do b t a i nm o r ep r e c i s ea n d e f f i c i e n ti n i r a - p r o c e d u r a lc o n o u r r e n ts l i c ei nc o n t r a s tt ob yo t h e rh i g h - p r e c i s i o ns l i c i n gm e t h o d s b a s e do l ls u 伍c i e n ta n a l y s i so fp r o b l e m si nm e t h o d sf o rs l i c i n gi n t e r - p r o c e d u r a lc o n e u t t e n tp r o g r a m s t h i sp a p e rp r o p o s e sat h r e e - p h a s es l i c i n gm e t h o dw h i c hi m p r o v e se f f i c i e n c yu n d e rg u a r a n t e e i n g p r e c i s i o no fs l i c e i nt h i sa p p r o a c h ，s u b p r o 毋 a m sn o ti n v o l v e di nt h r e a di n t e r a e t i o n sa r es l i c e db y c o m b i n a t i o n a ls l i c i n gm e t h o dw h i l es u b p r o g r a m si n v o l v e di nt h r e a di n t e r a c t i o n sa r ei n l i n e da n ds l i c e d b ys l i c i n gm e t h o db a s e do l lt h r e a d e di n t e r a e t i o nr e a c h a b i l i t yg r a p h b yt h r e e - p h a s es l i c i n gm e t h o dw e c a ns o l v ei n t r a n s i t i v i t vp r o b l e ma n do b t a i nc o n t e x t - s e n s i t i v es l i c ew h i c hi sm o r ep r e c i s et h a nb yo t h e r m e t h o d sf o rs l i c i n gi n t e r - p r o c e d u r a lc o n c n l t e n tp r o g r a m s 1 1 1 i sp a p e re x t e n d sp a r t i a l - o r d e rm e t h o d st or e d u c t i o nf o rt h r e a d e di n t e r a c t i o nr e a c h a b i l i t yg r a p ha n d i m p r o v e st e c h n i q u e sf o rp e r s i s t e n t s e t sa n dt e c h n i q u e sf o rc o v e r i n gs t e pg r a p hb a s e do ns t a w i n f o r m u t i o n p a t t i a l o r d e rm e t h o d sa r ee f f e c t i v el e c h n i q u e sf o rr e d u c i n gs t a t es p a c eo fc o n c u r r e n t s 3 ，s t e m s r e d u c e ds t a t es p a c ei n c l u d e sa l ir e p r e s e n t a t i v e so fe x e c u t i o n so fc o n c u r r e n tp r o g r a m s b e s e d o nr e l a t e dp a r t i a l - o r d e rr e d u c t i o nt h e o r y , t h i sp a p e rp r o v e st h a tc o m p u t a t i o n so fs l i c eb yt r a v e r s i n gt h e d e p e n d e n c eg r a p hw h i c hi sr e d u c e da n dt h eo n ew h i c hi sn o tr e d u c e da r ee q u i v a l e n t m o r e o v e r , t h i s p a p e rp r o p o s e st w oe f f e c t i v ea p p r o a c h e st oc o m p u t i n gd e p e n d e n c eo f t r a n s i t i o n sw i t hr e s p e c tt oag i v e n s t a t ea n di m p r o v et e c h n i q u e sf o rp e r s i s t e n ts e t s a l s o ，i tp r o p o s e so n ea p p r o a c ht oc o m p u t i n gt r a n s i t i v e d e p e n d e n c es e t so ft r a n s i t i o n sw i t hr e s c tt oag i y e ns t a t et oi m p r o v et h et e c h n i q u ef o rc o v e r i n gs t e p g r a p h ，0 b v i o u sr e d u c t i o nr e s u l t sa r eo b t a i n e db yu s i n gt h e s ei m p r o v e dm e t h o d sa n dc o s t sa r el o w t h e s ei m p r o v e da d p r o a c h e sa r ea l le x t e n s i o na n dc o m p l e m e n tf o re x i s t e dp a r t i a l - o r d e rr e d u c t i o n m e t h o d s k e y w o r d s ：c o n c o l t e n tp r o g r a m s , p r o g r a ms l i c i n g , d e p e n d e n c ea n a l y s i s , t e a c h a b i l i t ya n a l y s i s ，p a r t i a l - o r d e r r e d u c t i o n 主要算法列表 算法2 1 组合式子程序间切片算法1 0 算法2 2 基于调用串的组合式子程序间切片算法1 2 算法3 1 广度优先生成线程交互可达图算法2 l 算法3 2 基于r g 图的并发程序全局数据依赖分析算法一2 4 算法3 3 基于m s d g 图的并发程序切片算法2 6 算法3 4k 1 i i l l 【e 的并发程序切片算法一2 7 算法4 1 需内联子程序集算法3 3 算法4 2 内联子程序的插入顺序算法3 3 算法4 3 三趟式并发子程序问切片方法3 4 算法5 1 稳固集算法1 4 5 算法5 2 稳崮集算法2 4 6 算法5 3 稳固集算法3 4 7 算法5 4 采用稳固集技术深度优先搜索方法4 8 算法5 5 可能后继变迁集算法4 9 算法5 6 关于稳固集算法l 的第一种改进算法4 9 算法5 7 必经变迁集算法5 0 算法5 8 关于稳固集算法2 的第二种改进算法5 2 算法5 9 综合稳固集和睡眠集技术深度优先搜索方法5 3 算法5 1 0 带附加条件的综合稳固集和睡眠集技术深度优先搜索方法5 5 算法5 1 1 覆盖步刳技术深度优先搜索方法5 8 算法5 1 2 关于状态前向传递依赖变迁集算法6 0 主要图列表 图2 1 实例2 1 的源程序及其s d g 图8 图2 2 实例2 1 的子程序调用图以及各子程序的p d g 图9 图3 1 实例3 1 的源程序、t c f g 图和t p d g 图1 5 图3 2 实例3 2 的源程序和t p d g 图”1 5 圈3 3 a d a 并发程序片断1 一1 6 图3 4 a d a 并发程序片段2 1 7 图3 5 a d a 并发程序片断1 的s t f g 图一1 7 图3 6 a d a 并发程序片段2 的c c f g 图1 8 图3 7c t f g 图1 8 图3 8 实例3 1 的t i g 图2 0 图3 9 实例3 1 的t i r g 图2 1 图3 i o 实例3 2 的t i g 图2 3 图3 1 l 实例3 ，2 的t l r g 图2 4 图3 1 2 实例3 1 的m s d g 图2 5 图3 1 3 实例3 2 的m s d g 图2 5 图4 1 实例4 1 的源程序和t i c f g 图2 9 图4 2 实例4 1 的t s d g 图3 0 图4 3 实例4 2 的源程序和t i c f g 图3 2 图4 4 实例4 2 的子程序调用图和p d g 图3 5 图4 5 实例4 ，2 的t l g 图和t i r g 图3 6 图4 6 实例4 2 的m s d g 图3 6 图4 7 实例4 3 的源程序、t c g 图、t c r g 图4 0 图4 8 实例4 3 中各保护方法的p d g 图4 0 图4 9 实例4 3 的m s d g 图4 l 图5 1 实例5 1 的局部状态图和约筒状态图4 7 图5 2 实例5 2 的局部状态图和约简状态图，5 0 图5 3 实例5 , 3 的局部状态图和约简状态图5 l 图5 4 实例5 1 综合稳固集和睡眠集技术的约简状态图5 4 图5 5 实例5 4 的约筒状态图5 4 图5 6 实例5 5 的c s g 图和完全扩展状态图5 9 图5 7 实例5 6 的c s g 图和完全扩展状态图6 0 图5 8 实例5 7 的源程序和各线程的t l g 图6 3 图5 9 实例5 7 的约简t l r g 图6 4 图5 1 0 实例5 7 约简的m s d g 图一6 5 图6 1s s a c p 框架示意图6 7 图6 2 系统信息表组织7 1 东南大学学位论文 独创性声明及使用授权说明 一、学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：邀丝日期：坚：篁：竖 二、关于学位论文使用授权的说明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学 位论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论文。 本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外， 允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文 的公布( 包括刊登) 授权东南大学研 签名：导师签名：期：企竺量二! 二7 垆 东南大学大学博七论文 1 1 选题依据 第一章引言 随着软件技术的飞速发展，软件系统开发的规模逐步扩大，复杂程度也随之增加，对大型软件的分析、 理解和维护变得非常困难，越来越多的工作需要程序分析理论、技术与工具的支持。研究表明，将一个大 的程序分解为多个程序片断可大大降低程序的复杂程度，方便人们对大型程序的分析理解。为此，研究人 员提出了诸如信息隐藏、数据抽象和程序切片等多种程序分解方法以简化程序分析，其中程序切片技术一 经问世，就引起软件从业人员的极大兴趣和高度蕈视，并对此展开广泛而深入的研究，所取得研究成果应 用于软件： 程学科的各个方面，对软件_ t 程的发展产生了深远的影响i l 程序切片最初是由m w e i s e r 提出的程序分析技术，用于从原有程序中抽取对特定程序点上的特定变 量有影响的程序成份以构成新程序，通过分析这种简短的新程序( 称为程序切片) 达到分解程序、简化分析 和方便调试的目的【l i 。给定切片标准匈，v ，s 为程序p 中某程序点，v 为p 的某变量集，关于毽，v 的切 片包含当程序执行到s 时，p 中所有直接或间接对v 中变量有影响的语句和控制条件。程序切片分为两种： 动态切片和静态切片1 2 “。静态切片考虑程序所有可能的执行情况，与输入无关；动态切片只分析对给定输 入、程序动态执行时所经过路径上的语句，动态切片随输入的不同而不同。 程序切片的方法差要有m w e i s e r 提出的基于数据流方程的数据流迭代算法1 1j 和k o t t e n s t e i n 提出的基 于程序依赖图的幽的遍历算法 4 - ”。由于程序依赖圈直观地表现了程序成份之间的依赖关系，同时基于程序 依赖图进行切片计算的效率和精度较数据流迭代算法高，目莳摹于依赖性分析的程序切片方法已成为丰流 的程序切片方法针对顺序子程序h j 程序、面向对象程序、并发程序和面向方面程序( a o p ) 的特点发各自 存在问题，人们对k o t t e n s t e i n 基于依赖性分析的切片方法进行了扩充，开发出多种程序切片方法“” 在研究各种程序切片方法的司时，人们也实现了一些程序切片工具，如w i s c o n s i n 大学开发的支持c 程序 的切片系统i i 习，我们也曾开发了一个a d a 程序切片系统原璎l l ” 随着程序切片技术的深入研究。为适应不同的应用需求，程序切片纭牛出各种各样自变体，如无定缆 切片、条件切片、射片、砍片、概率切片以及瘦切片等n1 4 - 2 0 l ；进行程序切片研究的依赖性分析方法和切 片分解技术也逐步南对程序代码的分析扩展到对在软件需求分析和软件设计阶段生成制品的分析，如需求 规约切片、软件体系结构切片等p ”“j 。 程序切片技术历经二十多年的发展，取得了丰硕的研究成果，为软件：f 程各阶段提供理论和技术支持- 从理论上，它极大地丰富了程序分析、程序理解、程序维护的理论基础：从实践上，它在软件工程、软件 逆向工程、软件再工程以及信息抽取、程序变换中得到了广泛应用i i “。 上述研究工作主要是针对顺序程序，目前顺序程序切片的研究较为成熟。但随着实际应用对并发需求 的不断增加，越来越多的高级编程语言引入了并发设施支持并发程序设计，如c + + 、j a v a 的线程机制以及 a d a 的任务机制等，并发软件的开发和使用日盏广泛1 3 4 l 。与顺序程序相比，并发程序的分析理解更为困难 和复杂，迫切需要相关理论，技术与工具的支持。目前有关并发程序的分析理解、测试和维护方面的：i ：作 尚未成熟 3 5 - 8 1 】。作为一种摹本的程序分析技术，并发程序切片是该领域的一个霞要研究方向1 3 5 - 6 2 1 。对并发程 序切片进行深入研究取得的研究成果，一方面可丰富并发程序的分析珲解和维护的理论基础，使之广泛应 用于j 发软件的分析理解、调试、测试、维护以及度量等软件t ：程活动巾，另一方面，对并发程序切片的 研究方法i 一样可应用于在j # 发软件需求分析和并发软件设计阶段中所牛成制品的分析理解方面。由于并发 程序的f i 确定性，针对顺序程序的分析方法和工具无法商接应坩到并发程序切片巾，并发程序切片尚有许 多问题有待解决 3 5 * 5 5 l 。 本文在广泛调研的基础卜，结合国家杰出青年科学摹金项目( 6 0 4 2 5 2 0 6 ) 、国家自然科学基金项目 ( 6 0 0 7 3 0 1 2 ) 和国防“十五”霞点预研项目，通过对并发程序切片基本坪论的研究，一定程度卜解决目6 口在 并发程序切片领域所存在的问题，提高并发程序切片的精度和效率，同时对并发程序切片系统实现的一些 问题进行探索。 第一章引言 1 2 国内外研究现状 j c h e n g 最早研究了a d a 并发程序切片，针对并发程序中特有的同步、异步等通信活动，j c h e n g 引 入选择依赖、司步依赖和通信依赖等三种新的依赖，其中选择依赖( s e l e c t i o nd e p e n d e n c e ) 表示由并发程序不 确定性选择产生的依赖，同步依赖( s y n c h r o n i z a t i o nd e p e n d e n c e ) 表示由进程日j 刷步活动产生的控制依赖，通 信依赖( c o m m u n i c a t i o nd e p e n d e n c e ) 表示由进程阃数据通信产生的数据依赖，由此将一般顺序程序依赖图扩 展为进程依赖网( p d n ) 。并通过简单遍历p d n 计算并发程序切片；j z h a o 在p d n 上增加形参、实参节 点以及相关依赖边表示由于子程序调川引起的数据和控制依赖边，生成多线程依赖图( m d g ) ， 同时采用 顺序子程序两趟式遍历算法遍历m d g 图计算并发子程序问切片和面向对象的并发程序切片l ”8 】；j h a t c l i f