软件学报

作者：鲁法明，郑佳静，包云霞，曾庆田，段华，王晓宇

单位：鲁法明，山东科技大学 计算机科学与工程学院, 山东 青岛 26659011,郑佳静，山东科技大学 计算机科学与工程学院, 山东 青岛 26659002,包云霞，山东科技大学 数学与系统科学学院, 山东 青岛 26659003,曾庆田，山东科技大学 计算机科学与工程学院, 山东 青岛 26659004,段华，山东科技大学 数学与系统科学学院, 山东 青岛 26659005,王晓宇，山东科技大学 计算机科学与工程学院, 山东 青岛 26659006

关键词：程序验证;死锁检测;锁图;分段图;动态死锁分析

基金：国家自然科学基金（61602279，61472229）；国家重点研发计划（2016YFC0801406）；山东省泰山学者工程专项基金（ts20190936）；山东省高等学校青创科技支持计划（2019KJN024）；山东省自然科学基金智慧计算联合基金（ZL2019LZh001）；山东省博士后创新专项基金（201603056）；国家海洋局海洋遥测工程技术研究中心开放基金（2018002）；山东科技大学领军人才与优秀科研创新团队项目（2015TDJH102）

死锁是并行程序常见的缺陷之一，动态死锁分析方法根据程序运行轨迹构建锁图、分段图等模型来检测死锁.然而，锁图及其现有的各种变型无法区分同一循环中锁授权语句的多次执行，扩展锁图中记录的锁集无法捕捉线程曾经持有而又随后释放的锁信息，分段图无法刻画锁的获取和释放操作与线程启动操作耦合而导致的段间依赖关系.上述问题导致了多种死锁的误报.为解决上述问题，对已有的锁图和分段图模型进行改进，在锁图基础上扩充语句的执行时序信息，在分段图的基础上扩充锁的获取和释放信息，对段进行更细粒度的划分以建模锁对象导致的段间依赖关系；最终，在上述锁增广分段图与时序增广锁图的基础上，提出一种新的死锁检测方法.所提方法能够有效消除前述各种误报，从而提高死锁检测的准确率.文中开发相应的原型系统，并结合多个程序实例对所提方法的有效性进行评估验证.

来源：2021年第6期

《软件学报》期刊编辑部

查看软件学报杂志2021年第6期