Paper Info
Title
Gadara nets: Modeling and analyzing lock allocation for deadlock avoidance in multithreaded software
Abstract
Deadlock avoidance in shared-memory multithreaded programs is receiving increased attention as multicore architectures and parallel programming are becoming more prevalent. In our on-going project, called Gadara, the objective is to control the execution of multithreaded programs in order to avoid deadlocks by using techniques from discrete-event control theory. In this project, Petri nets are employed to model parallel programs. This paper formally defines the class of Petri nets that emerges from modeling multithreaded programs, called Gadara nets. Gadara nets are related to, but different from, other classes of nets that have been characterized in deadlock analysis of manufacturing systems. The contributions of this paper include: (i) formal definition of Gadara nets and of controlled Gadara nets; (ii) a behavioral analysis of Gadara nets for liveness and reversibility using siphons; and (iii) identification of a convexity-type property for the set of live markings.
Year
DOI
Venue
2009
10.1109/CDC.2009.5399950
CDC
Keywords
Field
DocType
modeling lock allocation,analyzing lock allocation,petri nets,parallel programming,multithreaded software,multi-threading,operating systems (computers),discrete event control theory,multicore architectures,deadlock avoidance,gadara nets,behavior analysis,petri net,multi threading,shared memory,control theory
Multithreading,Petri net,Lock (computer science),Computer science,Deadlock,Process architecture,Software,Multi-core processor,Distributed computing,Liveness
Conference
ISSN
ISBN
Citations 
0191-2216 E-ISBN : 978-1-4244-3872-3
978-1-4244-3872-3
19
PageRank 
References 
Authors
0.99
9
6
Name
Order
Citations
PageRank
Yin Wang131516.98
Hongwei Liao21159.58
Spyros A. Reveliotis336429.24
Terence Kelly481353.23
Scott Mahlke54811312.08
StéPhane Lafortune61738181.23