Abstract: 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.

Key words: multi-threaded program, lock operation, Petri net, Mixed Integer Programming(MIP), deadlock detection

摘要： 针对并发程序中死锁检测困难的问题,基于Petri网对多线程程序进行死锁检测。定义抽象描述多线程程序中锁操作的Petri网模型,在现有基于混合整数规划(MIP)的死锁检测算法基础上,提出改进的MIP算法检测该模型中是否存在死锁。实验结果表明,改进MIP算法能够检测到Petri网模型中的死锁,与标志矩阵算法和可达图相比,处理大规模多线程程序时计算效率更高。

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

CLC Number: 

• TP391.9