一种基于依赖分析的并发程序潜在死锁检测算法  

Potential Deadlock Detection Algorithm for Concurrent Programs Based on Dependence Ana-lysis

作　　者：卢超[1] 卢炎生[1] 谢晓东[1] 赵小松[1] 

机构地区：[1]华中科技大学计算机科学与技术学院,湖北武汉430074

出　　处：《小型微型计算机系统》2007年第5期841-844,共4页Journal of Chinese Computer Systems

基　　金："十五"国家级科技预研项目(41315.9.2)资助

摘　　要：死锁是并发程序特有的一种运行时错误,由于并发程序在执行时的不确定性,死锁的检测和定位是非常困难的.本文提出了一种基于依赖分析的并发程序潜在死锁检测算法,该算法是一种静态分析算法,能检测并发程序中是否存在潜在死锁,并能定位死锁发生时各线程可能被挂起的语句节点.本文给出了算法的形式化定义和时间复杂度分析,实验测试结果表明算法是正确且有效的.Deadlock is a kind of runtime error in concurrent programs. Detection of deadlock is very difficult due to the indeterminism of the execution of the concurrent programs. This paper proposed a potential deadlock detection algorithm for concurrent programs, which is based on the dependence analysis technology. The formal definition of the algorithm is presented, and the time cost is analyzed. The results of the experiments show that the algorithm is correct and efficient.

关 键 词：死锁 并发 依赖分析 软件测试 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]