Page 108 - 《软件学报》2021年第6期

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2021,32(6):1682−1700 [doi: 10.13328/j.cnki.jos.006244] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

∗
基于锁增广分段图的多线程程序死锁检测

1
1
1
2
2
鲁法明 , 郑佳静 , 包云霞 , 曾庆田 , 段 华 , 王晓宇 1
1
(山东科技大学 计算机科学与工程学院,山东 青岛 266590)
2 (山东科技大学 数学与系统科学学院,山东 青岛 266590)
通讯作者: 鲁法明, E-mail: fm_lu@163.com

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

中文引用格式: 鲁法明,郑佳静,包云霞,曾庆田,段华,王晓宇.基于锁增广分段图的多线程程序死锁检测.软件学报,2021,32(6):
1682−1700. http://www.jos.org. cn/1000-9825/6244.htm
英文引用格式: Lu FM, Zheng JJ, Bao YX, Zeng QT, Duan H, Wang XY. Deadlock detection of multithreaded programs based
on lock-augmented segmentation graph. Ruan Jian Xue Bao/Journal of Software, 2021,32(6):1682−1700 (in Chinese). http://www.
jos.org.cn/1000-9825/6244.htm

Deadlock Detection of Multithreaded Programs Based on Lock-augmented Segmentation
Graph

2
1
2
1
1
LU Fa-Ming , ZHENG Jia-Jing , BAO Yun-Xia , ZENG Qing-Tian , DUAN Hua , WANG Xiao-Yu 1
1 (College of Computer Science and Engineering, Shandong University of Science and Technology, Qingdao 266590, China)
2 (College of Mathematics and Systems Science, Shandong University of Science and Technology, Qingdao 266590, China)
Abstract: Deadlocks are a common defect of parallel programs. To detect deadlocks, dynamic deadlock analysis methods build models
such as lock graphs and segment graphs according to program running traces. However, a lock graph and its existing variants cannot

∗ 基金项目: 国家自然科学基金(61602279, 61472229); 国家重点研发计划(2016YFC0801406); 山东省泰山学者工程专项基金
(ts20190936); 山东省高等学校青创科技支持计划(2019KJN024); 山东省自然科学基金智慧计算联合基金(ZL2019LZh001); 山东省
博士后创新专项基金(201603056); 国家海洋局海洋遥测工程技术研究中心开放基金(2018002); 山东科技大学领军人才与优秀科研
创新团队项目(2015TDJH102)
Foundation item: National Natural Science Foundation of China (61602279, 61472229); National Key Research and Development
Plan (2016YFC0801406); Taishan Scholars Program of Shandong Province (ts20190936); Excellent Youth Innovation Team Foundation of
Shandong Higher School (2019KJN024); Smart Computing Joint Fund of Shandong Provincial Natural Science Foundation
(ZL2019LZh001); Postdoctoral Innovation Foundation of Shandong Province (201603056); Open Foundation of First Institute of
Oceanography, MNR (2018002); Shandong University of Science and Technology Research Fund (2015TDJH102)
本文由“形式化方法与应用”专题特约编辑邓玉欣教授推荐.
收稿时间: 2020-08-28; 修改时间: 2020-10-26, 2020-12-19; 采用时间: 2021-01-18; jos 在线出版时间: 2021-02-07