ISSN:
1433-3015
Keywords:
Deadlock prevention
;
Petri nets
;
Unfoldings
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mechanical Engineering, Materials Science, Production Engineering, Mining and Metallurgy, Traffic Engineering, Precision Mechanics
Notes:
Abstract Unfoldings of Petri nets (PN) provide a method for the analysis of concurrent systems without restoring the state space of a system. This allows one to overcome the “state explosion” problem. Many properties of the initial PN (boundedness, safety, persistency and hazards) can be checked by constructing the unfolding. A deadlock prevention procedure first detects deadlocks using an unfolding. Then, the first method reduces the unfolding to a set of deadlock-free subunfoldings that cover all live behaviours. The second method uses a direct transformation at the level of the original PN. The methods are implemented as subroutines in the Berkeley program SIS. Although the deadlock detection problem is known to be NP-complete, experimental results show that for highly parallel specifications deadlock prevention by unfoldings is typically more efficient than deadlock prevention based on symbolic BDD (binary decision diagrams) traversal of the corresponding reachability graph.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01438227
Permalink