July 2022

Conference Paper

Deadlock prediction via generalized dependency

By:
Zhou, Jinpeng; Yang, Hanmei; Lange, John R; Liu, Tongping
Page Number:
455-466
Book Title:
Proceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis
Publication Date:
July 2022
Publisher Location:
ACM, United States of America
Conference Name:
International Symposium on Software Testing and Analysis (ISSTA)
Conference Location:
Daejeon, South Korea
Conference Sponsor:
ACM
View DOI Listing:
https://doi.org/10.1145/3533767.3534377

Abstract

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.


Related Researchers