Paper Info
Title
Eliminating Concurrency Bugs in Multithreaded Software: A New Approach Based on Discrete-Event Control.
Abstract
Computer hardware is moving from uniprocessor to multicore architectures. One problem arising in this evolution is that only parallel software can exploit the full performance potential of multicore architectures, and parallel software is far harder to write than conventional serial software. One important class of failures arising in parallel software is circular-wait deadlock in multithreaded programs. In our ongoing Gadara project, we use a special class of Petri nets, called Gadara nets, to systematically model multithreaded programs with lock allocation and release operations. In this paper, we propose an efficient optimal control synthesis methodology for ordinary Gadara nets that exploits the structural properties of Gadara nets via siphon analysis. Optimality in this context refers to the elimination of deadlocks in the program with minimally restrictive control logic. We formally establish a set of important properties of the proposed control synthesis methodology, and show that our algorithms never synthesize redundant control logic. We conduct experiments to evaluate the efficiency and scalability of the proposed methodology, and discuss the application of our results to real-world concurrent software.
Year
DOI
Venue
2013
10.1109/TCST.2012.2226034
IEEE Trans. Contr. Sys. Techn.
Keywords
Field
DocType
System recovery,Software,Concurrent computing,Petri nets,Optimal control,Multicore processing,Software algorithms
Uniprocessor system,Petri net,Concurrency control,Computer science,Concurrency,Parallel computing,Deadlock,Software,Control logic,Multi-core processor,Distributed computing
Journal
Volume
Issue
ISSN
21
6
1063-6536
Citations 
PageRank 
References 
13
0.66
14
Authors
7
Name
Order
Citations
PageRank
Hongwei Liao11159.58
Yin Wang231516.98
Jason Stanley3393.48
StéPhane Lafortune41738181.23
Spyros A. Reveliotis536429.24
Terence Kelly681353.23
Scott Mahlke74811312.08