Petri-Netze

Petri-Netze wurden 1962 von C. A. Petri auf Basis der Graphentheorie entwickelt. Sie eignen sich zur Modellierung, Analyse und Simulation von dynamischen Systemen mit nebenläufigen und nichtdeterministischen Vorgängen, z.B. in Betriebssystemen oder Echtzeitsystemen, aber auch Organisationsabläufen wie in Büros oder Herstellungsverfahren.

Elemente des Petri-Netzes
Das dynamische Verhalten
Hierarchiebildung
Datenstrukturierung
Eignungsschwerpunkte

Elemente des Petri-Netzes

Ein Petri-Netz ist ein gerichteter Graph, der aus Kanten und zwei verschiedenen Arten von Knoten, den Stellen und Transitionen besteht.

Symbol	Benennung	Bedeutung / Bemerkungen
	Stelle (Platz)	Zwischenablage für Informationen. Stellen, von denen aus Kanten zu einer Transition T führen heißen Eingabestellen von T. Stellen, zu denen von einer Transition T aus Kanten führen, heißen Ausgabestellen.
	Transition (Hürde)	Verarbeitung von Daten. Anstelle des Rechtecks sind auch Striche gebräuchlich.
	Kante	Die Kanten dürfen jeweils nur von Stellen zu Transitionen oder von Transitionen zu Stellen führen.
	Marke	Kennzeichnung der Belegung einer Stelle.

Elemente eines Petri-Netzes

	branch oder Verzweigung
	meet, Begegnung oder Wettbewerb
	split oder Aufspaltung
	wait, Sammlung oder Rendevouz

Elementare Verknüpfungen

Das dynamische Verhalten

Das Netz kann als Basis für die Darstellung dynamische Vorgänge dienen. Dazu werden die strukturellen Eigenschaften durch Regeln für das dynamische Verhalten ergänzt. Man kann das Netz als Spielbrett betrachten auf dem ein Spiel mit Marken durchgeführt wird. Das Netz beschreibt das grundsätzliche Verhalten eines Systems, das Spiel simuliert einen bestimmten Ablauf.

Das Beispiel in Systemmodell einer Tankstelle als Petri-Netz vermittelt einen ersten Eindruck. Es erfüllt die folgende Aufgabenstellung:

Eine Selbstbedienungstankstelle hat zwei Zafpsäulen. Zu jeder gehört ein Standplatz, so dass ein Auto betankt werden kann, vorausgesetz, die Zapfsäule ist freigegeben. Die Freigabe der Zapfsäule erfolgt durch einen Tankwart, nachdem er nach dem Betanken kassiert hat.

Systemmodell einer Tankstelle als Petri-Netz

Dabei werden bezüglich der Belegung der Stellen mit Marken zwei Spielregeln unterschieden:

strong rule: diese spezielle Regel legt fest, dass jede Stelle mit höchstens einer Marke belegt sein darf (Datentyp boolean). Damit erfüllt eine Stelle eine Bedingung, die entweder erfüllt ist oder nicht. Das entspricht dem Zustandsgraphen der Automatentheorie. Man spricht von einem Bedingungs-Ereignis-System oder bool-Petri-Netz.
soft rule: bei der allgemeinen Regel ist die Belegung einer Stelle mit mehreren Marken zulässig (Datentyp natural). Dabei können für jede Stelle individuell eine obere Grenze festgelegt oder beliebig viele Marken zugelassen werden. Hier spricht man von einem Stellen-Transitions-Netz oder nat-Petri-Netz.

Bei Transitionen muß man zwischen der

Aktivierung (cocession) und dem
Schalten (firing) unterscheiden.

Eine Transition ist aktiviert:

bei der strong rule, wenn alle ihre Eingabestellen markiert und alle ihre Ausgabestellen nicht markiert sind,
bei der soft rule, wenn alle Eingabestellen mit mindestens einer Marke belegt sind und alle Ausgabestellen mindestens noch eine Marke aufnehmen können.

Das Schalten einer Transition kann nur erfolgen, wenn sie aktiviert ist. Aus allen Eingabestellen wird eine Marke entfernt, in alle Ausgabestellen wird eine Marke gesetzt.

Für Beginn und Dauer des Schaltvorganges gibt es keine generellen Regelungen.

Nachfolgend sind in Schaltvorgänge in Petri-Netzen Beispiele für Aktivierung und Schaltvorgang dargestellt.

nicht feuerbereit		aktiviert	Schaltung erfolgt
	Eingangsbedingung nicht erfüllt
	Ausgang noch belegt

Schaltvorgänge in Petri-Netzen

In bestimmten Situationen ergeben sich Konflikte in einem Netzwerk, die jedoch durch Einfügung steuernder Erweiterungen gelöst werden können.

Verzweigungskonflikt		Wettbewerbskonflikt
	Die Schaltregel gibt keinen Aufschluß darüber, welche Transition schaltet.		Die Transitionen können nicht gleichzeitig schalten, da die Ausgabestelle nur eine Marke aufnehmen kann.
	Zusätzliche Schaltbedingung schafft Klarheit. Jetzt wird "getoggelt".		Hier geht es jetzt nach dem "Reißverschluss-Verfahren".

Konflikte in Petri-Netzen

Neben den dargestellten Grundtypen gibt es verschiedene Modifikationen. Zum Beispiel werden neben den Datentypen boolean und nat auch allgemeinere Datentypen zugelassen. In der Bürowelt sind die Typen Formular oder Akte gebräuchlich.

Oft werden auch weitere Sorten von Stellen und Transitionen zugelassen, z.B. Stellen zur Beschreibung von Fallunterscheidungen. Das bedeutet eine Änderung der allgemeinen Schaltregel.

Je nach ihre Lage im Netz können Stellen oder Transitionen unterschiedliche Bedeutung haben. In der Bedeutung von Stellen und Transitionen nach Lage im Netz sind alle Möglichkeiten dargestellt und erläutert

Symbole	Bedeutung	Beispiel
	Löschung von Objekten.
	Erzeugung von Objekten.
	Verarbeitung oder Weitergabe von Objekten.
	Aufspaltung oder Vervielfachung von Objekten, Beginn einer Nebenläufigkeit.
	Verschmelzung von Objekten, Synchronisationspunkt, Ende einer Nebenläufigkeit.
	Ablage, z.B. Archiv.
	Quelle, Lieferant von Objekten.
	Zwischenablage, Zwischenspeicher.
	Nichtdeterministische Fortsetzung oder willkürliche Verzweigung eines Prozesses und/oder Beginn einer Nebenläufigkeit.
	Synchronisationsstelle, gemeinsamer Speicher für Objekte.

Bedeutung von Stellen und Transitionen nach Lage im Netz

Hierarchiebildung

Transitionen und Stellen können in Teilnetze aufgelöst werden, so wie Teilnetze zu Stellen oder Transitionen zusammengefaßt werden können. Dabei ist zu beachten:

Die Schnittstelle des Teilnetzes zum Restnetz bleibt unverändert, d.h. das Teilnetz, das eine Stelle ersetzt hat eine Stelle als Eingang und eine Stelle als Ausgang. Das Teilnetz, das eine Transition ersetzt hat eine Transition als Eingang und eine Transition als Ausgang.

Hierarchien in Petri-Netzen

Noch einige Anmerkungen zum Beispiel Systemmodell einer Tankstelle als Petri-Netz.

Deutlich wird die Parallelität von Prozessen, denn durch die Verdopplung der Betriebsmittels Zapfsäule und Stellplatz ist ein gleichzeitiges Betanken von zwei Fahrzeugen möglich.
Die Stelle Auto in "Einfahrt" ist ein Verzweigungskonflikt, der hoffentlich durch den Fahrer des Autos gelöst wird.
Den Wettbewerbskonflikt an der Stelle Tankwart verfügbar" wird der Tankwart lösen. Kleine Probleme wie fehlendes Wechselgeld sind in dem Modell nicht berücksichtigt, Sie können ja mal darüber nachdenken.
Das Problem der endlosen Autoschlangen vor den Tankstellen, den Warteschlangen", ist in unserem System ebenfalls nicht berücksichtigt. Es ist - wie so häufig - auf die Straße verlagert. Wenn in der Einfahrt der Tankstelle Stauraum für einige Fahrzeuge vorhanden ist, dann sollten wir in unserem Modell nach der soft rule spielen. Die Stelle Auto in Einfahrt" könnte dann z.B. 5 Marken = Autos aufnehmen. Damit hätten wir eine Warteschlange realisiert.

Vorgehen bei der Modellierung

Bei der Modellierung beginnt man zunächst mit einem sehr abstrakten Netz, dem Instanzen-Kanal-Netz. Instanzen entsprechen den Transitionen, sie sind die aktiven Teile des Netzes; in ihnen läuft etwas ab. Die Kanäle, sie entsprechen den Stellen, sind die passiven Teile. Sie leiten etwas weiter oder sie speichern etwas. Das Petri-Netz mit Instanzen und Kanälen zeigt so ein Beispiel.

Petri-Netz mit Instanzen und Kanälen

In einem zweiten Schritt werden die Kanäle konkretisiert. Der Kundenkanal kann z.B. aus eingehender Briefpost oder Telefonaten für die Bestellungen und ausgehender Paketpost für die Warenlieferung bestehen.

Verfeinerung eines Kanals

Im dritten Schritt werden die Instanzen von außen nach innen verfeinert. Zunächst sucht man nach einer Instanz für jeden dieser verfeinerten Kanäle. Diese neuen Instanzen werden ggf. über neue Kanäle innerhalb der zu verfeinernden Instanz verbunden. Das Beispiel Verfeinerung einer Instanz macht das Vorgehen deutlich.

Verfeinerung einer Instanz

Diese Verfeinerungen von Kanälen und Instanzen werden fortgesetzt bis das bestehende oder geplante System vollständig beschrieben ist. Dabei geht das Kanal-Instanzen-Netz in ein Stellen-Tronsitions-Netz oder gar Bedingungs-Ereignis-Netz über.

Datenstrukturierung

In der ursprünglichen Form der Petri-Netze sind keine Sprachelemente zur Spezifikation und Strukturierung von Daten vorgesehen.

Eignungsschwerpunkte

Mit Hilfe von Petri-Netzen läßt sich ein System als Folge von Zuständen und Ereignissen sehr schnell modellieren. Mit dem Markenspiel" kann das Verhalten bzw. das Fehlverhalten des Systems überprüft werden.