Deadlock prediction via generalized dependency
Deadlock prediction via generalized dependency
复制标题
DOI：
10.1145/3533767.3534377
复制
发表时间：
2022-07
期刊：
影响因子：
--
通讯作者：
Jinpeng Zhou;Hanmei Yang;J. Lange;Tongping Liu
中科院分区：
文献类型：
--
作者：
Jinpeng Zhou;Hanmei Yang;J. Lange;Tongping Liu
死锁是多线程程序中臭名昭著的bug，会导致严重的可靠性问题。然而，在部署之前很难完全清除它们，因为它们的外观通常取决于特定的输入和线程调度，这需要动态工具的帮助。然而，现有的死锁检测工具主要关注锁，而不能检测与条件变量相关的死锁。本文提出了一种新的方法来填补这一空白。它通过将条件变量的信号抽象为一种特殊资源，将经典的锁依赖关系扩展为广义依赖关系，这样通信死锁也可以建模为保持和等待周期。它进一步设计了多种实用机制来记录和分析广义依赖关系。最后，本文给出了该工具的具体实现。实际应用的实验结果表明，UnHang能够找到所有已知的死锁，并发现两个新的死锁。总的来说，UnHang只增加了大约3%的性能开销和8%的内存开销，使其成为部署环境的实用工具。
Deadlocks are notorious bugs in multithreaded programs, causing serious reliability issues. However, they are difficult to be fully expunged before deployment, as their appearances typically depend on specific inputs and thread schedules, which require the assistance of dynamic tools. However, existing deadlock detection tools mainly focus on locks, but cannot detect deadlocks related to condition variables. This paper presents a novel approach to fill this gap. It extends the classic lock dependency to generalized dependency by abstracting the signal for the condition variable as a special resource so that communication deadlocks can be modeled as hold-and-wait cycles as well. It further designs multiple practical mechanisms to record and analyze generalized dependencies. In the end, this paper presents the implementation of the tool, called UnHang. Experimental results on real applications show that UnHang is able to find all known deadlocks and uncover two new deadlocks. Overall, UnHang only imposes around 3% performance overhead and 8% memory overhead, making it a practical tool for the deployment environment.