Petri-Netz

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

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

Inhaltsverzeichnis

1 Funktionsweise
2 Wichtige Begriffe
3 Formale Definition
- 3.1 Schaltbereitschaft
- 3.2 Schaltvorgang
4 Synchronisationskonzepte in Petri-Netzen
5 Erweiterte Petrinetze
6 Anwendungsgebiete
7 Werkzeuge
8 Werkzeuge (für Fortgeschrittene)
9 Siehe auch
10 Literatur
11 Weblinks

[Bearbeiten] 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 Kanten eines Petri-Netzes 1, so wird es auch als Bedingungs-/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 der Kantengewichte Marken entnommen und bei den Ausgangsstellen entsprechend der Kantengewichte 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.

[Bearbeiten] 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 beschränkt, wenn es eine Schranke b gibt so dass nie mehr als b Marken in einer Stelle liegen. Ein Petri-Netz heißt 1-beschränkt, wenn b = 1, 2-beschränkt, wenn b = 2 ...

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, wo man den Konflikt auch als Kontakt bezeichnet, sind es zwei Transitionen, die Marken erzeugen können, aber die Kapazität nicht für beide ausreicht.

[Bearbeiten] Formale Definition

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

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

Die Mengen der Plätze P und Transitionen T sind disjunkt (formal: $P \cap T = \varnothing$ ). Die aktuelle Markierung $m : P \rightarrow \mathbb{N}$ bezeichnet man als Zustand des Petri-Netzes. m(p) ist die Anzahl der Marken auf Platz p.

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

Vorbereich $\bullet t = \lbrace p \in P | (p,t) \in F \rbrace$ , also alle Plätze, von denen eine Kante zur Transition t führt,
Nachbereich $t\bullet = \lbrace p \in P | (t,p) \in F \rbrace$ , also alle Plätze, zu denen eine Kante von der Transition t aus führt.

[Bearbeiten] Schaltbereitschaft

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

∀p ∈ •t : m(p) ≥ W(p,t)
∀p ∈ t•\•t : K(p) ≥ m(p) + W(t,p)
∀p ∈ t•∩•t : K(p) ≥ m(p) - W(p,t) + W(t,p)

[Bearbeiten] Schaltvorgang

Eine aktivierte Transition t kann schalten. Falls sie schaltet, werden für alle Plätze p die Anzahl der Marken wie folgt neu berechnet:

m'(p) = m(p) - W(p,t)	falls p ∈ •t und p ∉ t•
m'(p) = m(p) + W(t,p)	falls p ∉ •t und p ∈ t•
m'(p) = m(p) - W(p,t) + W(t,p)	falls p ∈ •t und p ∈ t•
m'(p) = m(p)	sonst

[Bearbeiten] Synchronisationskonzepte in Petri-Netzen

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

[Bearbeiten] Erweiterte Petrinetze

Um mit Petrinetzen 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.

[Bearbeiten] 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.

[Bearbeiten] Zeiterweiterte Petrinetze

Zusätzlich zu den zeitlosen Transitionen der klassischen Petrinetze 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 Petrinetzen lässt sich noch geschlossen analysieren. Warteschlangensysteme lassen sich als sehr einfache GSPNs darstellen.
DSPN (Deterministic Stochastic Petri Net): Neben den exponentialverteilten zeitbehafteten Transistionen 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 GSPN nie mehr als eine deterministische Transition aktiviert sein kann, ist es überhaupt noch analysierbar. Dennoch sind GSPNs beliebt, da sich viele Sachverhalte mit ihnen sehr viel genauer modellieren lassen und gute numerische Simulationsmethoden existieren.
Allgemeine Stochastische Petrinetze mit beliebigen Schaltzeitverteilungen.

[Bearbeiten] Farbige Petrinetze

Farbige Petrinetze erweitern die zeiterweiterten Petrinetze um Marken mit verschiedenen Farben. Während Marken bei normalen Petrinetzen nicht unterschieden werden können, ist dies durch die Färbung der Marken möglich.

[Bearbeiten] Anwendungsgebiete

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

[Bearbeiten] Werkzeuge

JARP - lokale Java-Anwendung - Editor zum Erstellen und Simulieren von einfachen Petrinetzen. Intuitive Bedienung, veränderbare Größe und Lage von Objekten und Beschreibungen, unbegrenzte Textlänge, einfache Layout-Hilfen. Durch grüne/rote Transitionen eindeutige Visualisierung der feuerbereiten Übergänge. In v1.1 noch einige Bugs beim Öffnen, Speichern und Drucken.

PNS - An S/T Petri-Net Simulation System ist ein sehr leicht bedienbares Java Applet zum schnellen Ausprobieren. Auch als Download-Version verfügbar, kann dann Netze auch speichern (am besten mit java jpns als Application aufrufen). Beschreibungen zu Objekten können lang sein, aber ihre Position ist nicht veränderbar.

[Bearbeiten] Werkzeuge (für Fortgeschrittene)

TimeNET analysiert und simuliert DSPNs, GSPNs, sowie andere Klassen von Petrinetzen numerisch mit sehr guter Performance. Die Version 4.0 ist komplett neu in Java geschrieben. Wurde an der TU Berlin entwickelt.
SIPN-Editor (ein Editor für signalinterpretierte Petrinetze (SIPN)) - Java - Funktioniert nicht ohne Anpassungen von Pfaden.
Low Level Petri net Analyzer - LoLA ist ein expliziter Model-Checker für Petrinetz-Modelle
Integrated Net Analyzer - Dos - Keine Graphische Oberfläche
ARP - Analysator -
Maria - Dos - Analysator
PEP - unter Win nicht ohne cygwin verwendbar
PIPE - Platform Independent Petri Net Editor 2
Renew (Tool für objektbasierte Petrinetze) - Integriert Java und gefärbte Netze. Starke Betonung von Simulation und Systementwicklung
Tina - nichts für jemanden der mal ein wenig mit Petrinetzen rumspielen will
Design/CPN (Tool für die farbigen Petri Netze) - Kostenpflichtig
Visual Object Net++ (Tool für hybride Petri Netze) - Testversion auf 200 Elemente limitiert.
Snoopy - Software tool; dient dem Erstellen und animieren hierarchischer Petri-Netze
Cool Modes (Collide Forschungsgruppe) - Download nach Registrierung möglich; inklusive Simulation, graphischer Oberfläche und mit weiteren visuellen Modellierungssprachen - Java
Peneca Chromos (Technische Universität Ilmenau) - Programm zur Simulation von Petri-Netzen, nur gegen persönliche Unterschrift erhältlich
WoPeD open-source Java-Editor für Workflow Nets und Place/Transition Nets
Netlab (Institut für Regelungstechnik) - Windowsprogramm, graphischem Editor, Analysefunktionen für verschiedene Graphen und Invarianten, Integration in Matlab
Petri-Netz Editor 1.0 (PED) - Ein Windowsprogramm zum Erstellen und Simulieren von Petri-Netzen
Winpetri - Ein Freeware Windowsprogramm zum Erstellen und Simulieren von Petri-Netzen
Geist3d - Eine GPL 3D Graphics Engine inklusive Entwicklungsumgebung die eine Kombination von Petri Netzen und Python als Programmiersprache nutzt.
HPSim - Freeware für Windows: ermöglicht das Erstellen und Simulieren von Petri-Netzen. Oberfläche ist in Englisch, Hilfe in Spanisch und Deutsch

[Bearbeiten] Siehe auch

[Bearbeiten] Literatur

Aalst, Wil van der ; Hee, Kees van: Workflow Management - Models, Methods, and Systems, The MIT Press, 2002, ISBN 0-262-01189-1
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
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: Theoretische Informatik - Petri Netze, Berlin: Springer Verlag, 2003, ISBN 3-540-44289-8
Reisig, Wolfgang: Petrinetze - Eine Einführung, Berlin: Springer, 1990, ISBN 3-540-16622-X
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

[Bearbeiten] Weblinks

Von „http://de.wikipedia.org../../../p/e/t/Petri-Netz_973e.html“

Kategorien: Theoretische Informatik | Parallelverarbeitung