Petri-Netz

Als Petri-Netze werden Modelle diskreter, vorwiegend verteilter Systeme bezeichnet. Der Informatiker Carl Adam Petri hat sie in den 1960er Jahren ausgehend von endlichen Automaten entwickelt, zunächst noch nicht in der heute gebräuchlichen Form. Dabei hat Petri nach grundlegenden Prinzipien zur Beschreibung nebenläufiger Schaltvorgänge gesucht, die später zu axiomatischen Theorien der Nebenläufigkeit verdichtet wurden.

Heutzutage werden Varianten von Petri-Netzen nicht nur in der Informatik zur Modellierung verwendet, sondern z. B. auch in der theoretischen Biologie, bei Geschäftsprozessen, im Maschinenbau, der Logistik und vielen anderen Gebieten. Viele andere Modellierungstechniken wie z. B. Aktivitätsdiagramme der UML 2 haben Prinzipien der Petri-Netze übernommen.

Allgemeine Symbolik und Beschreibung In der Grundausführung stellt sich ein Netz als ein Graph dar, der aus zwei Arten von Knoten aufgebaut ist, die Stellen (oder auch Plätze) bzw. Transitionen genannt werden. Die Knoten sind durch gerichtete Kanten verbunden, wobei eine Kante genau eine Stelle mit einer Transition oder umgekehrt verbindet. Ursprünglich hat Petri ungetypte Knoten betrachtet. Ein Netz mit solchen Knoten wird als Stellen/Transitions-Netz (kurz: S/T-Netz bzw. P/T-Netz aus dem Englischen zurückübersetzt als Platz/Transitions-Netz) bezeichnet.

Später wurden Netze mit durch Marken getypten Knoten und somit Attributen zu den Knoten eingeführt, welche als Prädikate an Transitionen und Kanten ausgewertet werden. Ein Netz mit Marken und dadurch getypten Knoten wird daher Prädikat/Transitions-Netz genannt, wobei die englischsprachige Bezeichnung Coloured Petri Net (CPN) – gefärbtes Petri-Netz – mindestens genauso häufig anzutreffen ist. Die Stellen können mit beliebig vielen Marken belegt sein. Eine solche Markierung stellt einen verteilten Zustand des Systems dar.

Die Dynamik eines Netzes ergibt sich aus dem Schalten von Transitionen: schaltet eine Transition, so entnimmt sie Marken aus den Stellen in ihrem unmittelbaren Vorbereich und legt Marken in die Stellen in ihrem Nachbereich, und zwar jeweils so viele, wie an den Kanten angegeben ist. Solange die Transition mehr Marken benötigt, als tatsächlich dort liegen, kann sie noch nicht schalten.

Mathematische Darstellung eines Petri-Netzes

Ein P/T-Netz kann als ein Quintupel dargestellt werden, dabei ist (Disjunktheit) und die (in aller Regel endliche) Menge der Stellen die (ebenfalls endliche) Menge der Transitionen die Flussrelation, die die Kanten angibt. Kanten verbinden also stets Stellen mit Transitionen oder andersherum, niemals Stellen mit Stellen oder Transitionen mit Transitionen. die Kantengewichtungsfunktion, erweitert auf durch die Anfangsmarkierung

mini|Abb. 0a: Vier-Jahreszeiten-Netz (1)

Die Dynamik der Netze wird im nächsten Abschnitt erläutert.

Dynamik der Petri-Netze

mini|Beispiel: Schalten einer Transition

Um die Dynamik und weitere Eigenschaften von Petri-Netzen zu beschreiben, sind folgende Definitionen und Bezeichnungen hilfreich.

Vor- und Nachbereich

Der Vorbereich von , bezeichnet mit , ist die Menge aller Knoten, von denen eine Kante zum Knoten führt: .

Der Nachbereich von , bezeichnet mit , ist die Menge aller Knoten, zu denen eine Kante vom Knoten aus führt: .

Beim Schalten einer Transition wird aus jeder Stelle des Vorbereichs der Transition eine Anzahl an Marken entnommen und in jede Stelle des Nachbereichs der Transition eine Anzahl an Marken hinzugefügt. Die Anzahl der hinzugefügten bzw. entnommenen Marken jeder Stelle richtet sich nach dem Gewicht der Kante zwischen der Transition und der Stelle .Dirk Abel: Petri-Netze für Ingenieure. Modellbildung und Analyse diskret gesteuerter Systeme. Springer, Berlin u. u. 1990, ISBN 3-540-51814-2.

Schaltregel

Die Schaltregel in P/T-Netzen stellt sich wie folgt dar: Eine Transition kann aus einer Markierung schalten (notiert ) und das Netz in den Zustand bringen, genau dann, wenn die Schaltbedingung für erfüllt ist für alle Stellen ( ist dann aktiviert bzw. schaltfähig):

und die Folgemarkierung für alle Stellen erfüllt ist: . Das Schalten der aktivierten Transition ergibt also die neue Markierung . Man schreibt dann .

Schaltsequenz und Erreichbarkeit

Eine Folge von Transitionen mit heißt Schaltfolge oder Schaltsequenz. Kann eine Schaltfolge auf eine Markierung angewendet werden, so dass bei jedem Schritt die Schaltbedingung erfüllt ist, so heißt die Schaltsequenz anwendbar auf . Ob eine Schaltfolge anwendbar ist oder wie eine bestimmte Markierung erreicht werden kann, ergibt das Erreichbarkeitsproblem. Gibt es eine anwendbare Schaltfolge , die die Anfangsmarkierung in überführt, so ist die Markierung erreichbar. Die Menge aller erreichbaren Markierungen wird Erreichbarkeitsmenge genannt.

Durch die Schaltregel ergibt sich, nach Art einer operationalen Semantik, ein vielleicht unendlicher beschrifteter Graph mit Wurzel , der Erreichbarkeitsgraph, aus dem alle möglichen Schaltfolgen und damit einhergehenden Zustandsänderungen des Netzes abgelesen werden können. Es ist allerdings zu beachten, dass dies noch keine echt nebenläufige Semantik ist, da von jeder nebenläufigen Ereignismenge nur die Sequentialisierungen als Schaltfolgen betrachtet werden können.

Das Vier-Jahreszeiten-Netz aus Abbildung 0a hat aufgrund seiner sehr simplen Struktur einen sehr einfachen Erreichbarkeitsgraphen, der ebenso wie vier Zustände hat und vier Übergänge, die genau den Transitionen entsprechen.

mini|Abb. 0b: Erweitertes Vier-Jahreszeiten-Netz

Das Netzbeispiel aus Abbildung 0b hat dagegen doppelt so viele erreichbare Zustände, da unabhängig von der Jahreszeit der Sack Reis umgefallen sein kann oder auch nicht. Dieses Netz zeigt auch die Eignung von Petri-Netzen zum Darstellen verteilter Zustände und kausal unabhängiger, „nebenläufiger“ Ereignisse in verschiedenen Teilen des Systems – „In China fällt ein Sack Reis um“ und „a“ können unabhängig voneinander schalten, da sie weder eine gemeinsame Vorbedingung haben noch eines vom anderen abhängt.

Modellieren mit Petri-Netzen

Für Petri-Netze sind ganz unterschiedliche Varianten und Ausprägungen vorgeschlagen worden. In den 1960er und 1970er Jahren wurden zunächst elementare Varianten untersucht; heutzutage werden oft „high-level“-Formen verwendet. Sie sind formal aufwendiger, beschreiben aber das modellierte System intuitiv genauer und unmittelbarer.

Einführendes Beispiel

mini|Abb. 1: abstraktes Modell der Aktion eines Keksautomaten

Als einführendes Beispiel eines High-level-Netzes zeigt Abb. 1 ein von Einzelheiten weitestgehend abstrahierendes Modell eines Keksautomaten: Im Anfangszustand befindet sich eine Münze im Eingabeschlitz des Automaten. Damit kann der Automat einen Schritt durchführen: Er kassiert die Münze und legt eine Keksschachtel in das Ausgabefach. So entsteht der Endzustand. mini|Abb. 2: Modell des Inneren des Keksautomaten

Abbildung 2 verfeinert und erweitert das Modell in seinem Anfangszustand, indem nun das Verhalten des Inneren des Automaten sichtbar wird, zusammen mit der möglichen Rückgabe der eingeworfenen Münze.

Komponenten von Petri-Netzen

Der genaue Sinn der Abbildungen 1 und 2 folgt aus den universellen Modellierungsprinzipien von Petri-Netzen: In einem (gegebenen oder geplanten diskreten) System identifiziert man eine Reihe von Komponenten, die im Petri-Netz-Modell explizit dargestellt werden. Dazu gehören:

Speicherkomponenten, die Gegenstände oder Datenelemente enthalten können (im Beispiel: Eingabeschlitz, Entnahmefach, Kasse, Signalplatz, Keksspeicher, Rückgabe) und denen Bedingungen zugeordnet werden. Im Modell werden sie als Plätze bezeichnet und graphisch als Kreise oder Ellipsen dargestellt; Aktivitäten, die Speicherinhalte verändern können (in Abb. 1: t, in Abb. 2: a, b, c). Alle Aktivitäten werden unbedingt nach Schalten der Plätze ausgeführt. Im Modell werden sie als Transitionen bezeichnet und graphisch als Quadrat oder Rechteck dargestellt. Zustände, also wechselnde Verteilungen von Gegenständen oder Datenelementen in Speicherkomponenten. (Abb. 2 beschreibt einen Zustand mit einer Münze im Eingabeschlitz und 3 Keksschachteln im Keksspeicher. Alle anderen Speicherkomponenten sind leer.) Im Modell bildet eine Verteilung von Marken auf die Plätze eine Markierung mit Bedingungen. Graphische Darstellungen (wie die in Abb. 1 und Abb. 2) zeigen üblicherweise die Anfangsmarkierung, die den Anfangszustand des Systems beschreibt. Gegenstände oder Datenelemente, die im System vorkommen, d. h. erzeugt, transformiert und verbraucht werden (im Beispiel: Münzen, Keksschachteln und Signale). Im Modell werden sie als Marken bezeichnet und graphisch möglichst „intuitiv“ dargestellt. Übergänge von Zuständen in neue Zustände als Beschreibung der Zustandswechsel: (im Beispiel: der Übergang vom Anfangs- zum Endzustand in Abb. 1 und vom Anfangs- zu einem Zwischenzustand in den Abbildungen Abb. 2 und Abb. 3). Im Modell kann man solche Schritte intuitiv als „Fluss von Marken durch die Kanten“ auffassen.

Schritte

mini|Abb. 3: nach Eintritt von a

Von einer gegebenen Markierung eines Petri-Netz-Modells aus ist eine neue Markierung erreichbar, indem eine Transition eintritt. Dazu muss in aktiviert sein. ist in aktiviert, wenn jeder bei endende Pfeil an einem Platz beginnt, der eine Marke enthält, die am Pfeil selbst notiert ist. In Abb. 1 ist t also aktiviert; in Abb. 2 sind a und c aktiviert, nicht aber b. Wenn eine aktivierte Transition eintritt, verschwinden die oben beschriebenen Marken von ihren Plätzen, und für jeden bei beginnenden Pfeil entsteht gemäß seiner Anschrift eine Marke auf dem Platz, wo endet.

Auf diese Weise entsteht in Abb. 1 aus der Anfangsmarkierung durch Eintritt von t die Endmarkierung. Aus Abb. 2 entsteht durch Eintritt von a die in Abb. 3 gezeigte Markierung.

Die „abstrakte“ Marke (schwarzer Punkt) auf dem Signal-Platz von Abb. 3 aktiviert nun zusammen mit einer Keksschachtel im Speicher die Transition b. Indem b eintritt, erscheint schließlich eine Keksschachtel im Entnahmefach. In Abb. 2 ist auch die Transition c aktiviert. Tritt c (statt a) ein, entsteht eine Markierung mit einer Münze in Rückgabe.

Mit der obigen Regel zum Eintritt von Transitionen sieht man unmittelbar, dass oder Münzen im Einwurfschlitz zu entsprechend vielen Schachteln im Entnahmefach führen. Mit einer zweiten Münze im Einwurfschlitz kann die Transition a unmittelbar nach ihrem ersten Eintritt wiederum eintreten, unabhängig vom (ersten) Eintritt von b.

Das Verhalten verteilter Systeme Das obige Beispiel zeigt vielfältige Bezüge zwischen den Aktivitäten eines verteilten Systems. Dementsprechend kann der Eintritt zweier Transitionen in unterschiedlicher Weise zusammenhängen. In Abb. 2 beispielsweise: nichtdeterministisch a und c treten alternativ zueinander ein. Die Münze im Einwurfschlitz aktiviert die beiden Transitionen a und c. Indem eine von beiden eintritt, ist die andere nicht mehr aktiviert. Welche der beiden Transitionen eintritt, wird nicht modelliert. geordnet a tritt vor b ein: Um einzutreten, benötigt b eine Marke, die a vorher erzeugt hat. nebenläufig Nachdem – wie in Abb. 3 – a eingetreten ist, kann mit einer zweiten Münze im Einwurfschlitz (in Abb. 2 nicht dargestellt) a ein zweites (oder c ein erstes) Mal eintreten, nebenläufig zum (d. h. unabhängig vom) Eintritt von b.

Elementare Netze

mini|Abb. 4: elementare Fassung des Keksautomaten