Deadlock prediction via generalized dependency

Jinpeng Zhou; Hanmei Yang; John Lange; Tongping Liu

doi:10.1145/3533767.3534377

Deadlock prediction via generalized dependency

Jinpeng Zhou, Hanmei Yang, John Lange, Tongping Liu

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

5 Scopus citations

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.

Original language	English
Title of host publication	ISSTA 2022 - Proceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis
Editors	Sukyoung Ryu, Yannis Smaragdakis
Publisher	Association for Computing Machinery, Inc
Pages	455-466
Number of pages	12
ISBN (Electronic)	9781450393799
DOIs	https://doi.org/10.1145/3533767.3534377
State	Published - Jul 18 2022
Externally published	Yes
Event	31st ACM SIGSOFT International Symposium on Software Testing and Analysis, ISSTA 2022 - Virtual, Online, Korea, Republic of Duration: Jul 18 2022 → Jul 22 2022

Publication series

Name	ISSTA 2022 - Proceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis

Conference

Conference	31st ACM SIGSOFT International Symposium on Software Testing and Analysis, ISSTA 2022
Country/Territory	Korea, Republic of
City	Virtual, Online
Period	07/18/22 → 07/22/22

Funding

We are thankful to the anonymous reviewers for their constructive feedback that has helped us improve this paper. This manuscript has been authored by UT-Battelle, LLC under Contract No. DE-AC05-00OR22725 with the U.S. Department of Energy. The United States Government retains and the publisher, by accepting the article for publication, acknowledges that the United States Government retains a non-exclusive, paidup, irrevocable, world-wide license to publish or reproduce the published form of the manuscript, or allow others to do so, for United States Government purposes. The Department of Energy will provide public access to these results of federally sponsored research in accordance with the DOE Public Access Plan (http://energy.gov/downloads/doe-public-access-plan). This material is also based upon work supported by the National Science Foundation under Award CCF-2024253, and UMass Start-up Package. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

Keywords

Condition Variables
Deadlock Prediction
Multithreaded Programs

Access to Document

10.1145/3533767.3534377

Cite this

Zhou, J., Yang, H., Lange, J., & Liu, T. (2022). Deadlock prediction via generalized dependency. In S. Ryu, & Y. Smaragdakis (Eds.), ISSTA 2022 - Proceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis (pp. 455-466). (ISSTA 2022 - Proceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis). Association for Computing Machinery, Inc. https://doi.org/10.1145/3533767.3534377

Zhou, Jinpeng ; Yang, Hanmei ; Lange, John et al. / Deadlock prediction via generalized dependency. ISSTA 2022 - Proceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis. editor / Sukyoung Ryu ; Yannis Smaragdakis. Association for Computing Machinery, Inc, 2022. pp. 455-466 (ISSTA 2022 - Proceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis).

@inproceedings{e7e77d0bcf18466688d898d42a5a4695,

title = "Deadlock prediction via generalized dependency",

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.",

keywords = "Condition Variables, Deadlock Prediction, Multithreaded Programs",

author = "Jinpeng Zhou and Hanmei Yang and John Lange and Tongping Liu",

note = "Publisher Copyright: {\textcopyright} 2022 ACM.; 31st ACM SIGSOFT International Symposium on Software Testing and Analysis, ISSTA 2022 ; Conference date: 18-07-2022 Through 22-07-2022",

year = "2022",

month = jul,

day = "18",

doi = "10.1145/3533767.3534377",

language = "English",

series = "ISSTA 2022 - Proceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis",

publisher = "Association for Computing Machinery, Inc",

pages = "455--466",

editor = "Sukyoung Ryu and Yannis Smaragdakis",

booktitle = "ISSTA 2022 - Proceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis",

}

Zhou, J, Yang, H, Lange, J & Liu, T 2022, Deadlock prediction via generalized dependency. in S Ryu & Y Smaragdakis (eds), ISSTA 2022 - Proceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis. ISSTA 2022 - Proceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis, Association for Computing Machinery, Inc, pp. 455-466, 31st ACM SIGSOFT International Symposium on Software Testing and Analysis, ISSTA 2022, Virtual, Online, Korea, Republic of, 07/18/22. https://doi.org/10.1145/3533767.3534377

Deadlock prediction via generalized dependency. / Zhou, Jinpeng; Yang, Hanmei; Lange, John et al.
ISSTA 2022 - Proceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis. ed. / Sukyoung Ryu; Yannis Smaragdakis. Association for Computing Machinery, Inc, 2022. p. 455-466 (ISSTA 2022 - Proceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Deadlock prediction via generalized dependency

AU - Zhou, Jinpeng

AU - Yang, Hanmei

AU - Lange, John

AU - Liu, Tongping

PY - 2022/7/18

Y1 - 2022/7/18

N2 - 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.

AB - 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.

KW - Condition Variables

KW - Deadlock Prediction

KW - Multithreaded Programs

UR - https://www.scopus.com/pages/publications/85136811128

U2 - 10.1145/3533767.3534377

DO - 10.1145/3533767.3534377

M3 - Conference contribution

AN - SCOPUS:85136811128

T3 - ISSTA 2022 - Proceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis

SP - 455

EP - 466

BT - ISSTA 2022 - Proceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis

A2 - Ryu, Sukyoung

A2 - Smaragdakis, Yannis

PB - Association for Computing Machinery, Inc

T2 - 31st ACM SIGSOFT International Symposium on Software Testing and Analysis, ISSTA 2022

Y2 - 18 July 2022 through 22 July 2022

ER -

Zhou J, Yang H, Lange J, Liu T. Deadlock prediction via generalized dependency. In Ryu S, Smaragdakis Y, editors, ISSTA 2022 - Proceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis. Association for Computing Machinery, Inc. 2022. p. 455-466. (ISSTA 2022 - Proceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis). doi: 10.1145/3533767.3534377

Deadlock prediction via generalized dependency

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this