Petrienetz

Ein Petri-Netz ist ein mathematisches Modell von nebenläufigen Systemen. Es ist eine formale Methode der Modellierung von Systemen bzw. Transformationsprozessen. Die ursprüngliche Form der Petri-Netze nennt man auch Bedingungs- oder Ereignisnetz. Petri-Netze wurden durch Carl Adam Petri in den 1960er Jahren definiert. Sie verallgemeinern wegen der Fähigkeit, nebenläufige Ereignisse darzustellen, die Automatentheorie.

Funktionsweise

Einfaches Petri-Netz

Ein Petri-Netz ist ein bipartiter und gerichteter Graph. Er besteht aus Stellen (Places) und Übergängen bzw. Transitionen (Transitions). Stellen und Transitionen sind durch gerichtete Kanten verbunden. Es gibt keine direkten Verbindungen zwischen zwei Stellen oder zwei Transitionen.

Stellen werden als Kreise, Transitionen als Rechtecke dargestellt. Jede Stelle hat eine Kapazität und kann entsprechend viele Token (Marken bzw. Zeichen) enthalten. Ist keine Kapazität angegeben, steht das für unbegrenzte Kapazität oder für eins. Jeder Kante ist ein Gewicht zugeordnet, das die Kosten dieser Kante festlegt. Ist einer Kante kein Gewicht zugeordnet, wird der Wert eins verwendet.

Sind alle Kapazitäten der Stellen und Gewichte der Kanten eines Petri-Netzes 1, so wird es auch als Bedingungs-, Prädikat- oder Ereignis-Netz bezeichnet.

Die Belegung der Stellen heißt Markierung und ist der Zustand des Petri-Netzes.

Transitionen sind aktiviert bzw. schaltbereit, falls sich in allen Eingangsstellen mindestens so viele Marken befinden, wie die Transitionen Kosten verursacht und alle Ausgangsstellen noch genug Kapazität haben, um die neuen Marken aufnehmen zu können. Schaltbereite Transitionen können zu einem beliebigen Zeitpunkt schalten. Beim Schalten einer Transition werden aus deren Eingangsstellen entsprechend den Kantengewichten Marken entnommen und bei den Ausgangsstellen entsprechend den Kantengewichten Marken hinzugefügt. Marken werden in einem Petri-Netz nicht bewegt. Sie werden entfernt und erzeugt!

Die Marken eines Petri-Netzes sind in ihrer einfachsten Form voneinander nicht unterscheidbar. Für komplexere, aussagekräftigere Petri-Netze sind Markeneinfärbungen, Aktivierungszeiten und Hierarchien definiert worden.

Wichtige Begriffe

Lebendigkeit:

Eine Transition heißt

• tot, falls sie unter keiner Folgemarkierung aktiviert ist.
• aktivierbar, falls sie unter mindestens einer Folgemarkierung aktiviert ist.
• lebendig, falls sie in jeder erreichbaren Markierung aktivierbar ist.

Ein Petri-Netz heißt

• tot, falls alle Transitionen tot sind.
• todesgefährdet, falls das Petri-Netz unter einer Folgemarkierung tot ist.
• verklemmungsfrei oder schwach lebendig, falls es unter keiner Folgemarkierung tot ist.
• (stark) lebendig, falls alle Transitionen lebendig sind.

Erreichbarkeit: Eine Markierung eines Petri-Netzes heißt erreichbar, falls es eine Schaltsequenz der Transitionen gibt, welche die Startmarkierung in diese Markierung überführt.

Konservativität: Ein Petri-Netz heißt konservativ, falls die (beliebig) gewichtete Summe der Marken konstant ist.

Beschränktheit: Ein Petri-Netz heißt b-beschränkt, wenn es eine Schranke b gibt, so dass nie mehr als b Marken in einer Stelle liegen.

Sicherheit: Ein Petri-Netz heißt sicher, falls es 1-beschränkt ist.

Konflikt: Es besteht ein Konflikt bei einer nicht nebenläufigen Aktivierung von zwei Transitionen. Im Vorbereich bedeutet das, dass zwei Transitionen die gleiche Marke benötigen um zu schalten. Im Nachbereich sind es zwei Transitionen, die Marken erzeugen können, aber die Kapazität nicht für beide ausreicht.

Kontakt: Eine Transition hat Kontakt, wenn sie nicht schalten kann, weil sonst die Kapazität einer Stelle im Nachbereich überschritten würde.

Formale Definition

Ein Petri-Netz ist ein 6-Tupel (S,T,F,K,W,m₀). Durch das 3-Tupel (S,T,F) ist ein bipartiter und gerichteter Graph definiert.

• S, nichtleere Menge von Stellen S = {s₁,s₂,...,s_|S|}
• T, nichtleere Menge von Transitionen (Übergängen) T = {t₁,t₂,...,t_|T|}
• F, nichtleere Menge der Kanten (Flussrelation) F ⊆ (S × T) ∪ (T × S)
• K, Kapazitäten der Plätze, Kapazitätsfunktion K : S → $\mathbb{N}\,\cup\,\{\infty\}$
• W, Kosten der Kanten, Gewichtsfunktion W : F → $\mathbb{N}$
• m₀, Startmarkierung m₀ : S → $\mathbb{N}$

Die Mengen der Stellen S und Transitionen T sind disjunkt (formal: $S \cap T = \emptyset$). Die aktuelle Markierung $m : S \rightarrow \mathbb{N}$ bezeichnet man als Zustand des Petri-Netzes. m(s) ist die Anzahl der Marken auf Stelle s.

Folgende (Teil-)Mengen sind für $t \in T$ definiert:

• Vorbereich $\bullet t = \lbrace s \in S | (s,t) \in F \rbrace$, also alle Stellen, von denen eine Kante zur Transition t führt,
• Nachbereich $t\bullet = \lbrace s \in S | (t,s) \in F \rbrace$, also alle Stellen, zu denen eine Kante von der Transition t aus führt.

Schaltbereitschaft

Eine Transition t heißt aktiviert, schaltbereit oder hat Konzession, falls gilt:

1. $\forall s \in \bullet t \setminus t\bullet : m(s) \ge W(s,t)$
2. $\forall s \in t\bullet \setminus \bullet t : K(s) \ge m(s) + W(t,s)$
3. $\forall s \in t\bullet \cap \bullet t : K(s) \ge m(s) - W(s,t) + W(t,s)$

Schaltvorgang

Eine aktivierte Transition t kann schalten. Falls sie schaltet, werden für alle Stellen s die Anzahl der Marken m'(s) wie folgt neu berechnet:

$m'(s) = \begin{cases} m(s) - W(s,t) & \text{ falls } s \in \bullet t \text{ und } s \not\in t\bullet\\ m(s) + W(t,s) & \text{ falls } s \not\in \bullet t \text{ und } s \in t\bullet\\ m(s) - W(s,t) + W(t,s) & \text{ falls } s \in \bullet t \text{ und } s \in t\bullet\\ m(s) & \text{ falls } s \not\in \bullet t \text{ und } s \not\in t\bullet \end{cases}$

Aus einer Stelle s im Vorbereich der Transition t werden beim Schalten so viele Marken entnommen, wie es die Kosten W an der entsprechenden Kante (s,t) vorgeben. Entsprechend werden Marken im Nachbereich erzeugt. Eine Stelle s, die weder im Vor- noch im Nachbereich der Transition t liegt, wird nicht verändert, wenn die Transition t schaltet.

Inzidenzmatrix

Die Inzidenzmatrix C eines Petri-Netzes zeigt jeweils an, wie sich die Markenzahl einer Stelle s_i (dargestellt durch die Zeilen der Matrix) durch ein Schalten der Transition t_j (Spalten der Matrix) vergrößert oder verringert.

Sie ist definiert durch:

$C_{ij}:=\begin{cases} -W(s_i,t_j), & \text{ falls } s_i \in \bullet t_j \text{ und } s_i \not\in t_j\bullet\\ W(t_j,s_i), & \text{ falls } s_i \not\in \bullet t_j \text{ und } s_i \in t_j\bullet\\ W(t_j,s_i)-W(s_i,t_j), & \text{ falls } s_i \in \bullet t_j \text{ und } s_i \in t_j\bullet\\ 0 & \text{ sonst}, \end{cases}$

für $1 \leq i \leq m, 1 \leq j \leq n$. Hierbei ist zu beachten, dass Schlingen nur mit der Differenz ihrer beiden Kantengewichte, bei Gleichheit also gar nicht, das heißt nur als 0, in der Inzidenzmatrix C auftauchen^[1].

Synchronisationskonzepte in Petri-Netzen

• Nebenläufige Ausführung
• Semaphore
• Lese-Schreib-Puffer

Erweiterte Petri-Netze

Um mit Petri-Netzen genauere Modelle aufstellen zu können, wurden diese im Laufe der Zeit um neue Elemente erweitert. Daraus entstanden neue Klassen von Petri-Netzen, die einerseits mächtiger sind, andererseits aber schwerer oder gar nicht geschlossen analysiert werden können.

Prioritäten und hemmende Kanten

• Prioritäten werden als Zahlen, beginnend mit 1, neben einer Transition notiert. Wenn zwei zeitlose Transitionen aktiviert sind, schaltet die mit der höheren Priorität.
• Hemmende Kanten verbinden Stellen mit Transitionen. Wenn eine hemmende Kante durch eine Marke in ihrer Ausgangsstelle aktiviert ist, kann die verbundene Transition nicht feuern, auch wenn alle ihre anderen eingehenden Kanten aktiviert sind.

Durch Prioritäten und hemmende Kanten erreichen Petri-Netze die Mächtigkeit der Turingmaschine.

Zeiterweiterte Petri-Netze

Zusätzlich zu den zeitlosen Transitionen der klassischen Petri-Netze wurden Transitionen eingeführt, welche beim Schalten Zeit verbrauchen. Dabei unterscheidet man verschiedene Klassen von Netzen, je nachdem welche Art von zeitverbrauchenden Transitionen in ihnen vorkommen:

• SPN (Stochastic Petri Net): Jede Transition verbraucht Zeit. Die Zeit, die eine Transition beim Schalten verbraucht, ist eine Zufallsvariable und exponentialverteilt. Diese Klasse von Petrinetzen eignet sich nicht zur Modellierung von Synchronisation.
• GSPN (Generalized Stochastic Petri Net): Enthalten exponentialverteilte zeitbehaftete Transitionen und zeitlose Transitionen. Diese Klasse von Petri-Netzen lässt sich noch geschlossen analysieren. Warteschlangensysteme lassen sich als sehr einfache GSPNs darstellen.
• DSPN (Deterministic Stochastic Petri Net): Neben den exponentialverteilten zeitbehafteten Transitionen gibt es auch solche mit deterministischer Schaltzeit. Dieser werden als ausgefüllte Rechtecke gezeichnet. Die Komplexität von DSPNs ist ungleich höher als die von GSPNs: Nur wenn in einem DSPN nie mehr als eine deterministische Transition aktiviert sein kann, ist es überhaupt noch analysierbar. Dennoch sind DSPNs beliebt, da sich viele Sachverhalte mit ihnen sehr viel genauer modellieren lassen und gute numerische Simulationsmethoden existieren.
• Allgemeine Stochastische Petrinetze mit beliebigen Schaltzeitverteilungen.

Farbige Petri-Netze

Farbige Petri-Netze erweitern Marken um verschiedenen "Farben", indem die Marken nun strukturiert und getypt sind. Während Marken bei normalen Petri-Netzen nicht unterschieden werden können, ist dies durch die Färbung der Marken möglich.

Attributierte Petri-Netze

Verallgemeinerte Form der Petri-Netze, bei der Transitionen, Stellen und Konnektoren mit Attributen versehen werden können.

• Die Attributierung der Konnektoren dient dazu, Daten und Objekte durch das Petrinetz zu transportieren.
• Die Attributierung der Stellen dient der Regulierung deren Kapazität.
• Die Attribute von Transitionen dienen der Zeitmodellierung, Verarbeitung der transportierten Daten sowie der bedingten Ausführung von Transitionen.

Anwendungsgebiete

• Asynchroner Schaltkreis
• Datenanalyse
• Nebenläufige Programmierung
• Paralleler Algorithmus
• Softwareentwurf
• Verwaltung von Arbeitsabläufen
• Verifikation von nebenläufigen Prozessen
• Automatisierung (Steuerungstechnik)
• Stoffstromnetz

Siehe auch

• Aktivitätsdiagramm der UML
• Erreichbarkeitsgraph (Petri-Netz)
• Graphentheorie
• Lebendigkeit
• Verifikation
• Verklemmung

Literatur

• Abel, Dirk: Petri-Netze für Ingenieure − Modellbildung und Analyse diskret gesteuerter Systeme, Berlin: Springer Verlag, 1990, ISBN 3-540-51814-2
• Baumgarten, Bernd : Petri-Netze - Grundlagen und Anwendungen, Heidelberg: Spektrum Akademischer Verlag, 1996, ISBN 3-8274-0175-5
• Billington, Jonathan ; Reisig, Wolfgang: Application and Theory of Petri Nets, Springer, 1996, ISBN 3-540-61363-3
• König, Rainer ; Quäck, Lothar: Petri-Netze in der Steuerungs- und Digitaltechnik, München: Oldenbourg, 1988, ISBN 3-486-20735-0
• Petri, Carl Adam: Kommunikation mit Automaten, Bonn: Schriften des Rheinisch-Westfälischen Institutes für instrumentelle Mathematik an der Universität Bonn, 1962
• Priese, Lutz ; Wimmel, Harro: Petri Netze, Berlin: Springer Verlag, 2008, ISBN 978-3-540-76970-5
• Reisig, Wolfgang: Petrinetze - Eine Einführung, Berlin: Springer, 1990, ISBN 3-540-16622-X
• Reisig, Wolfgang ; Rozenberg, Grzegorz: Lectures on Petri Nets, Springer, 1998, ISBN 3-540-65306-6
• Starke, Peter H.: Analyse von Petri-Netz-Modellen, Stuttgart: B.G. Teubner, 1990, ISBN 3-519-02244-3
• Zuse, Konrad: Petri-Netze aus der Sicht des Ingenieurs, Braunschweig: Vieweg, 1980, ISBN 3-528-09615-2

Weblinks

• Einführungskurs mit interaktiven Beispielen
• Fachgruppe "Petrinetze und verwandte Systemmodelle" der Gesellschaft für Informatik
• Übersicht über Softwaretools zur Erstellung von Petri-Netzen
• Petri Nets World (englisch)
• Informelle Einführung

Einzelnachweise

1. ↑ Baumgarten, Bernd: Petri-Netze. Grundlagen und Anwendungen. BI-Wissenschaftsverlag, Mannheim 1990, ISBN 3-411-14291-X