基于Petri网的多线程程序死锁检测  

Deadlock Detection in Multi-threaded Program Based on Petri Net

作　　者：黄理[1,2,3] 顾乃杰[1,2,3] 曹华雄 

机构地区：[1]中国科学技术大学计算机科学与技术学院,合肥230027 [2]中国科学技术大学安徽省计算与通信软件重点实验室,合肥230027 [3]中国科学技术大学先进技术研究院,合肥230027

出　　处：《计算机工程》2016年第4期1-6,共6页Computer Engineering

基　　金：安徽省自然科学基金资助项目"基于GPU集群的深度神经网络并行部署和优化策略研究"(1408085MKL06)

摘　　要：针对并发程序中死锁检测困难的问题,基于Petri网对多线程程序进行死锁检测。定义抽象描述多线程程序中锁操作的Petri网模型,在现有基于混合整数规划(MIP)的死锁检测算法基础上,提出改进的MIP算法检测该模型中是否存在死锁。实验结果表明,改进MIP算法能够检测到Petri网模型中的死锁,与标志矩阵算法和可达图相比,处理大规模多线程程序时计算效率更高。Deadlock detection is in general difficult in concurrent program. Aiming at this problem,this paper proposes a method of deadlock detection in multi-threaded program based on Petri net. It defines a Petri net model which describes the lock operation in multi-threaded program. Based on the current deadlock detection algorithm using Mixed Integer Programming（MIP） ,it proposes an improved MIP algorithm to detect whether the model exists deadlock. Experimental results show that the improved MIP algorithm can detect the deadlock in Petri net model. It has higher computational efficiency when dealing with larger programs,compared with flag matrix algorithm and reachability graph.

关 键 词：多线程程序 锁操作 PETRI网 混合整数规划 死锁检测 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]