Vorlesung 5 - Eigenschaften von Petrinetzen

• Deadlocks

• Alle Fälle behandelbar

• Alle Fälle beendbar

• Können Tasks paralellisert werden

Tasks die nicht ausgeführt oder beeendet werden könnnen

tote Markierungen vor oder nach beendigung

Kommt nie zu einem Deadlock

• hängt nur von der Struktur ab nicht der markierung

• Stellen passive Komponenten

• Transitionen aktive Komponenten

• Vorbereich, Nachbereich

• Vorwärtsverzweigung, Rückwärtsverzweigung

• Teilnetz, Rand (stellen-, transitionsberandet)

• Hierarchieerweiterung (in der Entwurfsphase eingesetzt, Darstellung unterschiedlicher Sichtweisen)

Nachbereich mehr als ein Knoten

Vorbereich mehr als ein Knoten

Teil eines gesamten Netzes

Bedingungen:

Knoten des Teilnetzes die verbindung zum Rest des gesamten Netzes haben -> Randknoten

Ein Netz darf kein Teilnetz besitzen, das keine Verbindung zum Restznetz hat

Beispiel für ein NICHT-Zusammenhängendes Netz

Jede Stelle ist von überall aus dem Netz erreichbar

Eine Markierung eines Netzes N=(S,T,F) ist eine Abbildung von m: S -> IN

4-Tupel N=(S,T,F,m)

Falls geschaltet werden kann führt das zu einer Folgemarkierung

Schreibweise: [m>

• Zustand: Markierung

• Stellen: Anzahl der Marken die in den Stellen sind

• Tranistiononen: Stellen die Schalten können

• Folgezustand: Markierungen die darauf folgen können

Ein Netz ist beschränkt, durch die höchste Anzahl an Marken in einer Stelle, von allen möglichen Markierungen innerhalb aller Stellen.

Bsp. Wenn ein Netz 10 Stellen hat und durch eine Markierung keine Stelle mehr als 4 Marken erhält ist das Netz mit 4 beschrönkt

Keine Beschränkung

Theoretisch unendlich Marken innerhalb einer Stelle möglich

Auch 1-beschränkt

Beschränkung = 1

• Durch die komplementbildung lässt sich eine Stelle begrenzen.

• Ein Komplement, hat als Vorbereich den Nachbereich der zu begrenzenden Stelle

• Und als Nachbereich den Vorbereich der zu begrenzenden Stelle

• Die Summe aller Marken die sich in diesem System befinden begrenzt die Marken für die zu begrenzende Stelle.

• Transistion ist tot wenn sie durch keine Markierung mehr aktiviert werden kann

• Eine Markierung heißt Tot wenn alle Transistionen tot sind

• Verklemmungsfrei: wenn es keine toten Markierungen gibt

-> In System soll tote Markierung vermieden werden

Ein Netz heißt…

• Lebendig

  • wenn keine Markierung tot ist

  • wenn keine totalen bzw. partiellen Verklemmungen auftreten

• Deadlock

  • Wenn eine Markierung erreicht werden kann, von der keine Transistion mehr schalten kann

• Partiell verklemmt

  • wenn mind. eine Transistion nie wieder schalten kann

• Reversibilität

  • Wenn von jeder Markierung aus, durch schalten der Anfangszustand wieder erreicht werden kann

• Terminiert

  • Wenn die Menge der Schaltungen endlich sind

Minimale Anforderung - soundness

• Beendigungsmöglichkeit: Es sollte immer möglich sein, einen Fall zu beenden. Dies garantiert, dass keine Deadlocks vorhanden sind.

• Richtigkeit der Beendigung: Das Prozessende sollte eindeutig sein, d.h. nach Beendigung eines Falles sollten keine Aufgaben für diesen Fall mehr auszuführen sein.

• Aufgabenerfordernis: Jede Aufgabe sollte die Möglichkeit haben, ausgeführt zu werden, sollte also für den Prozess erforderlich sein.

• für jede von i aus erreichbare Markierung M existiert eine Schaltfolge von M nach o,

  • ∀ M: i → M ⇒ M → o

• die Markierung o ist die einzige von i erreichbare Markierung mit mindestens einer Marke in o,

  • ∀ M: (i → M∧ M ≥o) ⇒ M = o

• es existieren keine toten Transitionen

  • ∀ t∈T ∃ M, M´: i → M → M´

  => für jeden fall terminiert das Netz

  => In diesem Zustand besitzt nur die letzte Stelle eine Marke der rest ist leer

  => es gibt keine toten aufgaben, alles muss druchlaufen werden

Soundness kann bewiesen werden durch Standard-Methoden

Bedingung über eine gewisse Konstantheit der Anzahl der Token eines Netzes N

weist jeder Stelle Token zu, sodass die gewichteten Token konstant bleiben

Folge von Transitionen, die von einer Markierung m aus geschaltet werden kann, um wieder die gleiche Markierung m zu erreichen

Gibt an wie oft welche Transitionen von einer Markierung m aus geschaltet werden müssen, um wieder die gleiche Markierung m zu erreichen.

Betrachtet ein Netz

Zeilen represäntieren die Transaktionen

Spalten represäntieren die Stellen

Befüllung mit -1, 0, 1 je nachdem obn durch die Schaltung einer Transition die Stellen einen Token verlieren, erhalten oder die Anzahl gleich bleibt

Enthält wie oft in einer Schaltfolge eine Schaltung geschaltet wurde so folgt z.B. aus der Schaltfolge (Beispielhafte Schaltfolge für Netz aus Karteikarte davor):

τ = t2 t1 t1 t4 t1 t4 => Vektor qτ = (3 1 0 2)

-> Es wurde 3 mal t1, 1 mal t2, 0 mal t3 und 2 mal t4 geschaltet

Y * I = 0

wobei Y=random Variable und I = Inzidenzvektor

Bsp.:

Folgerung wenn es ein Y gibt, bei dem Yn immer größer 1 ist, dann ist das Netz beschränkt

mit I = Inzidenzmatrix und X random Variable transformiert

wenn es eine Lösung gibt außer Nullvektor ist es der gesuchte Schaltvektor

Bsp:

Matrix Multiplikation

Matrix Addition

Matrix transformation

Gauß-Verfahren

systematische Auflistung aller erreichbaren Markierungen eines Petrinetzes

Seine Knoten sind die erreichbaren Markierungen, seine Kanten die Transitionen und die Flussrichtung stellen die Schritte zwischen den erreichbaren Markierungen von N dar

Beispiel: