Deadlock is a potential problem for all multithreaded programs. Timely detection of deadlock is essential for resolving the error and maintaining forward progress. We developed Pulse, an operating system mechanism that dynamically detects deadlocks in user applications. Pulse speculatively unblocks each process (or thread) that has been blocked for a long time, and executes it ahead. Speculative execution allows Pulse to identify what events a blocked process would generate if it were not blocked. By comparing against the events on which each process is blocked, Pulse can discover the dependences among the processes and events; if the dependences form a circular chain, Pulse reports a potential deadlock. The ability to look into the future allows Pulse to detect deadlocks that involve complex (non-lock-like) resources, which, to the best of our knowledge, no existing tools can detect.

For details about Pulse, please refer to our USENIX'05 paper. We implemented Pulse in the Linux kernel 2.6.8.1. Follow this link to download our code.