Deadlock prevention using Petri nets and their unfoldings
| Autor: | Michael Kishinevsky, Alexander Taubin, Alex Kondratyev |
|---|---|
| Rok vydání: | 1998 |
| Předmět: |
Computer science
Binary decision diagram Mechanical Engineering Deadlock Petri net Industrial and Manufacturing Engineering Computer Science Applications Tree traversal Control and Systems Engineering Reachability Graph (abstract data type) State space Algorithm Deadlock prevention algorithms Software |
| Zdroj: | The International Journal of Advanced Manufacturing Technology. 14:750-759 |
| ISSN: | 1433-3015 0268-3768 |
| DOI: | 10.1007/bf01438227 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink