一种基于程序可达图的并发程序依赖性分析方法-电子学报.PDF

第 2 期 电　　子 　　学 　　报 Vol . 35 　No . 2 　2007 年 2 月 ACTA ELECTRONICA SINICA Feb . 　2007 　 一种基于程序可达图的并发程序依赖性分析方法 1 1 ,2 1 ,2 戚晓芳 ,徐宝文 ,周晓宇 ( 1. 东南大学计算机科学与工程学院 ,江苏南京 210096 ; 2 . 江苏省软件质量研究所 ,江苏南京 210096) 　　摘 　要 : 　依赖性分析是一种重要的程序分析手段. 针对多线程共享变量通信机制 ,本文在提出一种新的并发程 ( ) 序表示 —线程交互可达图 t IRG 的基础上 ,从全局分析并发程序的依赖关系 ,构建了以程序状态和语句二元组为节点 ( ) 的并发程序依赖图 MSDG . 与传统的以语句为节点的并发程序依赖图相比 ,MSDG 图中依赖关系不仅精确 ,且具有可 传递性 ,对其遍历可获得高精度的并发程序切片 ,精度和效率较其它高精度切片方法有显著提高. 关键词 : 　并发程序 ; 可达性分析 ; 依赖性分析 ; 程序切片 中图分类号 : 　TP311 　　　文献标识码 : 　A 　　　文章编号 : (2007) An Appro ach to Analyzing Dep endence of Concurrent Pro gram s Ba se d on Pro gram Re achability Grap h s QI Xiaofang1 ,XU Baowen1 ,2 ,ZHOU Xiaoyu1 ,2 ( 1 College of Comp uter Science and Engineering , Southeast University , N anj ing , J iangsu 210096 , China ; 2. J iangsu Institute of Sof tware Quality , N anj ing , J iangsu 210096 , China) Ab stract : 　Dep endence analysis is an imp ortant technique to analyze programs . This p ap er prop oses a novel representation for multithreaded programs with shared variables ,which is called thread interaction reachability grap h (tIRG) . Based on tIRG , dep en dences in concurrent programs are analyzed globally and a new dep endence grap h called MS