Run-Time Detection of Potential Deadlocks for Programs with Locks, Semaphores, and Condition Variables.
Rahul Agarwal and Scott D. Stoller

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 run-time 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.