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



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 distinguish different executions of one lock acquisition statement in a loop structure. The lock set used in extended lock graphs cannot capture those locks which were once held and then released. A segmentation graph cannot model the inter-segment dependencies caused by the coupling of lock release/acquisition operation and thread start operation. The above problems have led to a variety of false positives. To address this issue, existing lock graph and segment graph models are improved. Specifically, a lock graph is extended with statement execution order information. A segmentation graph is expanded with lock acquisition and release information. Furthermore, segments in a segmentation graph are more finely divided in the improved model to capture the inter-segment dependencies caused by lock objects. Eventually, based on the improved models, a new deadlock detection method is proposed. It can eliminate the aforementioned false alarms effectively and improve deadlock detection accuracy. A corresponding prototype system is developed for experimental evaluation. The validity of the proposed method is verified through experiments.



PDF全文下载地址:

http://jos.org.cn/jos/article/pdf/6244