基于程序运行轨迹Petri网模型挖掘的死锁检测方法

来源：计算机集成制造系统杂志2021年第9期北京时间：

作者：鲁法明,崔明浩,包云霞,曾庆田,段华

单位：1.山东科技大学计算机科学与工程学院2.山东科技大学数学与系统科学学院

摘要：程序死锁检测对于保证软件系统的稳定性具有重要作用。动态死锁分析方法由于具有高效和低误报率的特点而得到广泛研究。然而,传统的动态分析方法采用锁图及其各类扩展模型进行程序运行轨迹的建模和分析,它们难以对锁的授权/释放操作及其执行场景进行准确刻画,从而会导致误报现象。针对该问题,提出一种新型的基于程序运行轨迹Petri网模型挖掘的多线程程序动态死锁分析方法。首先,捕获程序运行轨迹中各类并发原语对应的操作,并据此构建程序的Petri网模型;然后,将程序的死锁检测问题转化为程序伴随Petri网模型的死标识检测问题;最后,在传统可达树基础上,计算并扩充了可用于死锁重演的程序调度方案。所提方法能排除更多的误报,并给出一种确定性的死锁重演方案,可有效提高死锁检测的准确性。

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

基金资助：国家自然科学基金资助项目(61602279);山东省泰山学者工程专项基金资助项目(ts20190936);山东省高等学校青创科技支持计划资助项目(2019KJN024);国家海洋局海洋遥测工程技术研究中心开放基金资助项目(2018002);青岛西海岸新区揭榜挂帅技术攻关项目。