Run-time detection of potential deadlocks for programs with locks, semaphores, and condition variables

Rahul Agarwal; Scott D. Stoller

doi:10.1145/1147403.1147413

Run-time detection of potential deadlocks for programs with locks, semaphores, and condition variables

Rahul Agarwal
, Scott D. Stoller

Computer Science

Stony Brook University

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

52 Scopus citations

Abstract

Concurrent programs are notorious for containing errors that are difficult to reproduce and diagnose. A common kind of concurrency error is deadlock, which occurs when some threads are permanently blocked. This paper defines a runtime notion of potential deadlock in programs with locks, semaphores, and condition variables. Informally, an execution has potential for a deadlock if some feasible permutation of the execution results in a deadlock. Feasibility of a permutation is determined by ordering constraints amongst events in the execution. Previous work on run-time detection of potential deadlocks are for programs that use locks. This paper presents run-time algorithms to detect potential deadlocks in programs that use locks (block structured as well as non block structured), semaphores, and condition variables.

Original language	English
Title of host publication	Proceeding of the 2006 Workshop on Parallel and Distributed Systems
Subtitle of host publication	Testing and Debugging, PADTAD '06
Pages	51-59
Number of pages	9
DOIs	https://doi.org/10.1145/1147403.1147413
State	Published - 2006
Event	2006 Workshop on Parallel and Distributed Systems: Testing and Debugging, PADTAD '06 - Portland, ME, United States Duration: Jul 17 2006 → Jul 17 2006

Publication series

Name	Proceeding of the 2006 Workshop on Parallel and Distributed Systems: Testing and Debugging, PADTAD '06
Volume	2006

Conference

Conference	2006 Workshop on Parallel and Distributed Systems: Testing and Debugging, PADTAD '06
Country/Territory	United States
City	Portland, ME
Period	07/17/06 → 07/17/06

Keywords

Algorithms
Reliability

Access to Document

10.1145/1147403.1147413

Cite this

Agarwal, R., & Stoller, S. D. (2006). Run-time detection of potential deadlocks for programs with locks, semaphores, and condition variables. In Proceeding of the 2006 Workshop on Parallel and Distributed Systems: Testing and Debugging, PADTAD '06 (pp. 51-59). (Proceeding of the 2006 Workshop on Parallel and Distributed Systems: Testing and Debugging, PADTAD '06; Vol. 2006). https://doi.org/10.1145/1147403.1147413

@inproceedings{dfd5ad4a99434506a54fa7d2b1d74eb5,

title = "Run-time detection of potential deadlocks for programs with locks, semaphores, and condition variables",

abstract = "Concurrent programs are notorious for containing errors that are difficult to reproduce and diagnose. A common kind of concurrency error is deadlock, which occurs when some threads are permanently blocked. This paper defines a runtime notion of potential deadlock in programs with locks, semaphores, and condition variables. Informally, an execution has potential for a deadlock if some feasible permutation of the execution results in a deadlock. Feasibility of a permutation is determined by ordering constraints amongst events in the execution. Previous work on run-time detection of potential deadlocks are for programs that use locks. This paper presents run-time algorithms to detect potential deadlocks in programs that use locks (block structured as well as non block structured), semaphores, and condition variables.",

keywords = "Algorithms, Reliability",

author = "Rahul Agarwal and Stoller, \{Scott D.\}",

year = "2006",

doi = "10.1145/1147403.1147413",

language = "English",

isbn = "1595934146",

series = "Proceeding of the 2006 Workshop on Parallel and Distributed Systems: Testing and Debugging, PADTAD '06",

pages = "51--59",

booktitle = "Proceeding of the 2006 Workshop on Parallel and Distributed Systems",

note = "2006 Workshop on Parallel and Distributed Systems: Testing and Debugging, PADTAD '06 ; Conference date: 17-07-2006 Through 17-07-2006",

}

Agarwal, R & Stoller, SD 2006, Run-time detection of potential deadlocks for programs with locks, semaphores, and condition variables. in Proceeding of the 2006 Workshop on Parallel and Distributed Systems: Testing and Debugging, PADTAD '06. Proceeding of the 2006 Workshop on Parallel and Distributed Systems: Testing and Debugging, PADTAD '06, vol. 2006, pp. 51-59, 2006 Workshop on Parallel and Distributed Systems: Testing and Debugging, PADTAD '06, Portland, ME, United States, 07/17/06. https://doi.org/10.1145/1147403.1147413

Run-time detection of potential deadlocks for programs with locks, semaphores, and condition variables. / Agarwal, Rahul; Stoller, Scott D.
Proceeding of the 2006 Workshop on Parallel and Distributed Systems: Testing and Debugging, PADTAD '06. 2006. p. 51-59 (Proceeding of the 2006 Workshop on Parallel and Distributed Systems: Testing and Debugging, PADTAD '06; Vol. 2006).

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

TY - GEN

T1 - Run-time detection of potential deadlocks for programs with locks, semaphores, and condition variables

AU - Agarwal, Rahul

AU - Stoller, Scott D.

PY - 2006

Y1 - 2006

N2 - Concurrent programs are notorious for containing errors that are difficult to reproduce and diagnose. A common kind of concurrency error is deadlock, which occurs when some threads are permanently blocked. This paper defines a runtime notion of potential deadlock in programs with locks, semaphores, and condition variables. Informally, an execution has potential for a deadlock if some feasible permutation of the execution results in a deadlock. Feasibility of a permutation is determined by ordering constraints amongst events in the execution. Previous work on run-time detection of potential deadlocks are for programs that use locks. This paper presents run-time algorithms to detect potential deadlocks in programs that use locks (block structured as well as non block structured), semaphores, and condition variables.

AB - Concurrent programs are notorious for containing errors that are difficult to reproduce and diagnose. A common kind of concurrency error is deadlock, which occurs when some threads are permanently blocked. This paper defines a runtime notion of potential deadlock in programs with locks, semaphores, and condition variables. Informally, an execution has potential for a deadlock if some feasible permutation of the execution results in a deadlock. Feasibility of a permutation is determined by ordering constraints amongst events in the execution. Previous work on run-time detection of potential deadlocks are for programs that use locks. This paper presents run-time algorithms to detect potential deadlocks in programs that use locks (block structured as well as non block structured), semaphores, and condition variables.

KW - Algorithms

KW - Reliability

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

U2 - 10.1145/1147403.1147413

DO - 10.1145/1147403.1147413

M3 - Conference contribution

AN - SCOPUS:34247540013

SN - 1595934146

SN - 9781595934147

T3 - Proceeding of the 2006 Workshop on Parallel and Distributed Systems: Testing and Debugging, PADTAD '06

SP - 51

EP - 59

BT - Proceeding of the 2006 Workshop on Parallel and Distributed Systems

T2 - 2006 Workshop on Parallel and Distributed Systems: Testing and Debugging, PADTAD '06

Y2 - 17 July 2006 through 17 July 2006

ER -

Agarwal R, Stoller SD. Run-time detection of potential deadlocks for programs with locks, semaphores, and condition variables. In Proceeding of the 2006 Workshop on Parallel and Distributed Systems: Testing and Debugging, PADTAD '06. 2006. p. 51-59. (Proceeding of the 2006 Workshop on Parallel and Distributed Systems: Testing and Debugging, PADTAD '06). doi: 10.1145/1147403.1147413

Run-time detection of potential deadlocks for programs with locks, semaphores, and condition variables

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this