关键词: 程序运行轨迹, 死锁检测, Petri网, 死锁重演, 过程挖掘

Abstract: Deadlock detection of programs plays an important role in ensuring the stability of software systems.In view of the high efficiency and low false alarmrate of deadlock detection,the dynamic deadlock analysis method is widely studied.However,traditional dynamic analysis methods use lock graph or extended variants to model program trajectory,which cannot accurately describe the lock authorization/release operations and their execution scenario information,thus still leads to some deadlock false positives.To solve this problem,a new deadlock dynamic analysis method based on Petri net model mining was proposed.The operations corresponding to concurrent primitives of programs were captured,and a Petri net model of the program was constructed according to the captured operation sequence.The deadlock detection problem of programs was converted to the dead marking detection problem of adjoint Petri net model of programs.Traditional reachability trees were extended to incorporate scheduling scheme for deadlock replay.The proposed method could eliminate more false positives and provide a deterministic deadlock replay scheme,which effectively improved the accuracy of deadlock detection.

Key words: program trajectory, deadlock detection, Petri nets, deadlock replay, process mining