Deadlock Detector and Solver (DDS)

Deadlock is found to be one of the most complex problems that can negatively impact the reliability of programs. If deadlocks are not detected and resolved, this can cause permanent thread blockage. The existing deadlock detectors are typically based on timeout and rollback of computations, which results in considerable delays and waste of computing resources. This research presents Deadlock Detector and Solver (DDS), a method and toolset for detecting and resolving deadlocks in Java programs at run-time. DDS efficiently detects deadlocks caused by hold-and wait cycles on Java locks, does not require manual code annotations, and only imposes a modest performance overhead on the running Java program. Upon detecting a deadlock, DDS employs a preemptive approach to break up the deadlock cycle. We assess the effectiveness of DDS on benchmarks of deadlocking and non-deadlocking programs. To preserve semantic correctness of the monitored program, it is crucial that one of the threads in a deadlock be amenable to lock preemption. When this is not the case, we resort to an approach based on software transactional memories—a nonblocking methodology to ensure that any write operation is made atomically. Our empirical findings show that DDS can detect and resolve deadlocks in Java programs without substantial runtime overhead. We conclude that the combination of lock preemption and software transactional memories is an effective method for handling deadlocks at runtime. In addition, applications of the DDS to other lock-based languages, such as C++/pthreads, will be briefly discussed.