Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben

2013 | Buch

An Example Kapitel lesen Erstes Kapitel lesen

Understanding Petri Nets

Modeling Techniques, Analysis Methods, Case Studies

verfasst von: Wolfgang Reisig

Verlag: Springer Berlin Heidelberg

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

With their intuitive graphical approach and expressive analysis techniques, Petri nets are suitable for a wide range of applications and teaching scenarios, and they have gained wide acceptance as a modeling technique in areas such as software design and control engineering. The core theoretical principles have been studied for many decades and there is now a comprehensive research literature that complements the extensive implementation experience.

In this book the author presents a clear, thorough introduction to the essentials of Petri nets. He explains the core modeling techniques and analysis methods and he illustrates their usefulness with examples and case studies. Part I describes how to use Petri nets for modeling; all concepts are explained with the help of examples, starting with a generic, powerful model which is also intuitive and realistic. Part II covers the essential analysis methods that are specific to Petri nets, introducing techniques used to formulate key properties of system nets and algorithms for proving their validity. Part III presents case studies, each introducing new concepts, properties and analysis techniques required for very different modeling tasks. The author offers different paths among the chapters and sections: the elementary strand for readers who wish to study only elementary nets; the modeling strand for those who wish to study the modeling but not the analysis of systems; and finally the elementary models of the modeling strand for those interested in technically simple, but challenging examples and case studies.

The author achieves an excellent balance between consistency, comprehensibility and correctness in a book of distinctive design. Among its characteristics, formal arguments are reduced to a minimum in the main text with many of the theoretical formalisms moved to an appendix, the explanations are supported throughout with fully integrated graphical illustrations, and each chapter ends with exercises and recommendations for further reading.

The book is suitable for students of computer science and related subjects such as engineering, and for a broad range of researchers and practitioners.

Inhaltsverzeichnis

Frontmatter

Modeling Techniques

Frontmatter
Chapter 1. An Example
Abstract
In this chapter, we will use an example to explain the basic graphical components of Petri nets and how they can be used to model discrete systems.
Wolfgang Reisig
Chapter 2. The Basic Concepts
Abstract
Now we take a little closer look at Petri nets, that is, at their structure of places, transitions and arcs, the fundamental data structure of multisets, the structure of markings and steps and lastly the reachable markings and the final markings. We explain this with the help of the (slightly modified) cookie vending machine.
Wolfgang Reisig
Chapter 3. Common Special Case: Elementary System Nets
Abstract
Petri nets can be used to describe how the control flow and data flow of a distributed algorithm or system interact. However, one often merely wants to express where a control flow currently stands, whether resources are available, how many messages are pending, etc.
For such an abstract view, it is not necessary to distinguish several kinds of tokens: only “black dots” are used as tokens (such tokens already occurred in the cookie vending machine).
Whenever a transition occurs, “exactly one black token flows through each adjacent arc”. Because this does not have to be instead of explicitly stated, the arcs do not have any labelings. Such system nets are called elementary.
Important aspects of distributed and reactive systems can be modeled appropriately with elementary system nets. We will show this with three examples: an abstract variant of the cookie vending machine, the problem of mutual exclusion, and the crosstalk algorithm.
Wolfgang Reisig
Chapter 4. Sequential and Distributed Runs
Abstract
This chapter covers the question of how to formulate individual runs (e.g., calculations, behaviors) of distributed, reactive systems, and what insights into a system such runs can provide.
At first, we will examine the very intuitive term of a sequential run of a system net. Distributed runs require slightly more effort in understanding, but also describe the behavior more accurately. They form the basis for the concept of scenarios, which is covered in the next chapter.
Wolfgang Reisig
Chapter 5. Scenarios
Abstract
A user of a technical or organizational system usually does not need each and every possible behavior of the system. The work is often limited to a few activities that are repeatedly executed. Therefore, it is convenient to consider typical scenarios of a system. A scenario consists of a finite number of elementary actions and terminates in the same state in which it started. Because of this, multiple instances of a scenario can occur multiple times in the same run. A scenario often describes an interaction pattern between a process and its environment, or between two processes.
Typical scenarios of the systems considered thus far are: selling a packet of cookies, visiting one’s critical state once, and sending a message.
Technically, a scenario is constructed as a finite distributed run, whose final marking equals its initial marking. A run of a distributed, reactive system is often composed of many instances of only a few scenarios. If every run can essentially be constructed like this, the system is scenario-based. Understanding the scenarios of a system is often the easiest way to understand the entire system. We will illustrate this using the examples of the mutual exclusion system, the crosstalk algorithm and the cookie vending machine.
Wolfgang Reisig
Chapter 6. Further Notations for Elementary System Nets
Abstract
In the literature, elementary system nets are often extended by additional notations, especially capacities (“no transition can add an (n + 1)th token to a place p”) and arc weights (“n tokens simultaneously flow through an arc”). We will discuss both of these extensions and show that they do not increase the expressiveness of elementary system nets: they can be simulated and are thus merely syntactic sugar. Occasionally, it is possible to use capacities and arc weights to construct very intuitive and clear models. In such cases, they should definitely be used.
However, a transition that is supposed to “test” the number of tokens in a place, or that should be given priority in case of a conflict, is a different matter: such things cannot be simulated within the bounds of elementary system nets.
Wolfgang Reisig
Chapter 7. The Synthesis Problem
Abstract
A system is often modeled by a description of its observable behavior, that is, global states and steps. However, to implement a system, it is often more practical to identify local state components and actions whose cause and effect are limited to a few state components. At first, we will discuss this problem using the example of the light/fan system, and then give the problem a precise form and solve it in the rest of this chapter. The techniques presented here will be used in the case study in Chapter 21 to systematically create an asynchronous hardware architecture.
Wolfgang Reisig
Chapter 8. Composition of Nets
Abstract
It is a general principle of software engineering to assemble small systems into larger ones. This process is called composition. Here we will consider the case of nets with interfaces. Two such nets can be joined together at their interfaces. Interfaces used for asynchronous, directed communication are an important special case. Such open nets are particularly natural: each Petri net can be broken down unambiguously into its set of smallest open nets.
Wolfgang Reisig

Analysis Methods

Frontmatter
Chapter 9. State Properties
Abstract
Important properties of a system pertain to the system’s reachable states. In a system net N, those are the reachable markings. We represent such a state property E of N with an expression a that contains as variables the places of N. If, for a marking M, each place p in a is then replaced with M(p), the expression can be evaluated to either true (“E holds in M”) or false (“E does not hold in M”).
State properties are often expressed as linear equations or inequalities. This chapter covers the form and the validity of such equations and inequalities. How to prove their validity is covered in the following chapters. As an example, we start out with properties of the cookie vending machine. The form of linear equations and inequalities is very simple and is explained in the second section. This is followed by further examples, and finally by ideas about variants of linear equations and inequalities.
Wolfgang Reisig
Chapter 10. Traps and Cotraps of Elementary System Nets
Abstract
Traps form the basis of a particularly simple technique for proving inequalities. They take advantage of the structure of Petri nets, in particular, the simple rule for the occurrence of transitions and the alternating pattern of places and transitions. We will consider traps of elementary system nets first.
Wolfgang Reisig
Chapter 11. Place Invariants of Elementary System Nets
Abstract
Place invariants are the most important analysis technique for system nets. They take advantage of the constant effect of transitions: each time a transition t occurs in the mode β, the same multisets aremoved. The effect of (t, β) is linear. For instance, if the places in • t hold twice as many tokens, then t may occur twice as many times. The mathematics for linear behaviors is the well-known linear algebra with vectors, matrices and systems of equations. In fact, many aspects of Petri nets can be represented and calculated with these structures. We start with linear-algebraic notation for elementary system nets.
Wolfgang Reisig
Chapter 12. Combining Traps and Place Invariants of Elementary System Nets
Abstract
When two valid equations or inequalities are added or subtracted, the result is again a valid equation or inequality. We will show that such calculations substantially increase the expressive power of traps and place invariants. We will start with equations and inequalities of elementary system nets.
Wolfgang Reisig
Chapter 13. Traps and Place Invariants of Generic System Nets
Abstract
Analogously to Chapters 10 and 11, traps and place invariants can also be formulated for generic system nets. Traps are less important here, and we will show only one example. The place-invariant calculus uses expressions as they occur in arc labelings.
Wolfgang Reisig
Chapter 14. Marking and Covering Graphs
Abstract
The marking graph G of a system net N has already been introduced in Section 2.8. Its nodes are the reachable states, its edges the reachable steps of N. We will specify a series of properties of N that are mirrored in G.
However, G is generally infinitely large. We therefore construct the finite covering graph H, which approximates G. A series of necessary or sufficient conditions for some properties of N can be specified by means of H.
Wolfgang Reisig
Chapter 15. Reachability in Elementary System Nets
Abstract
Determining the reachability of an arbitrary marking is one of the interesting, but also one of the most difficult problems of elementary system nets. How to decide whether a marking M of an elementary system net N is reachable (from the initial marking M 0)? If only a finite number of markings is reachable, it is possible to construct each of them and test whether M is among them. If M is reachable, it is also possible to incrementally construct the (possibly infinite) marking graph until M is eventually encountered.
However, if an infinite number of markings is reachable in N, and M is not one of them, then this procedure fails. Nevertheless, the problem can be solved: it is possible to construct a finite set K of reachable markings of N such that M is reachable if and only if M is an element of K. However, this set is incredibly large and it was a long time before the reachability problem was solved.
In this chapter, we will discuss a necessary condition for the reachability and thus a sufficient condition for the unreachability of a marking. At the same time, we will formulate criteria for deciding whether a finite or an infinite number of markings are reachable.
To do this, we will add the marking equation and transition invariants to our set of linear-algebraic tools. The covering graph, too, yields criteria for the reachability of markings and for the finiteness of the set of reachable markings.
Wolfgang Reisig
Chapter 16. Run Properties
Abstract
The question raised in the previous chapter, whether or not it is possible to reach a marking M of a system net, is now strengthened to considering whether or not M is definitely reached.
Wolfgang Reisig
Chapter 17. Free-Choice Nets
Abstract
Traps and place invariants exploit the general structure of Petri nets. For nets with particular structural properties, like the free-choice property, there are further analysis techniques.
Wolfgang Reisig
Chapter 18. Marked Graphs
Abstract
If the free-choice structure is further restricted such that it does not allow any choices at all, the result is a marked graph. This restriction greatly simplifies the analysis. In particular, for each marked graph N, there exists an initial marking such that N is live and 1-bounded.
Wolfgang Reisig
Chapter 19. Well-Formed System Nets
Abstract
Many real systems have a special state in which each individual instance of the system terminates. The system can then be newly instantiated.
A corresponding system net designates one of its reachable markings as the final marking. Furthermore, it satisfies three rather intuitive conditions: 1) The final marking is reachable from any reachable marking. 2) At the end of an instance, no tokens generated in between remain. 3) Each transition can become enabled.
We will see how these three conditions can be verified rather easily.
Wolfgang Reisig

Case Studies

Frontmatter
Chapter 20. Mutual Exclusion
Abstract
By the 1960s, mutual exclusion was recognized as one of the central problems in the organization of computer systems. It arises whenever a resource can be accessed by only one of many processes at any one time (for instance, a processor, a printer or a communications device). While a process is using the resource, it is in its critical state. An agreement between the processes has to guarantee that no two processes can be in their critical states at the same time. We will introduce such an agreement in which processes can only communicate via asynchronous messages.
Wolfgang Reisig
Chapter 21. Asynchronous Hardware
Abstract
This case study describes the systematic construction of asynchronous hardware. It uses the example of an extremely dynamic architecture of a processor that adapts to the current availability of data packets and functions, as well as the varying durations of individual calculation steps.
Wolfgang Reisig
Chapter 22. Network Algorithms
Abstract
Nowadays, computers often function as nodes of a network. In such a network, two nodes can be connected to each other by a communications channel via which they can exchange messages. Such nodes are neighbors.
In a network, there exist some typical tasks: a node sends a message over the network to all other nodes, the nodes synchronize themselves (as far as possible) in cycles or they reach mutual agreements. In this chapter, we discuss solutions to such tasks. Other typical tasks relate to the organization of limited resources, the distribution of tasks or the reinitialization after a critical error.
Such tasks are not easy to solve, because each node generally only has a small number of neighbors. No node “knows” the entire network. Furthermore, a solution is supposed to work not only for a specific network, but for infinitely many, for instance, for all connected or for all acyclic networks.
Wolfgang Reisig

Conclusion

Frontmatter
Chapter 23. Closing Remarks
Abstract
In the 1960s, Carl Adam Petri’s proposals for the modeling of discrete, asynchronous systems were too advanced for practical application and the “wrong” topic for the theory at that time. Accordingly, the responses were limited at first, but at least the MAC project at MIT picked up Petri nets in the late 1960s. In the 1970s, Petri nets were often used (inappropriately) to characterize formal languages. The reachability problem was long regarded as the central challenge in this area. In the early 1980s, “colored” tokens significantly increased the expressive power of Petri nets, and modeling tools enhanced their applicability in larger projects. At the same time, Petri nets entered into a fierce competition with other modeling techniques. The general interest in modeling techniques, especially graphical ones, which had been growing since the 1990s, eventually established Petri nets as an important contribution to computer science. Since 1979, an annual conference, summer schools, workshops and anthologies on specific topics have come on the scene. The number of publications on Petri nets is in the five-digit range.
Wolfgang Reisig
Backmatter
Metadaten
Titel
Understanding Petri Nets
verfasst von
Wolfgang Reisig
Copyright-Jahr
2013
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-33278-4
Print ISBN
978-3-642-33277-7
DOI
https://doi.org/10.1007/978-3-642-33278-4

Premium Partner

    Bildnachweise