Modellierung Wintersemester 2014/15 Petri-Netze (Folien ... · Modellierung Petri-Netze Grundlagen und Erreichbarkeitsgraphen Motivation: Petrinetze Petrinetzesind ein Formalismus

Modellierung

Vorlesung “Modellierung”Wintersemester 2014/15

Petri-Netze(Folien teilw. von Prof. B. Konig)

Prof. Norbert Fuhr

1 / 1

Modellierung

Petri-Netze

Grundlagen und Erreichbarkeitsgraphen

Motivation: Petrinetze

Petrinetze sind ein Formalismus zur Modellierung vonnebenlaufigen Systemen mit folgenden Eigenschaften:

Vorstellung von Systemubergangen, bei denen gemeinsameRessourcen konsumiert und neu erzeugt werden konnen.

Einfache Modellierung von raumlicher Verteilung derRessourcen, Nebenlaufigkeit, Parallelitat und(Zugriffs-)Konflikten.

Intuitive graphische Darstellung.

Petrinetze werden in der Praxis vielfach benutzt. In UML sindsie abgewandelt als sogenannte Aktivitatsdiagramme (engl.activity diagrams) eingegangen.

Eingefuhrt wurden Sie in der Doktorarbeit von Carl AdamPetri: “Kommunikation mit Automaten”’, Bonn, 1962.

2 / 1

Modellierung

Petri-Netze



Parallelitat versus Nebenlaufigkeit:

Parallelitat

Zwei Ereignisse finden parallel statt, wenn sie gleichzeitigausgefuhrt werden.

Nebenlaufigkeit

Zwei Ereignisse sind nebenlaufig, wenn sie parallel ausgefuhrtwerden konnen (jedoch nicht mussen), das heißt, wenn zwischenihnen keine kausale Abhangigkeit besteht.

Das bedeutet: Nebenlaufigkeit ist der allgemeinere Begriff.

3 / 1

Modellierung

Petri-Netze



Anwendungen fur Petrinetze:

Modellierung von Buroablaufen (work flow, businessprocesses)

Modellierung und Analyse von Web Services

Beschreibung von graphischen Benutzeroberflachen

Prozessmodellierung bei Betriebssystemen

Ablaufbeschreibungen in ingenieurwissenschaftlichenAnwendungen

. . .

4 / 1

Modellierung

Petri-Netze



Beispiel fur ein Petrinetz:

Notation:

Stellen (dargestellt als Kreise): Mogliche Platze fur Ressourcen

Marken (dargestellt als kleine ausgefullte Kreise): Ressourcen

Transitionen (dargestellt durch Rechtecke): Systemubergange

5 / 1

Modellierung

Petri-Netze



Darstellung einer Transition:

Vorbedingung (Marken, die konsumiert werden)

Nachbedingung (Marken, die erzeugt werden)

Die Entfernung der Marken der Vorbedingung und Erzeugung derMarken der Nachbedingung nennt man Schalten bzw. Feuern derTransition.

6 / 1

Modellierung

Petri-Netze



7 / 1

Modellierung

Petri-Netze



7 / 1

Modellierung

Petri-Netze



7 / 1

Modellierung

Petri-Netze



7 / 1

Modellierung

Petri-Netze



7 / 1

Modellierung

Petri-Netze



7 / 1

Modellierung

Petri-Netze



7 / 1

Modellierung

Petri-Netze



7 / 1

Modellierung

Petri-Netze



7 / 1

Modellierung

Petri-Netze



7 / 1

Modellierung

Petri-Netze



7 / 1

Modellierung

Petri-Netze



7 / 1

Modellierung

Petri-Netze



7 / 1

Modellierung

Petri-Netze


Beispiel: Dining Philosophers

Wir betrachten das Beispiel der Dining Philosophers (speisendePhilosophen):

Es sitzen drei Philosophen um einen runden Tisch, zwischen jezwei Philosophen liegt eine Gabel.Philosophen werden von Zeit zu Zeit hungrig und benotigenzum Essen beide benachbarte Gabeln.Jeder Philosoph nimmt zu einem beliebigen Zeitpunkt beideGabeln nacheinander auf (die rechte zuerst), isst und legtanschließend beide Gabeln wieder zuruck.

P2P1

P3

F2F3

F1

8 / 1

Modellierung

Petri-Netze


Beispiel: Dining Philosophers

Modellierung alsPetrinetz:

In dem Netz ist einDeadlock(Verklemmung)erreichbar, d.h.,eine Markierung,bei der keineTransition mehrgeschaltet werdenkann.

E1

W1

E2

F1H1

W2

H2

W3

H3

E3

F2

F3

9 / 1

Modellierung

Petri-Netze


Petrinetze: Definitionen

Petrinetz (Definition)

Ein Petrinetz ist ein Tupel N = (S ,T , •(), ()•,m0), wobei

S eine Menge von Stellen und

T eine Menge von Transitionen ist.

Außerdem gibt es fur jede Transition t zwei Funktionen•t : S → N0, t• : S → N0, die angeben, wieviele Marken t auseiner Stelle entnimmt und in eine Stelle legt.

m0 : S → N0 ist die Anfangsmarkierung (oder initialeMarkierung).

Der Wert •t(s) bzw. t•(s) wird auch als Gewicht bezeichnet.

10 / 1

Modellierung

Petri-Netze


Petrinetze: Definitionen

Markierung

Eine Markierung ist eine Abbildung m : S → N0, die festlegt,wieviele Marken in jeder Stelle liegen.Falls eine Reihenfolge s1, . . . , sn der Stellen fixiert wurde, kann eineMarkierung m auch durch ein Tupel (m(s1), . . . ,m(sn)) dargestelltwerden.

11 / 1

Modellierung

Petri-Netze


Petrinetze: Darstellung

Eine andere Definition stellt die Verbindungen zwischen Stellenund Transitionen und die dazugehorigen Gewichte als Graph dar:

F ⊆ (S ∪ T )× (N0\{0})× (S ∪ T ) (Flussrelation),

wobei nur Kanten der Form (s, n, t) (von Stelle zu Transition) und(t, n, s) (von Transition zu Stelle) mit s ∈ S , t ∈ T erlaubt sind.

Zusammenhang zur eingefuhrten Notation:

(s, n, t) ∈ F ⇐⇒ •t(s) = n 6= 0

(t, n, s) ∈ F ⇐⇒ t•(s) = n 6= 0

Manchmal werden auch unbeschriftete Kante eingefuhrt, denendann mit Hilfe einer Funktion W ein Gewicht zugeordnet wird.

12 / 1

Modellierung

Petri-Netze



Graphische Darstellung:

Stellen werden als Kreise, Transitionen als Quadrate oderRechtecke, Marken als kleine schwarze ausgefullte Kreisedargestellt

Kanten zwischen Stellen und Transitionen werden als Pfeiledargestellt.

Das Gewicht als Kantenbeschriftung kann weggelassenwerden, falls es den Wert eins hat. Die Kante wird ganzweggelassen, falls das Gewicht den Wert 0 hat.

13 / 1

Modellierung

Petri-Netze



Wir betrachten den Zusammenhang zwischen der mathematischenNotation und der graphischen Darstellung genauer:

s1 s2

t1

2

t3

s3

t2

Stellenordnung: s1, s2, s3

S = {s1, s2, s3}T = {t1, t2, t3}•t1(s1) = 1 •t1(s2) = 1 •t1(s3) = 0

t1•(s1) = 0 t1

•(s2) = 0 t1•(s3) = 2

oder: •t1 = (1, 1, 0) t1• = (0, 0, 2)

. . .

m0(s1) = 1 m0(s2) = 2 m0(s3) = 0

oder: m0 = (1, 2, 0)

14 / 1

Modellierung

Petri-Netze



Wir betrachten den Zusammenhang zwischen der mathematischenNotation und der graphischen Darstellung genauer:

s1 s2

t1

2

t3

s3

t2

Stellenordnung: s1, s2, s3

Alternative Darstellung (mit Flussrelati-on):

S = {s1, s2, s3}T = {t1, t2, t3}F = {(s1, 1, t1), (s2, 1, t1), (t1, 2, s3),

(s3, 1, t2), (t2, 1, s1),

(s3, 1, t3), (t3, 1, s2)}m0 = (1, 2, 0)

14 / 1

Modellierung

Petri-Netze


Petrinetze: Dynamik

Operationen auf Markierungen:

Seien m,m′ : S → N0 zwei Abbildungen von Stellen auf naturlicheZahlen.

Ordnung

Es gilt m ≤ m′, falls fur alle s ∈ S gilt: m(s) ≤ m′(s).

Addition

Wir definieren m′′ = m ⊕m′, wobei m′′ : S → N0 mitm′′(s) = m(s) + m′(s) fur alle s ∈ S .

Subtraktion

Wir definieren m′′ = m m′, wobei m′′ : S → N0 mitm′′(s) = m(s)−m′(s) fur alle s ∈ S . Dabei gilt n − k = 0, fallsn, k ∈ N0, n < k (modifizierte Subtraktion).

15 / 1

Modellierung

Petri-Netze


Petrinetze: Dynamik

Weitere Definitionen:

Aktivierung

Eine Transition t ist unter einer Markierung m aktiviert, falls•t ≤ m gilt. (D.h., falls genug Marken vorhanden sind, um dieTransition zu schalten.)

Schalten

Sei m eine Markierung und t eine Transition, die fur m aktiviertist. Dann kann t schalten, was zu der Nachfolgemarkierungm′ = m •t ⊕ t• fuhrt. Symbolisch m[t〉m′.

16 / 1

Modellierung

Petri-Netze


Petrinetze: Dynamik

Weitere Definitionen:

Erreichbarkeit

Eine Markierung m heißt erreichbar in einem Netz, falls es eineFolge von Transitionen t1, . . . , tn gibt mit m0[t1〉m1 . . .mn−1[tn〉m,wobei m0 die Anfangsmarkierung ist.

In diesem Fall schreibt man auch m0[t1 . . . tn〉m oder m0[t〉m mitt = t1 . . . tn.

Die Sequenz t heißt auch Schaltfolge. Auch die leere Schaltfolget = ε is moglich. In diesem Fall andert sich die Markierung nicht(m[ε〉m, fur jede Markierung m).

17 / 1

Modellierung

Petri-Netze


Petrinetze: Dynamik

s1 s2

t1

2

t3

s3

t2

Die Markierung m2 = (1, 1, 1) ist inzwei Schritten erreichbar:

•t1 = (1, 1, 0) ≤ (1, 2, 0) = m0

m1 = m0 •t1 ⊕ t1• = (1, 2, 0)

(1, 1, 0)⊕ (0, 0, 2) = (0, 1, 2)

•t2 = (0, 0, 1) ≤ (0, 1, 2) = m1

m2 = m1 •t2 ⊕ t2• = (0, 1, 2)

(0, 0, 1)⊕ (1, 0, 0) = (1, 1, 1)

Es gilt also: m0[t1〉m1[t2〉m2

18 / 1

Modellierung

Petri-Netze


Petrinetze: Dynamik

Zustandsubergangsdiagramm eines Petrinetzes

Sei N = (S ,T , •(), ()•,m0) ein Petrinetz. Dann besteht das zu Ngehorende Zustandsubergangsdiagramm aus folgendenKomponenten:

Menge der Beschriftungen L: Menge aller Transitionen

Zustandsmenge Z : Menge aller erreichbaren Markierungen

Ubergangsmenge U: (m, t,m′) ∈ U ⇐⇒ m[t〉m′.Startzustand z0: die Anfangsmarkierung m0

Das Zustandsubergangsdiagramm eines Petrinetzes heißt auchErreichbarkeitsgraph.

19 / 1

Modellierung

Petri-Netze


Petrinetze: Dynamik

Beispiel: Bestimme den Erreichbarkeitsgraph fur das folgendeBeispielnetz

s1 s2

t1

2

t3

s3

t2

20 / 1

Modellierung

Petri-Netze


Petrinetze: Dynamik

Erreichbarkeitsgraph fur das Beispielnetz:

��

(1, 2, 0)

t1��

(0, 1, 2)t3 //

t2

##

(0, 2, 1)t3 //

t2pp

(0, 3, 0)

(1, 1, 1)t2 //

t1��

t3

DD

(2, 1, 0)

t1��

(0, 0, 3)

t3

MM

t2// (1, 0, 2)

t2//

t3cc

(2, 0, 1)t2//

t3pp

(3, 0, 0)

21 / 1

Modellierung

Petri-Netze


Petrinetze: Dynamik

Frage: Wie kann ein beliebiges Zustandsubergangsdiagramm in einPetrinetz umgewandelt werden, das als Erreichbarkeitsgraph wiederdas ursprungliche Zustandsubergangsdiagramm besitzt?

Idee:

Zustande werden zu Stellen

Ubergange werden zu Transitionen

die Stelle, die den Anfangszustand darstellt, ist als einzige zuBeginn markiert

Aber:

das entstandene Petrinetz enthalt keinerlei Nebenlaufigkeit

bei der Umwandlung

Petrinetz → Zustandsubergangsdiagramm → Petrinetz

wird das zweite Petrinetz im allgemeinen viel großer als daserste

22 / 1

Modellierung

Petri-Netze


Petrinetze: Dynamik

Beispiel: Umwandlung eines Zustandsubergangsdiagramms in einPetrinetz

c

e bd

aa

bd e

c

23 / 1

Modellierung

Petri-Netze

Eigenschaften von Petrinetzen, Uberdeckbarkeitsgraphen

Petrinetze: Beschranktheit

Sichere, beschrankte und unbeschrankte Netze

Sei N ein Petrinetz. Das Netz N heißt

beschrankt, wenn es eine Konstante c ∈ N0 gibt, so dass furjede erreichbare Markierung m und jede Stelle s gilt, dassm(s) ≤ c .

sicher (oder auch 1-sicher), wenn

Fur jede Transition t und fur jede Stelle s gilt •t(s) ≤ 1und t•(s) ≤ 1, d.h., alle Gewichte sind hochstens 1 undfur jede erreichbare Markierung m und jede Stelle s gilt,dass m(s) ≤ 1.

unbeschrankt, falls es fur jede Konstante c ∈ N0 eineerreichbare Markierung m und eine Stelle s gibt mit m(s) > c .

Aufgabe: Finde ein Beispiel fur ein unbeschranktes Netz.24 / 1

Modellierung

Petri-Netze


Petrinetz-Beispiel: Keksautomat

Wir modellieren einen Keksautomaten mit folgenden Bestandteilen:

extern: Einwurfschlitz, Entnahmefach

intern: Keksspeicher, Kasse, Signalweiterleitung (der Einwurfeiner Munze soll ein Signal erzeugen, das die Ausgabe einesKekses triggert)

Nach: “Petrinetze – Modellierungstechnik, Analysemethoden,Fallstudien” von W. Reisig

25 / 1

Modellierung

Petri-Netze



Munze einwerfen

Einwurfschlitz Signal

Einwurf moglich kein Signal

Kasse

Entnahmefach

Schachtel entnehmen

Keksspeicher

26 / 1

Modellierung

Petri-Netze



Ist der Keksautomat so in Ordnung?

Problem: Sobald der Keksspeicher leer ist, kann immer noch eineMunze eingeworfen werden, die dann nicht zuruckgegeben wird.

Es gibt verschiedene Losungen fur dieses Problem: Ruckgabe derMunze, Keks-Zahler, . . .

27 / 1

Modellierung

Petri-Netze


Petrinetze: Lebendigkeit und Verklemmungen

Wir betrachten nun Begriffe wie Lebendigkeit und Deadlock (=Verklemmung).

(Starke) Lebendigkeit

Ein Petrinetz N heißt (stark) lebendig, wenn es fur jede Transitiont und fur jede erreichbare Markierung m eine Markierung m′ gibt,die von m erreichbar ist und unter der t aktiviert ist.

Fur den Erreichbarkeitsgraph bedeutet dies: von jedem Knoten desGraphen aus ist ein Ubergang erreichbar, der mit der Transition tbeschriftet ist.

28 / 1

Modellierung

Petri-Netze



Schwache Lebendigkeit

Ein Petrinetz N heißt schwach lebendig, wenn es fur jede Transitiont eine erreichbare Markierung m gibt, unter der t aktiviert ist.

Fur den Erreichbarkeitsgraph bedeutet dies: fur jede Transition gibtes mindestens einen Ubergang, der mit der Transition t beschriftetist.

29 / 1

Modellierung

Petri-Netze



Verklemmung

Ein Petrinetz N enthalt ein Deadlock oder eine Verklemmung,wenn es eine erreichbare Markierung m gibt, unter der keineTransition aktiviert ist.

Fur den Erreichbarkeitsgraph bedeutet dies: es gibt einen Knoten,von dem aus es keinen Ubergang gibt.

Ein Netz, das keine Verklemmung enthalt, heißt verklemmungsfrei.

30 / 1

Modellierung

Petri-Netze



Eigenschaften der (starken) Lebendigkeit

Fur Netze, deren Transitionsmenge nicht leer ist, gilt: jedes (stark)lebendige Netz ist sowohl verklemmungsfrei, als auch schwachlebendig.

31 / 1

Modellierung

Petri-Netze



Beispiele fur Lebendigkeit und Verklemmungen:

Ein Beispiel fur ein (stark)lebendiges Netz . . .

32 / 1

Modellierung

Petri-Netze



Ein Beispiel fur einschwach lebendiges undverklemmungsfreies Netz,das jedoch nicht (stark)lebendig ist . . .

33 / 1

Modellierung

Petri-Netze



Ein Beispiel fur einverklemmungsfreies Netz,das jedoch nicht schwachlebendig ist . . .

34 / 1

Modellierung

Petri-Netze



Ein Beispiel fur einschwach lebendiges Netz,das jedoch eineVerklemmung enthalt . . .

35 / 1

Modellierung

Petri-Netze



Ein Beispiel fur ein Netz,das eine Verklemmungenthalt und das auch nichtschwach lebendig ist . . .

36 / 1

Modellierung

Petri-Netze



Uberblick uber die verschiedenen Netzklassen (unter derVoraussetzung, dass jedes Netz mindestens eine Transitionenthalt):

verklemmungs-freie Netze

schwach lebendigeNetze

Netzelebendigestark

alle Petrinetze

37 / 1

Modellierung

Petri-Netze


Petrinetze: Uberdeckbarkeitsgraph

Beobachtung: Ein Petrinetz ist unbeschrankt genau dann, wennsein Erreichbarkeitsgraph unendlich groß ist.

Gibt es in diesem Fall trotzdem noch eine graphische Darstellung,die “in gewisser Weise” alle erreichbaren Markierungenreprasentiert?

Uberdeckbarkeitsgraph

38 / 1

Modellierung

Petri-Netze



Zugrundeliegende Ideen:

Das Verhalten von Petrinetzen ist “monoton”, d.h., jedeSchaltfolge ist auch dann noch moglich, wenn man zusatzlicheMarken hinzufugt.

Wenn im Erreichbarkeitsgraph zwei Markierungen m,m′

existieren, so dass gilt:

m ist echt kleiner als m′ (in Zeichen m < m′, d.h.,m ≤ m′ und m 6= m′) undes gibt einen Pfad von m zu m′,

dann kann man die Transitionsfolge von m zu m′ noch einmalschalten und erhalt wiederum eine großere Markierung m′′.

39 / 1

Modellierung

Petri-Netze



Konstruktion des Uberdeckbarkeitsgraphen

Fuhre zunachst wie gewohnt die Konstruktion desErreichbarkeitsgraphen aus.

Sobald eine neue Markierung m′ hinzugefugt wird, wobei eseine Vorgangermarkierung m mit m < m′ gibt . . .

m0 m′m

. . . ersetze m′ durch eine (ω-)Markierung m mit folgendenEigenschaften:

m(s) = m′(s), falls m(s) = m′(s), undm(s) = ω, falls m(s) < m′(s), wobei s ∈ S .

Mache dann mit der Konstruktion weiter, solange bis keineMarkierungen mehr hinzugefugt werden konnen.

40 / 1

Modellierung

Petri-Netze



Bemerkungen:

Die neu erzeugten besonderen ω-Markierungen ordnen einerStelle “unendlich” viele Marken (reprasentiert durch ω).

Dies nimmt das wiederholte Schalten der Transitionsfolge vonm zu m′ vorweg, die in den ω-Stellen beliebig viele Markenproduzieren kann.

Fur ω-Markierungen gilt beim Schalten von Transitionen:ω + k = ω und ω − k = ω. Außerdem gilt ω als großer alsjede naturliche Zahl.

Der englische Name fur Uberdeckbarkeitgraphen ist coverabilitygraphs.

41 / 1

Modellierung

Petri-Netze



Beispiel:

s1

t2

t1

s3

s2

t3

Reihenfolge der Stellen:s1, s2, s3

��

(1, 0, 0)t3 //

t1��

(0, 0, 0)

(0, 1, 0)

t2��

(1, 0, ω)t3 //

t1��

(0, 0, ω)

(0, 1, ω)

t2

ZZ

42 / 1

Modellierung

Petri-Netze



Eigenschaften des Uberdeckbarkeitsgraphen (I)

Die Konstruktion des Uberdeckbarkeitsgraphen terminiertimmer nach endlich vielen Schritten.

ω-Markierungen treten genau dann auf, wenn das Netzunbeschrankt ist. (D.h., der Uberdeckbarkeitsgraph kann auchdazu verwendet werden, um zu uberprufen, ob ein Netzunbeschrankt ist.)

43 / 1

Modellierung

Petri-Netze



Eigenschaften des Uberdeckbarkeitsgraphen (II)

Sei N ein Netz und G der dazugehorige Uberdeckbarkeitsgraph.Dann gilt:

Fur jede erreichbare Markierung m von N gibt es einenKnoten m′ in G , mit m ≤ m′.

Fur jeden Knoten m′ in G und jedes i ∈ N0 gibt es eineerreichbare Markierung m in N, so dass fur alle Stellen s gilt:

m(s) = m′(s), falls m′(s) 6= ωm(s) ≥ i , falls m′(s) = ω.

Frage: Ist fur eine ω-Markierung m′ in G vielleicht sogar jedeMarkierung m von N mit m ≤ m′ erreichbar?

44 / 1

Modellierung

Petri-Netze



Nein! Gegenbeispiel:

s1

t1

s2

2

Reihenfolge der Stellen:s1, s2

��

(1, 0)

t1��

(1, ω)

t1

HH

Die Markierung (1, 1) ist kleiner als (1, ω), ist aber in dem Netznicht erreichbar.

45 / 1

Modellierung

Petri-Netze


Petrinetze: Kausalitat, Nebenlaufigkeit, Konflikt

Wichtige Begriffe bei Petrinetzen sind Nebenlaufigkeit, Konfliktund Kausalitat. Wir beschaftigen uns damit etwas genauer.

Kausalitat

In einem Petrinetz N ist die Transition t1 notwendige Bedingungfur das Schalten von t2 genau dann, wenn fur alle Schaltfolgen tgilt:

falls m0[tt2〉m fur eine Markierung m, dann enthalt t dieTransition t1.

46 / 1

Modellierung

Petri-Netze



Beispiel fur Kausalitat:

t1

t2

t3

t4

t1 ist eine notwendige Bedingung fur t4,

aber t2 ist keine notwendige Bedingung fur t4. Denn nichtjede Schaltfolge, die zu t4 fuhrt, enthalt t2 (z.B. t = t1t3).Das gleiche gilt fur t3.

47 / 1

Modellierung

Petri-Netze



Eigenschaften der Kausalitat

Wenn t1 eine notwendige Bedingung fur t2 ist, und t2 einenotwendige Bedingung fur t3 ist, dann ist t1 eine notwendigeBedingung fur t3. (Transitivitat)

48 / 1

Modellierung

Petri-Netze



Nebenlaufigkeit

Eine Menge T ′ = {t1, . . . , tn} ⊆ T von Transitionen heißtnebenlaufig aktiviert unter der Markierung m, wenn

•t1 ⊕ · · · ⊕ •tn ≤ m.

D.h., die Markierung m enthalt genug Marken, um alleTransitionen “gleichzeitig” zu feuern.

Eigenschaften der Nebenlaufigkeit

Wenn die Transitions-Menge T ′ unter der Markierung mnebenlaufig ist, so ist auch jede Teilmenge von T ′ unter mnebenlaufig.

49 / 1

Modellierung

Petri-Netze



Beispiele fur Nebenlaufigkeit:

t1

t2

t3

t4

Die Menge {t2, t3} ist nebenlaufig unter der Anfangsmarkierung.

50 / 1

Modellierung

Petri-Netze



t2t1 t3

Die Menge T ′ = {t1, t2, t3}ist nebenlaufig unter derAnfangsmarkierung.

51 / 1

Modellierung

Petri-Netze



t2t1 t3

Die Mengen {t1, t2} {t2, t3}und {t1, t3} sind allenebenlaufig unter derAnfangsmarkierung. Dies giltjedoch nicht fur {t1, t2, t3}.

52 / 1

Modellierung

Petri-Netze



t1 t3t2

Die Mengen {t1, t3} und{t2, t3} sind alle nebenlaufigunter der Anfangsmarkierung.Dies gilt jedoch nicht fur dieMengen {t1, t2} und{t1, t2, t3}.

Dieses Beispiel zeigt auch, dass Nebenlaufigkeit nicht transitiv ist:t1 ist nebenlaufig zu t3, t3 ist nebenlaufig zu t2, jedoch sind t1 undt2 nicht nebenlaufig.

53 / 1

Modellierung

Petri-Netze



Nebenlaufigkeit (Konsequenzen)

Wenn eine Menge T ′ von Transitionen nebenlaufig ist, so ist jedebeliebige Anordnung dieser Transitionen eine Schaltfolgeausgehend von m.

Das heißt, fur jede Sequenz t, in der jede Transitionen aus T ′

genau einmal vorkommt, gibt es eine Markierung m′ mit m[t〉m′.Die Markierung m′ ist durch T ′ eindeutig bestimmt.

54 / 1

Modellierung

Petri-Netze



Nebenlaufige Transitionen fuhren daher in Erreichbarkeitsgraphenzu Strukturen, die die Form eines Quadrats (Diamond) oder(hoherdimensionalen) Wurfels haben.

Beispiel fur ein Quadrat:

t1 t2

s1 s2 (1, 1)t1 //

t2��

(0, 1)

t2��

(1, 0)t1 // (0, 0)

55 / 1

Modellierung

Petri-Netze



Beispiel fur einen Wurfel:

t1 t2

s2s1 s3

t3

(1, 1, 1)t1 //

t2

��

t3 %%

(0, 1, 1)

t2

��

t3 %%

(1, 1, 0)t1 //

t2

��

(0, 1, 0)

t2

��

(1, 0, 1)t1 //

t3 %%

(0, 0, 1)

t3 %%

(1, 0, 0)t1 // (0, 0, 0)

56 / 1

Modellierung

Petri-Netze



Frage: Wenn jede Anordnung von Transitionen in T ′ eineSchaltfolge darstellt, ist dann T ′ automatisch nebenlaufig (untereiner Markierung m)?

Nein! Gegenbeispiel:

t1 t2

57 / 1

Modellierung

Petri-Netze



Schlinge

Ein Schlinge (oder Schleife) in einem Netz N besteht aus einerTransition t und einer Stelle s mit •t(s) > 0 und t•(s) > 0.

Graphisch:t s

n

m

Fur schlingenfreie Netze gilt:

Sei N ein schlingenfreies Netz, sei m eine Markierung und T ′ eineMenge von Transitionen, so dass jede Anordnung der Transitionenin T ′ von m aus schaltbar ist. Dann ist T ′ nebenlaufig.

58 / 1

Modellierung

Petri-Netze



Konflikt

Zwei Transitionen t, t ′ ∈ T stehen unter der Markierung m inKonflikt genau dann wenn:

t und t ′ sind beide unter m aktiviert und

die Menge {t, t ′} ist unter m nicht nebenlaufig.

Anschaulich: nur eine der beiden Transitionen kann schalten.

Das liegt immer daran, dass sie eine gemeinsame Stelle in denVorbedingungen haben. D.h., es gibt eine Stelle s mit •t(s) ≥ 1und •t ′(s) ≥ 1.

59 / 1

Modellierung

Petri-Netze



Beispiel fur einen Konflikt:

t1 t2 t3

Unter der Anfangsmarkierung steht t1 in Konflikt mit t2.Außerdem steht t2 in Konflikt mit t3.

Jedoch steht t1 nicht in Konflikt mit t3 (keine Transitivitat derKonfliktrelation).

60 / 1

Modellierung

Petri-Netze



Bemerkung: auf bestimmten Arten von azyklischen Netzen(sogenannte Occurrence-Netze) kann man Begriffe wie Kausalitat,Nebenlaufigkeit und Konflikt noch klarer herausarbeiten.

Zwei Transitionen sind in solchen Netzen immer entweder kausalabhangig, nebenlaufig oder in Konflikt, unabhangig von derMarkierung.

61 / 1

Modellierung

Petri-Netze

Inzidenzmatrizen und Invarianten

Petrinetze: Invarianten

Kurze Einfuhrung in Matrizen und Vektorrechnung:

Matrix

Seien m, n ∈ N0. Eine m×n-Matrix C (uber den ganzen Zahlen Z)besteht aus m · n Eintragen

Ci ,j ∈ Z fur i ∈ {1, . . . ,m}, j ∈ {1, . . . , n}

Sie wird folgendermaßen dargestellt:

C =

C1,1 . . . C1,n

.... . .

...Cm,1 . . . Cm,n

62 / 1

Modellierung

Petri-Netze



Bemerkungen:Eine m×n-Matrix besteht also aus m Zeilen der Lange n, oder –anders ausgedruckt – aus n Spalten der Lange m.

Dabei heißt m Zeilendimension und n Spaltendimension der Matrix.

Eine Matrix, fur die m = n gilt, heißt quadratisch. Die Matrizen,die wir im Folgenden betrachten werden, sind nichtnotwendigerweise quadratisch.

63 / 1

Modellierung

Petri-Netze



Spaltenvektor

Ein Spaltenvektor (oder Vektor) ~u der Dimension n ist einen×1-Matrix, d.h., er hat folgendes Aussehen.

~u =

u1...un

Wir betrachten im Folgenden immer Spaltenvektoren mitEintragen aus Z.

64 / 1

Modellierung

Petri-Netze



Bemerkungen:

Gegeben sei eine Markierung m = (m(s1), . . . ,m(sn)). Dannentspricht dieser Markierung der Spaltenvektor

~m =

m(s1)...

m(sn)

Spaltenvektoren kann man – wie Markierungen – addieren.Dabei werden die Komponenten paarweise addiert:u1

...un

+

v1...vn

=

u1 + v1...

un + vn

65 / 1

Modellierung

Petri-Netze



Matrizen konnen miteinander multipliziert werden. Wir betrachtenzunachst die Multiplikation einer Matrix mit einem Spaltenvektor.

Multiplikation einer Matrix mit einem Spaltenvektor

Sei C eine m×n-Matrix und ~u ein Spaltenvektor der Dimension n.Dann ist C · ~u folgender Spaltenvektor:

C ·~u =

C1,1 . . . C1,n

.... . .

...Cm,1 . . . Cm,n

·u1

...un

=

C1,1 · u1 + · · ·+ C1,n · un. . .

Cm,1 · u1 + · · ·+ Cm,n · un

Das heißt, in der i-ten Zeile des Spaltenvektors steht der Eintrag∑n

j=1 Ci ,j · uj .

66 / 1

Modellierung

Petri-Netze



Zeilenvektor

Ein Zeilenvektor u der Dimension n ist eine 1×n-Matrix, d.h., erhat folgendes Aussehen.

u =(u1 . . . un

)Wir betrachten im Folgenden immer Zeilenvektoren mit Eintragenaus Z.

67 / 1

Modellierung

Petri-Netze



Zeilenvektoren und Tupel:Im folgenden werden wir Zeilenvektoren im wesentlichen mitn-Tupeln gleichsetzen. Eine Markierung m = (m(s1), . . . ,m(sn)),d.h., ein Tupel aus Nn

0 schreiben wir auch als folgendenZeilenvektor:

m =(m(s1) . . . m(sn)

)

68 / 1

Modellierung

Petri-Netze



Multiplikation einer Matrix mit einem Zeilenvektor

Sei C eine m×n-Matrix und u ein Zeilenvektor der Dimension m.Dann ist u · C folgender Zeilenvektor der Dimension n:

u · C =(u1 . . . um

)·

C1,1 . . . C1,n

.... . .

...Cm,1 . . . Cm,n

=(u1 · C1,1 + · · ·+ um · Cm,1 . . . u1 · C1,n + · · ·+ um · Cm,n

)Das heißt, in der j-ten Spalte des Zeilenvektors steht der Eintrag∑n

i=1 ui · Ci ,j .

69 / 1

Modellierung

Petri-Netze



Merkregel:

Die Multiplikation einer m×n-Matrix mit einer n×1-Matrix(Spaltenvektor der Dimension n) ergibt eine m×1-Matrix(Spaltenvektor der Dimension m).

Die Multiplikation einer einer 1×m-Matrix (Zeilenvektor derDimension m) mit einer m×n-Matrix ergibt eine 1×n-Matrix(Zeilenvektor der Dimension n).

70 / 1

Modellierung

Petri-Netze



Wir betrachten nun die Inzidenzmatrix (oder einfach Matrix) einesPetrinetzes.

Sei S = {s1, . . . , sm} die Stellenmenge, T = {t1, . . . , tn} dieTransitionsmenge des Petrinetzes N.Die Inzidenzmatrix C von N ist eine m × n-Matrix mit Eintragender Form:

Ci ,j = tj•(si )− •tj(si ) ∈ Z

Dabei handelt es sich um die herkommliche Subtraktion (nicht diemodifizierte) und das Ergebnis liegt in den ganzen Zahlen.

Der Eintrag Ci ,j gibt an, wie sich die Anzahl der Marken in Stellesi andert, wenn die Transition tj geschaltet wird.

71 / 1

Modellierung

Petri-Netze



Beispiel fur eine Matrix:

s1 s2

t1

2

t3

s3

t2

Berechnung der Matrix-Eintrage:

t1 t2 t3s1 C1,1 = 0− 1 C1,2 = 1− 0 C1,3 = 0− 0s2 C2,1 = 0− 1 C2,2 = 0− 0 C2,3 = 1− 0s3 C3,1 = 2− 0 C3,2 = 0− 1 C3,3 = 0− 1

Resultierende Matrix:

C =

−1 1 0−1 0 12 −1 −1

72 / 1

Modellierung

Petri-Netze



s2

s1

s3

t1 s2

s1

s3

t1

Die beiden Netze sind verschieden, haben aber dieselbeInzidenzmatrix:

C =

−101

Dieses Phanomen kann nicht auftreten, wenn wir nur schlingenfreieNetze betrachten.

73 / 1

Modellierung

Petri-Netze



Angenommen, es gibt eine Schaltfolge, bei der die Transition tjuj -mal geschaltet wird (uj ∈ N0). Wie kann man die dadurchverursachte Anderung der Markierung mit Hilfe der Inzidenzmatrixbestimmen?

Man multipliziert die Spalte j , die fur die Transition tj steht,mit uj .Damit erhalt man den Effekt des uj -maligen Schaltens von tjfur jede einzelne Stelle.

Man addiert alle Werte der Zeile i , die fur die Stelle si steht,auf.Damit erhalt man den Effekt des Schaltens aller Transitionenfur eine einzelne Stelle.

Multiplikation der Matrix mit einem Vektor!74 / 1

Modellierung

Petri-Netze



Sei

~u =

u1...un

der sogeannte Schaltvektor, der angibt, wie oft jede Transitiongeschalten werden soll.

Schaltvektor fur das Beispielnetz: t1 und t2 werden zweimalgeschaltet, t3 einmal (dieser Schaltvektor ist von derAnfangsmarkierung aus realisierbar, z.B. durch die Schaltfolget1t2t3t1t2).

~u =

221

C · ~u =

2 · (−1) + 2 · 1 + 1 · 02 · (−1) + 2 · 0 + 1 · 1

2 · 2 + 2 · (−1) + 1 · (−1)

=

0−11

75 / 1

Modellierung

Petri-Netze



D.h., die Schaltfolge hat den Effekt, die Anzahl der Marken inStelle s1 gleichzulassen, in s2 um eins zu verringern und in s3 umeins zu erhohen.

Wenn wir diese Anderung zu dem Spaltenvektor addieren, der derAnfangsmarkierung entspricht, ergibt sich:

~m0 + C · ~u =

120

+

0−11

=

111

76 / 1

Modellierung

Petri-Netze



Markierungsgleichung

Fur jede erreichbare Markierung m gibt es einen Schaltvektor ~u mit

~m = ~m0 + C · ~u

Das heißt, jede erreichbare Markierung kann in obiger Formdargestellt werden.

Aber: nicht jede Markierung, die so dargestellt werden kann, istauch erreichbar.

77 / 1

Modellierung

Petri-Netze



s2

s1

s3

t1

C =

−101

1

00

+

−101

· (1) =

001

Diese Markierung ist jedochnicht erreichbar, da t1 nichtaktiviert ist.

78 / 1

Modellierung

Petri-Netze



t1

s1

s3

s2

t2

C =

−1 0−1 11 −1

1

00

+

−1 0−1 11 −1

·(11

)=

000

Diese Markierung ist jedochnicht erreichbar, da dieSchaltfolgen t1t2 und t2t1beide nicht moglich sind.

79 / 1

Modellierung

Petri-Netze



Die Markierungsgleichung kann also nicht dazu genutzt werden,um zu zeigen, dass eine bestimmte Markierung erreichbar ist.

Aber: man kann damit manchmal zeigen, dass eine Markierungnicht erreichbar ist.

Beispiel: Ist in folgendem Netz die Markierung m = (2, 2, 0)erreichbar?

s1 s2

t1

2

t3

s3

t2

Wir uberprufen, ob die Gleichung220

=

120

+

−1 1 0−1 0 12 −1 −1

·u1u2u3

eine Losung in den naturlichenZahlen hat.

80 / 1

Modellierung

Petri-Netze



Losen eines Gleichungssystems

Hier sieht man leicht durch Addition aller Gleichungen, dass dasGleichungssystem keine Losung hat.

2 = 1 −u1 +u22 = 2 −u1 +u30 = 2u1 −u2 −u34 = 3 Widerspruch!

Das heißt, die Markierung m = (2, 2, 0) ist nicht erreichbar.

81 / 1

Modellierung

Petri-Netze



Achtung: Als Losungen des Gleichungssystem interessieren uns hierLosungen in den in den naturlichen Zahlen.

Daher ist das zum Losen von Gleichungssystemen ublicherweiseverwendete Gaußsche Eliminationsverfahren nur begrenzteinsetzbar. In manchen Fallen muss es noch durch andereTechniken (z.B. Losungsverfahren fur diophantische Gleichungen)erweitert werden.

In unserem Fall werden wir die Beispiele jedoch immer so wahlen,dass die entstehenden Gleichungssysteme einfach zu losen sind.

82 / 1

Modellierung

Petri-Netze



Aufgabe: Stelle die Markierungsgleichung fur folgendes(unbeschrankte) Netz auf.

s1

2

t1

t2

s3s2

Kann man mit Hilfe der Markierungsgleichung uberprufen,dass die Markierung (1, 20, 0) nicht erreichbar ist?Kann das gleiche Ergebnis auch mit demUberdeckbarkeitsgraph erzielt werden?

83 / 1

Modellierung

Petri-Netze



Wir kommen nun zu einer weiteren Verwendung vonInzidenzmatrizen: sogenannte T- und S-Invarianten.

T-Invariante

Gegeben sei ein Netz N und seine m×n-Inzidenzmatrix C . EinSpaltenvektor ~u der Dimension n heißt T-Invariante, falls

C · ~u = ~0

Dabei ist ~0 ein Spaltenvektor, der nur Eintrage der Form 0 hat.

Bedeutung: eine T-Invariante beschreibt mogliche Schaltfolgen, dieeine Markierung unverandert lassen. Im Erreichbarkeitsgraph ergibtsich dann ein Kreis.

84 / 1

Modellierung

Petri-Netze



Bemerkung zu T-Invarianten:

Wie bei der Markierungsgleichung mussen solche Schaltfolgennicht notwendigerweise realisierbar sein.

Wenn es einen Kreis im Erreichbarkeitsgraphen gibt, soentspricht dieser aber auf jeden Fall einer T-Invariante.

Wie bei der Markierungsgleichung interessieren uns hier nurT -Invarianten mit Eintragen aus N0.

85 / 1

Modellierung

Petri-Netze



Aufgabe: Bestimme die T-Invarianten des folgenden Netzes:

s1 s2

t1

2

t3

s3

t2

Welche Bedeutung haben die T-Invarianten fur denErreichbarkeitsgraph?

Erreichbarkeitsgraph

86 / 1

Modellierung

Petri-Netze



S-Invariante

Gegeben sei ein Netz N und seine m×n-Inzidenzmatrix C . EinZeilenvektor v der Dimension m heißt S-Invariante, falls

v · C =(0 . . . 0

)

87 / 1

Modellierung

Petri-Netze



Bedeutung: sei ~m eine erreichbare Markierung. Dann gilt nach derMarkierungsgleichung, dass es einen Schaltvektor ~u gibt mit:

~m = ~m0 + C · ~u

Wenn man die Gleichung auf beiden Seiten von links mit vmultipliziert, so erhalt man:

v · ~m = v · ~m0 + v · C · ~u = v · ~m0 + 0 = v · ~m0

Also gilt v · ~m = v · ~m0 fur jede S-Invariante v und fur jedeerreichbare Markierung m.

Eine Markierung, die diese Gleichung nicht erfullt, kann dahernicht erreichbar sein!

88 / 1

Modellierung

Petri-Netze



Aufgabe: Bestimme die S-Invarianten des folgenden Netzes:

s1 s2

t1

2

t3

s3

t2

Kann man mit Hilfe der S-Invarianten uberprufen, ob dieMarkierung (2, 2, 0) erreichbar ist?

89 / 1

Modellierung

Petri-Netze



Lose die Gleichung(v1 v2 v3

)·

−1 1 0−1 0 12 −1 −1

=(0 0 0

).

Es ergibt sich folgendes Gleichungssystem:

−v1 −v2 +2v3 = 0v1 −v3 = 0

v2 −v3 = 0

Durch Vereinfachung erhalten wir v1 = v2 = v3, d.h., die Losungensind genau die Zeilenvektoren, bei denen alle Eintrage gleich sind.Sie sind also alle von der Form

v =(v1 v1 v1

)= v1 ·

(1 1 1

)All diese Vektoren ergeben aquivalente S-Invarianten, wirbetrachten daher nur die S-Invariante v =

(1 1 1

).

90 / 1

Modellierung

Petri-Netze



Fur eine allgemeine Markierung m = (m1,m2,m3) desBeispielnetzes gilt also:

v · ~m = m1 + m2 + m3 = 3 = v · ~m0

Die Gleichung besagt, dass die Summe der Marken in den dreiStellen konstant bzw. invariant ist und immer drei betragt.

Im allgemeinen haben Invarianten die Form

v1 ·m1 + · · ·+ vm ·mm = k ,

wobei v1, . . . , vm, k ∈ Z Konstanten sind.

91 / 1

Modellierung

Petri-Netze



Fur die spezielle Markierung m = (2, 2, 0) ergibt sich:

2 + 2 + 0 = 4 6= 3

D.h., diese Markierung ist in dem Netz auf jeden Fall nichterreichbar (ausgehend von der Anfangsmarkierung).

92 / 1

Modellierung

Petri-Netze



Bemerkungen:

Bei der Losung des Gleichungssystems zur Berechnung vonS-Invarianten sind prinzipiell auch Losungen außerhalb dernaturlichen Zahlen (negative Zahlen, Bruche, etc.) interessant.

Da es sich jedoch um ein homogenes Gleichungssystemhandelt (auf der rechten Seite steht der Nullvektor), kannman durch Multiplikation mit dem Hauptnenner (kleinstesgemeinsames Vielfaches der Nenner) zumindest immer eineDarstellung aller Losungen als Vielfaches von ganzzahligenVektoren erhalten.

Es gibt im allgemeinen unendlich viele S-Invarianten:insbesondere sind alle Vielfache einer S-Invariante wiederS-Invariante. Diese Vielfachen liefern jedoch keine zusatzlichenInformationen uber das Netz.

93 / 1

Modellierung

Petri-Netze




s2

t1

3

2

s1

Kann man mit Hilfe der S-Invarianten uberprufen, ob dieMarkierung (0, 5) erreichbar ist?

94 / 1

Modellierung

Petri-Netze



Lose die Gleichung(v1 v2

)·(−23

)=(0).

Es ergibt sich folgendes Gleichungssystem:

−2v1 +3v2 = 0

Durch Vereinfachung erhalten wir v1 = 32 · v2.

D.h., die Losungen sind von der Form v = v2 ·(32 1

)Wenn man nur Losungen in den ganzen Zahlen betrachten will, somultipliziert man mit dem Hauptnenner 2 und erhalt:

v = ` ·(3 2

), fur ` ∈ Z.

Im Folgenden betrachten wir nur die S-Invariante, die man erhalt,wenn man ` = 1 setzt.

95 / 1

Modellierung

Petri-Netze



Fur eine erreichbare Markierung m = (m1,m2) des Beispielnetzesgilt also:

v · ~m = 3 ·m1 + 2 ·m2 = 12 = v · ~m0

Fur die spezielle Markierung m = (0, 5) erhalten wir:

v · ~m = 3 · 0 + 2 · 5 = 10 6= 12

und damit ist diese Markierung nicht erreichbar.

96 / 1

Modellierung

Petri-Netze




s4

t4

s3

t1

s1

t2 t3

s2

s5

Kann man mit Hilfe der S-Invarianten uberprufen, ob dieMarkierung (0, 0, 1, 1, 1) erreichbar ist?

97 / 1

Modellierung

Petri-Netze



Aufgabe: Mit Hilfe des folgenden Beispiels soll gezeigt werden,dass Invarianten auch fur unbeschrankte Netze sehr nutzlich seinkonnen. Bestimmen Sie dazu die S-Invarianten des folgendenNetzes:

s1

s3

t1

s2

2

98 / 1

Modellierung

Petri-Netze



Aufgabe: Wir hatten mit Hilfe der Markierungsgleichung gezeigt,dass die Markierung (1, 20, 0) in folgendem Netz nicht erreichbarist.

s1

2

t1

t2

s3s2

Kann man das gleiche Ergebnis auch mit Hilfe von S-Invariantenerzielen?

99 / 1

Modellierung

Petri-Netze



Bemerkungen:

Fur beschrankte Netze sind folgende Techniken zum Testen derNicht-Erreichbarkeit geeignet. Sie werden der Reihe nachaufwandiger und exakter:

1 S-Invarianten

2 Markierungsgleichung

3 Erreichbarkeitsgraph(exakt, kann auch zur Uberprufung der Erreichbarkeitverwendet werden).

100 / 1

Modellierung

Petri-Netze



Bemerkungen:

Auch fur unbeschrankte Netze ist die Markierungsgleichungaufwandiger und exakter als S-Invarianten.

Der Uberdeckbarkeitsgraph ist jedoch, im Gegensatz zumErreichbarkeitsgraph, keine exakte Technik und erlaubt nurbegrenzt Aussagen uber die Erreichbarkeit von Markierungen.

101 / 1

Modellierung

Petri-Netze



Fur unbeschrankte Petrinetze haben wir also bisher nurapproximative, unvollstandige Methoden fur dasErreichbarkeitsproblem. Es gilt jedoch:

Entscheidbarkeit des Erreichbarkeitsproblems

Es gibt ein Verfahren, das fur ein gegebenes (unbeschranktes) NetzN und eine Markierung m entscheidet, ob m in N erreichbar ist.(Mayr, 1984)

102 / 1

Modellierung

Petri-Netze



Dieses Verfahren ist jedoch extrem aufwandig und in derPraxis derzeit nicht einsetzbar.

Die obige Aussage bedeutet jedoch auch, dass Petrinetzenicht zu den machtigsten Berechnungsmodellen gehoren. Esgibt namlich Berechnungsmodelle, fur die dasErreichbarkeitsproblem nicht entscheidbar ist.

Anders ausgedruckt: Petrinetze sind nicht Turing-machtig ( Vorlesung “Berechenbarkeit und Komplexitat”).

Das liegt vor allem daran, dass Petrinetze keine Nulltestsfolgender Form erlauben: “Die Transition t kann nur feuern,wenn in der Stelle s keine Marken liegen.”

103 / 1

Modellierung

Petri-Netze


Petrinetze: Fallstudien (Wechselseitiger Ausschluss)

Wir betrachten nun noch einige großere Fallstudien . . .

Zunachst behandeln wir das Konzept des wechselseitigenAusschlusses (engl. mutual exclusion oder mutex).

Wir betrachten zwei Akteure, die jeweils einen kritischenBereich haben.

Beide Akteure durfen nicht gleichzeitig in ihren kritischenBereich kommen, da sie sich dort gegenseitig behindern undunerwunschtes Verhalten auslosen wurden (z.B. indem beideAkteure in dieselbe Datei schreiben).

Es darf sich also immer hochstens ein Akteur im kritischenBereich befinden.

104 / 1

Modellierung

Petri-Netze



Ursprungliches System:

K1NK 1

nk1

k1

kritischer Bereich

NK 2K2

nk2

k2

Bedeutung der Stellen: K1 (krit. Bereich Akteur 1), NK 1

(nicht-krit. Bereich Akteur 1), K2 (krit. Bereich Akteur 2), NK 2

(nicht-krit. Bereich Akteur 2)

105 / 1

Modellierung

Petri-Netze



Erweitertes System mit Mechanismen zum wechselseitigen Aus-schluss:

K1NK 1

nk1

k1

NK 2K2

k2

nk2

S

Bedeutung der Stellen: K1 (krit. Bereich Akteur 1), NK 1

(nicht-krit. Bereich Akteur 1), K2 (krit. Bereich Akteur 2), NK 2

(nicht-krit. Bereich Akteur 2), S (Hilfsstelle, sog. Semaphor)

105 / 1

Modellierung

Petri-Netze



Wir mochten zeigen, dass in den Stellen K1, K2 niemalsgleichzeitig Marken liegen.

Reihenfolge der Stellen: K1, NK 1, K2, NK 2, S

Reihenfolge der Transitionen: k1, nk1, k2, nk2

Inzidenzmatrix:

C =

1 −1 0 0−1 1 0 00 0 1 −10 0 −1 1−1 1 −1 1

106 / 1

Modellierung

Petri-Netze



Wir bestimmen die S-Invarianten, nach der Gleichung

v · C =(0 . . . 0

)Entstehendes Gleichungssystem:

v1 −v2 −v5 = 0−v1 +v2 +v5 = 0

v3 −v4 −v5 = 0−v3 +v4 +v5 = 0

107 / 1

Modellierung

Petri-Netze



Vereinfacht ergibt sich:

v1 = v2 + v5v3 = v4 + v5

Das heißt, die Losungen haben genau die Form:(v2+v5 v2 v4+v5 v4 v5

)= v2 ·

(1 1 0 0 0

)+ v4 ·

(0 0 1 1 0

)+ v5 ·

(1 0 1 0 1

)fur v2, v4, v5 ∈ Z. Die drei Vektoren bilden eine Basis desLosungsraums.

108 / 1

Modellierung

Petri-Netze



Fur uns ist vor allem der letzte Vektor interessant. Fur jedeerreichbare Markierung m = (m1,m2,m3,m4,m5) muss gelten:

m1 + m3 + m5 = v · ~m = v · ~m0 = 1

Angenommen, in der Stelle K1 liegt mindestens eine Marke(m1 ≥ 1) und in der Stelle K2 liegt mindestens eine Marke(m3 ≥ 1).

Dann gilt:2 ≤ m1 + m3 + m5 = 1,

was ein Widerspruch ist.

Also liegt in den Stellen K1, K2 zusammen immer hochstens eineMarke.

109 / 1

Modellierung

Petri-Netze


Petrinetze: Fallstudien (Speisende Philosophen)

Wir kommen nochmal auf die speisenden Philosophen zuruck:

Diesmal sitzen nur zwei Philosophen an einem Tisch (damitdas Beispiel nicht zu groß wird).

Einer davon ist ein Linkshander (und nimmt die linke Gabelzuerst), der andere ein Rechtshander (und nimmt die rechteGabel zuerst).

110 / 1

Modellierung

Petri-Netze



Petrinetz: links- und rechtshandige Philosophen

w1

e1

h1

F1 F2

E2

W1 E1

W2

H2

H1

h2w2

e2

Reihenfolge derStellen:F1,F2,H1,H2,W1,W2,E1,E2

Reihenfolge derTransitionen:w1, e1, h1,w2, e2, h2

111 / 1

Modellierung

Petri-Netze



Zu zeigen: in diesem Netz gibt es keine Verklemmung, bei derbeide Philosophen im Wartezustand sind.D.h., folgende Markierung soll nicht erreichbar sein:

m = (0, 0, 0, 0, 1, 1, 0, 0)

Dazu betrachten wir die Inzidenzmatrix des Netzes:

C =

−1 0 1 −1 0 10 −1 1 0 −1 1−1 0 1 0 0 00 0 0 −1 0 11 −1 0 0 0 00 0 0 1 −1 00 1 −1 0 0 00 0 0 0 1 −1

112 / 1

Modellierung

Petri-Netze



Eine S-Invariante ist

v =(1 0 0 0 1 1 1 1

)Und es gilt:

v · ~m0 = 1 v · ~m = 2

Daraus folgt v · ~m0 6= v · ~m. Damit ist m nicht erreichbar und eskann daher kein Deadlock dieser Form geben.

113 / 1

Modellierung

Petri-Netze


Fallstudie: Leser-Schreiber-Problem

Beliebig viele Prozessedurfen gleichzeitig lesen

Wenn geschrieben wird,darf nur ein Schreiberund keine Leser imkritischen Abschnitt sein

Die Schreiber’verhungern’, solangenoch jemand lesen will

114 / 1

Modellierung

Petri-Netze


Fallstudie: Leser-Schreiber-Problem(2)

Bessere Losung:Sobald jemandschreiben will, mussenalle Leser warten

115 / 1

Modellierung

Petri-Netze


Petrinetze: Weitere Arten von Netzen

Wir betrachten zuletzt noch zwei weitere Arten von Netzen:

Netze mit Kapazitaten

Attributierte Netzeauch bekannt unter den Namen: Netze mit individuellenMarken, Pradikat-Transitions-Netze, engl. coloured Petri nets

116 / 1

Modellierung

Petri-Netze



Netze mit Kapazitaten

Ein Petrinetz mit Kapazitaten besteht aus einem (herkommlichen)Petrinetz N (mit Stellenmenge S) und einer Kapazitatsfunktionk : S → N0. Fur die Anfangsmarkierung m0 muss gelten: m0 ≤ k .

Intuition: die Stelle s darf hochstens k(s) Marken enthalten.Kapazitaten werden neben die Stellen geschrieben.

Schalten von Transitionen bei Kapazitaten

Eine Transition t kann unter einer Markierung m schalten, wenngilt:

1 •t ≤ m

2 und m •t ⊕ t• ≤ k .

D.h., eine Transition darf nur dann schalten, wenn dadurch dieKapazitaten nicht uberschritten werden.

117 / 1

Modellierung

Petri-Netze



Beispielnetz mit Kapazitaten

s2s1

2 1

t1

t2

t3


// (1, 1)t3 //

t2��

(1, 0)

t1��

(2, 0)

t1

DD

(0, 1)

t2

DD

t3 // (0, 0)

Insbesondere: unter der Anfangsmarkierung (1, 1) ist die Transitiont1 nicht schaltbar.

118 / 1

Modellierung

Petri-Netze



Umwandlung eines Netzes mit Kapazitaten in ein Netz ohneKapazitaten

1 Fuge zu jeder Stelle s eine sogenannte Komplementstelle shinzu. In der Anfangsmarkierung enthalt s genauk(s)−m0(s) Marken.Idee: die Summe der Marken in der Stelle und derKomplementstelle ergibt immer die Kapazitat.

2 Falls eine Transition in der Summe Marken aus einer Stelleherausnimmt (n = t•(s)− •t(s) < 0) fuge eine Kante von tnach s mit Gewicht −n ein.

3 Falls eine Transition in der Summe Marken in eine Stellehineinlegt (n = t•(s)− •t(s) > 0) fuge eine Kante von s nacht mit Gewicht n ein.

119 / 1

Modellierung

Petri-Netze



Mit dieser Konstruktion ist fur jedes Paar s, s von Stellensichergestellt, dass

m(s) + m(s) = k(s) fur jede erreichbare Markierung s;

eine Transition t nur schaltbar ist, wenn die Kapazitat derStellen in der Nachbedingung noch nicht ausgeschopft ist.Das wird dadurch uberprufen, dass die benotigte Kapazitatuber die Komplementstellen abgefragt wird.

120 / 1

Modellierung

Petri-Netze



Umgewandeltes Beispielnetz

s1 s2

s2s1t1

t2

t3

Reihenfolge der Stellen: s1, s1, s2, s2


// (1, 1, 1, 0)t3 //

t2��

(1, 1, 0, 1)

t1��

(2, 0, 0, 1)

t1

DD

(0, 2, 1, 0)

t2

DD

t3 // (0, 2, 0, 1)121 / 1

Modellierung

Petri-Netze


Fallstudie: Erzeuger-Verbraucher-Problem

Ein Prozess erzeugt Objekte, der andere verbraucht diese

Es steht nur eine begrenzte Anzahl Speicherplatze zurVerfugung

122 / 1

Modellierung

Petri-Netze


Fallstudie: Erzeuger-Verbraucher-Problem (2)

Ein Prozess erzeugt Objekte, der andere verbraucht diese

Es steht nur eine begrenzte Anzahl Speicherplatze zurVerfugung

Das Schreiben/Lesen der Objekte muss im kritischenAbschnitt erfolgen

123 / 1

Modellierung

Petri-Netze



Obige Losung ignoriert, dass bei der Programmierung dieBedingungen (kritischer Abschnitt, freie Platze/Objektevorhanden) nacheinander uberpruft werden mussenVariante 1: Erst kritischer AbschnittEs kommt zum Deadlock, wenn die zweite Bedingung nichterfullt ist

124 / 1

Modellierung

Petri-Netze



Korrekte Losung: Erst die Anzahl uberprufen, danach in denkritischen Abschnitt

125 / 1

Modellierung

Petri-Netze



Bei attributierten Netzen (oder coloured nets) haben die MarkenFarben. Die Transitionen geben an, Marken welcher Farbeentnommen und erzeugt werden sollen.

Beispielsweise entnimmt folgende Transition eine blaue und einerote Marke und erzeugt zwei grune Marken.

2×

126 / 1

Modellierung

Petri-Netze



Farben konnen dabei auch Elemente eines bestimmten Datentypssein (z.B. Zahlen). Die Transitionen werden dabei symbolischannotiert und an den Transitionen konnen auch Bedingungenstehen.

Beispielsweise hat folgendes Netz naturliche Zahlen als “Farben”.Die Transition entnimmt der ersten Stelle eine naturliche Zahl xund der zweiten Stelle eine Zahl y . In die Stelle der Nachbedingungwird dann die Zahl x + y gelegt. Die Transition darf nur schalten,wenn x > 3.

27

45

x + yx

yx > 3

127 / 1

Documents

Modellierung Wintersemester 2014/15 Petri-Netze (Folien ... · Modellierung Petri-Netze Grundlagen und Erreichbarkeitsgraphen Motivation: Petrinetze Petrinetzesind ein Formalismus