ALDAKHEEL-DISSERTATION-2019.pdf (2.29 MB)
0/0

Deadlock Detector and Solver (DDS)

Download (2.29 MB)
thesis
posted on 01.12.2019 by Eman Abdullah Aldakheel
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.

History

Advisor

Buy, Ugo

Chair

Buy, Ugo

Department

Computer Science

Degree Grantor

University of Illinois at Chicago

Degree Level

Doctoral

Degree name

PhD, Doctor of Philosophy

Committee Member

Kshemkalyani, Ajay Sistla, Prasad Venkatakrishnan, Venkat Alowibdi, Jalal

Submitted date

December 2019

Thesis type

application/pdf

Language

en

Issue date

09/12/2019

Exports