Paper Info
Title
Deadlock-Avoidance Control Of Multithreaded Software: An Efficient Siphon-Based Algorithm For Gadara Petri Nets
Abstract
This paper presents an efficient implementation of an iterative control algorithm for the synthesis of maximally-permissive liveness-enforcing control policies for Gadara nets presented in earlier work. Gadara nets are a special class of Petri nets arising when modeling multithreaded software for the purpose of deadlock analysis and resolution. The considered control synthesis algorithm is based on structural analysis of Gadara nets in terms of a certain type of siphons, called resource-induced deadly-marked siphons. We propose a new customized mixed integer programming formulation to detect these siphons in Gadara nets. We then compare the performance of our customized algorithm with that of a generic siphon detection algorithm for process-resource nets in the context of the iterative control algorithm. Finally, we investigate the scalability of the overall algorithm to large program models.
Year
DOI
Venue
2011
10.1109/CDC.2011.6160535
2011 50TH IEEE CONFERENCE ON DECISION AND CONTROL AND EUROPEAN CONTROL CONFERENCE (CDC-ECC)
Keywords
DocType
ISSN
petri net,structure analysis,multi threading,petri nets,integer programming,programming model,iterative methods
Conference
0743-1546
Citations 
PageRank 
References 
4
0.41
13
Authors
6
Name
Order
Citations
PageRank
Hongwei Liao11159.58
Jason Stanley2393.48
Yin Wang331516.98
StéPhane Lafortune41738181.23
Spyros A. Reveliotis536429.24
Scott Mahlke64811312.08