Paper Info
Title
Confirmation of deadlock potentials detected by runtime analysis
Abstract
This paper presents a framework for confirming deadlock potentials detected by runtime analysis of a single run of a multi-threaded program. The multi-threaded program under examination is instrumented to emit lock and unlock events. When the instrumented program is executed, a trace is generated consisting of the lock and unlock operations performed during that specific run. A lock graph is constructed which can reveal deadlock potentials in the form of cycles. The effectiveness of this analysis is caused by the fact that successful non-deadlocking runs yield as good, and normally better, information as deadlocking runs. Each cycle is then used to construct an observer that can detect the occurrence of the corresponding real deadlock, should it occur during subsequent test runs; and a controller, which, when composed with the program, determines the optimal scheduling strategy that will maximize the probability for the corresponding real deadlock to occur. The framework is formalized in terms of transition systems and is implemented in Java.
Year
DOI
Venue
2006
10.1145/1147403.1147412
PADTAD
Keywords
Field
DocType
single run,runtime analysis,specific run,deadlocking run,corresponding real deadlock,lock graph,multi-threaded program,optimal scheduling strategy,deadlock potential,instrumented program,false positives,verification,reliability,dynamic program analysis,testing,java,multi threading,deadlock detection,algorithms
Multithreading,Edge chasing,Computer science,Lock (computer science),Scheduling (computing),Deadlock,Real-time computing,Deadlock prevention algorithms,Java,Dynamic program analysis,Distributed computing
Conference
ISBN
Citations 
PageRank 
1-59593-414-6
27
1.02
References 
Authors
18
4
Name
Order
Citations
PageRank
Saddek Bensalem11242106.13
Jean-Claude Fernandez2271.02
Klaus Havelund33522254.55
Laurent Mounier4118779.54