Transcription

PetrinetzePetrinetzeLiteratur:– B. Baumgarten, Petri Netze, Akademischer Verlag, 1996– W. Reisig, Systementwurf mit Netzen, Springer-Verlag, 1985– J. L. Peterson, Petri Net Theory and the Modeling of Systems,Prentice Hall, 1981!#" # %& # %'( "% )*PetrinetzeIdee von Petrinetzen Modellierung eines Systems als– Nebenläufige Prozesse– Bedingungen und Abhängigkeiten dieser nebenläufigen Prozesse(Synchronisationsbedingungen) Simulation und Analyse des daraus resultierenden Verhaltens– mit Konflikten und Nichtdeterminismus– daraus resultierenden unterschiedlichen Verhaltensmustern(Erreichbarkeit)– Lebendigkeit– Sicherheit– .!#" # %& # %'( "% )*

PetrinetzeDining Philosophers Problem!#" # %& # %'( "% )*,PetrinetzeDining Philosophers Problem!#" # %& # %'( "% )*-

PetrinetzeKonzept der Modellierung mit Petrinetzen passive Komponenten (Plätze, Stellen, Bedingungen, Kanäle, .)– modellieren Betriebsmittel, Bedingungen, Queues, Speicher,Behälter, Variablen etc. des realen Systems (alles was einenZustand annehmen kann) Markierungen der passiven Komponenten modellieren aktuellenZustand der passiven Komponenten aktive Komponenten (Transitionen, Ereignisse, Prozesse, .)– modellieren Aktivitäten, die Marken durch das System fließen lassenund so die Zustände, Bedingungen etc. verändern Kanten zwischen passiven und aktiven Komponenten– modellieren Zusammenhänge von passiven und aktivenKomponenten– stellen Fluss der Marken dar!#" # %& # %'( "% ).*PetrinetzeBeispiel eines ehmenVerbraucherverbrauchsbereit passive Komponenten durch Kreis aktive Komponenten durch Rechteck (oder Strich) Marken durch Punkt Fluss der Marken über Kanten Aktivierungsbedingungen für aktive Komponenten durch passiveKomponenten bei eingehenden (und ausgehenden) Kanten" # %& # %'( "% VerbraucherentnahmebereitKanalfrei/

PetrinetzeMathematische DefinitionEin Petrinetz N ist ein TupelN (P, T, Pre, Post)mitP {p1, p2, p3, .}ist eine Menge von PlätzenT {t1, t2, t3, .}ist eine Menge von TransitionenPre P Tist die Menge der gerichteten Kanten von Plätzen zuTransitionenPost T Pist die Menge der gerichteten Kanten von Transitionen zuPlätzenDes weiteren seien definiert Markierungen M als AbbildungenM: P Νbzw.M: P {0, 1}durch die den Plätzen eine natürliche Zahl für die Anzahl der Marken zugeordnet wirdEin PetrinetzN (P, T, Pre, Post, M0)mit der Anfangsmarkierung M0 wir als initiales Petrinetz bezeichnet!#" # %& # %'( "% )0*PetrinetzeBeispiel Mathematische Definitions1t1s3s2t2N (P, T, Pre, Post, M0)mitP {s1, s2, s3}T {t1, t2}Pre {(s1, t1), (s1, t2), (s2, t2)}Post {(t2, s3), (t1, s3)}M0 : P ΝmitM0(s1) 1, M0(s2) 1, M0(s3) 0!#" # %& # %'( "% )*1

PetrinetzeMathematische Definition (2)Folgende Mengen sind für Transitionen t definiert:In(t) ist die Menge aller Eingangsplätze der Transition tIn(t) {p (p, t) Pre}Out(t) ist die Menge aller Ausgangsplätze der Transition tOut(t) {p (t, p) Post}Analog sind folgende Mengen für Plätze p definiert:In(p) ist die Menge aller Eingangstransitionen des Platzes pIn(p) {t (t, p) Post}Out(p) ist die Menge aller Ausgangstransitionen des Platzes pOut(p) {t (p, t) Pre}!#" # %& # %'( "% )2*PetrinetzeRegeln für den Markenfluss (einfachster Fall)Schaltbarkeit von Transitionen:– Eine Transition ist schaltbar bei einer bestimmten Markierung M, wenn alleseine Eingangsplätze eine Markierung haben p In(t) : M(p) 0Schalten von Transitionen:– Beim Schalten einer Transition t wird jeweils eine Marke von denEingangsplätzen entnommen und jeweils eine Marke auf denAusgangsplätzen der Transition abgelegt.– Dadurch wird ausgehend von einer Markierung M, bei der Transition tschaltbar ist, eine neue Markierung M' wie folgt erzeugt p P : M'(p) M(p) - 1 wenn p In(t) p Out(t)M(p) 1 wenn p Out(t) p In(t)!#" # %& # %'( "% )*M(p)sonst3

PetrinetzeKonflikte Transitionen t1 und t2 stehen in Konflikt zueinander, wenn beideschaltbar sind und durch das Schalten der einen Transition dieandere nicht mehr schaltbar ist.t1t2 !#Ein Konflikt stellt einen Nicht-Determinismus im Modell dar, durch densich unterschiedliches Verhalten ergibt." # %& # %'( "% )*PetrinetzeKapazität von Plätzen und Gewicht von KantenKapazität von Plätzen– Plätze können durch Kapazitäten beschränkt sein, die die maximale Anzahlder Marken begrenzt, d.h.K: P Νist eine Abbildung, welche für jeden Platz p die maximale Anzahl derMarken bestimmtKantengewicht– Kantengewichte können verwendet werden, um die Anzahl der beimSchalten einer Transition fließenden Marken zu bestimmen; d.hW: Pre Post Νist eine Abbildung, welcher für jede Kante das Gewicht bestimmt.313!#" # %& # %'( "% )*

PetrinetzeErweiterte SchaltregelUnter Berücksichtigung von Kapazität von Plätzen und Gewicht vonKanten ergibt sich folgende erweiterte SchaltregelSchaltbarkeit von Transitionen:– Eine Transition t ist schaltbar (oder aktiviert) bei einer bestimmten Markierung M,wenn alle seine Eingangsplätze p mindestens so viele Marken haben wie dasGewicht der Kante (p, t) p In(t) : M(p) W(p, t)und alle Ausgangsplätze q soviel freie Kapazität wie das Gewicht der Kante (t, q) q Out(t) : K(q) - M(q) W(t, q)Schalten von Transitionen:– Das Schalten einer Transition t bewirkt einen Markenfluss entsprechend denKantengewichten der eingehenden und ausgehenden Kanten von t p P : M'(p) !#M(p) - W(p, t)wenn p In(t) p Out(t)M(p) W(t, p)wenn p Out(t) p In(t)M(p) - W(p, t) W(t, p)wenn p In(t) p Out(t)M(p)sonst" # %& # %'( "% )*,PetrinetzeErweiterte Schaltregel: Abbildung!#" # %& # %'( "% )*-

PetrinetzeErreichbarkeitsgraph und Erreichbarkeitsmenge Basis der Analyse von Petrinetzen ist der Erreichbarkeitsgraph Der Erreichbarkeitsgraph gibt ausgehend von einer AnfangsmarkierungM0 die Folge der erreichbaren Markierungen an Dadurch kann bestimmt werden, welche prinzipiellen Markierungen dasPetrinetz erreichen kann Die Menge der durch den Erreichbarkeitsgraph erzeugten Markierungenheißt die ErreichbarkeitsmengeBeispiel: Petrinetz und sein 13014.p1!#" # %& # %'( "% ).*PetrinetzeErreichbarkeitsgraphE2V1FANEVBE1!#" # %& # %'( "% )*V2/

PetrinetzeBeispiel K1K1VNNAEANEVVK2K2E2V2E2V2E1V1K1ANEVK2!#E2" # %& # %'( "% )V20*PetrinetzeBeispiel Erreichbarkeitsgraph (Fortsetzung)10 10 10NA10 01 01EV01 01 1010 10 01V01 10 10N!#" # %& # %'( "% )*EA01 01 011

PetrinetzeVerklemmung, Lebendigkeit und SicherheitDer Erreichbarkeitsgraph erlaubt die Bestimmung wichtigerEigenschaften von Petrinetzen:– Unter einer Verklemmung eines Petrinetzes N verstehen wir eineMarkierung V, bei der es keine Transition aus T gibt, die bei Vschaltbar ist– Ein Petrinetz N ist lebendig, wenn die Erreichbarkeitsmenge keineMarkierung enthält, die eine Verklemmung ist.– Ein Petrinetz heißt sicher bezüglich einer vorgegebenenMarkenanzahl B, wenn die Erreichbarkeitsmenge keineMarkierung enthält, bei der einem Platz mehr als B Markenzugewiesen sind.– Ein Petrinetz wird sicher schlechthin bezeichnet, wenn es sicherbezüglich der Markenanzahl B 1 ist.!#" # %& # %'( "% )*2PetrinetzeTypen von Petrinetzen!# Bedingungs/Ereignis - Netze Stellen/Transitionen - Netze Netze mit individuellen Marken Zeitbehaftete Netze Stochastische Netze" # %& # %'( "% )* 3

PetrinetzeBedingungs/Ereignis-Netze Plätze modellieren boolesche Bedingungen– eine Marke auf einer Bedingung bedeutet, dass die Bedingung wahr ist– alle Plätze haben die Kapazität 1 !#Transitionen modellieren Ereignisse" # %& # %'( "% ) *PetrinetzeStellen/Transitionen - Netze Braucht man Mengen von Marken bei Plätzen und unterschiedlicheKantengewichte für den Markenfluss, werden die sogenanntenStellen/Transitionen - Netze verwendet Modellierungskonzept der Stellen/Transitionen - Netze entspricht imwesentlichen dem allgemeinen Konzept von Petrinetzen wie obendargestellt.Beispiel BarberShop :barbersscissorsarrivalqueuestartwashingstart cuttingdryerstart dryingfinished10!#" # %& # %'( "% )*

PetrinetzeStellen/Transitionen - Netze: Beispiel Tankstelle!#" # %& # %'( "% )* ,PetrinetzeNetze mit individuellen Marken (Coloured Petri Nets) Wird die Anonymität der Marken aufgegeben, sondern arbeitetman mit unterschiedlichen Typen und individuellen Objekten,so kommt man zum mächtigen Modellierungskonzept derNetze mit individuellen Markenoder auchColoured Petri Nets Diese sind dann mit einem allgemeinen Programmierkonzepterweitert, mit welchem man den Fluss der Objekte von Platz zuPlatz durch die Transitionen programmieren kann.!#" # %& # %'( "% )* -

PetrinetzeBeispielmodell: Netz mit individuellen Marken1000100!#100" # %& # %'( "% ) .*PetrinetzeBeispielmodell: Stellen/Transitionen - benSchraubenschlüsselZusammenschrauben!#" # %& # %'( "% )*Schraubprodukt /

PetrinetzeZeitbehaftete Netze Eine weiteres mächtiges Modellierungskonzept ergibt sich aus denPetrinetzen, wenn man eine reelle (Simulations-)zeit verwendet:– Schalten der Transitionen dauert Zeit (Zeitverzögerung)– Bei Fluss von Marken (Objekten) werden diese zeitverzögert bei denAusgangsplätzen der Transitionen verfügbar sein Zeitbehaftete Petrinetze sind als Modellierungskonzept für die diskreteereignisorientierte Simulation gut einsetzbarAnmerkung: Alternativ kann auch für die Plätze eine Zeitverzögerungangegeben werden. Hier wird diese üblicherweise alsMindestverweildauer interpretiert.!#" # %& # %'( "% )* 0PetrinetzeNetz mit Zeitbedingungen Z.B. Netze mit Zeitbegriffen (für die Simulation besonders interessant) Zeit wird zugeordnet:– Stellen oder Transitionen– Stellen und Transitionen Zeitbedingungen werden formuliert:– Frühester Zeitpunkt– Mindestdauer– Spätester Zeitpunkt,– Höchstdauer– Exakter Zeitpunkt– Exakte Dauer etc.!#" # %& # %'( "% )* 1

PetrinetzeNetze mit Zeitbegriffen Zeiträume in Stellen werden als Mindestverweildauer interpretiert Zeiträume in Transitionen als Schaltdauer Erreichbarkeitsanalyse komplex Berechnung von Mindest- und Höchstzeiten Angabe deterministische oder auch Wahrscheinlichkeitsaussagen Zeitpunkte und Zeitintervalle in Netzen können auch mit ZufallsVerteilungsfunktionen versehen werden (stochastische Netze) – inkl.statistischer Analysen.τa 0τa die seit a verstrichene Zeitτa 10!#τa 10" # %& # %'( "% )* 2PetrinetzeStochastische Petrinetze Stochastische Petrinetze (SPN) gehen aus den Standard-Petri-netzenhervor, wobei jeder Transition eine exponentiell verteilte Schaltratezugewiesen wird. Ein stochastisches Petrinetz ist ein PetrinetzSPN (S, T, Pre, Post, M0, R)mit S, T, Pre, Post und M0 wie bereits eingeführt und R {r1,r2,.,rm}. !#R ist die Menge der Schaltraten, wobei ri den Mittelwert der zurTransition ti gehörenden, exponentiell verteilten Schaltrate darstellt." # %& # %'( "% )*,3

PetrinetzeStochastische Petrinetze Für die analytische Modellierung ist die Exponentialverteilung diewichtigste und auch die am leichtesten handhabbare Verteilung, da sieals einzige kontinuierliche Verteilung die Markov-Eigenschaft derGedächtnislosigkeit (memoryless property) besitzt. (entsprechendlassen sich viele Kennwerte wie bei der Warteschlangentheorieberechnen).!#" # %& # %'( "% enp1t1CPU1CPU3BUSm1·λSpeicherwarten aufden Busp2CPU2t2p3t3!#" # %& # %'( "% )*greifen aufden Speicherzuµp4Bussteht zurVerfügung,

PetrinetzeBeispiel Fortsetzung Gegenstand der Modellierung in diesem Beispiel ist der Zugriff dreierProzessoren auf einen gemeinsamen, globalen Speicherbereich übereinen gemeinsamen Bus. Die drei Marken in p1 repräsentieren die in ihrem lokalenSpeicherbereich arbeitenden Prozessoren. Nach einer zufälligen, exponentiell verteilten Zeit mit Mittelwert1/(m1*λ) schaltet die Transition t1 (markierungsabhängige Schaltrate)und eine Marke aus p1 befindet sich nun in p2 (einer der Prozessorenist im Begriff auf den gemeinsamen Speicherbereich zuzugreifen).!#" # %& # %'( "% )*,,PetrinetzeBeispiel Fortsetzung An Transition t2 wird geprüft, ob der gemeinsame Bus (reprä-sentiertdurch eine Marke in p4) zur Verfügung steht. Ist das der Fall, schaltet t2 und die Marken aus p2 und p4 verschwinden, während eine neue Marke in Platz p3 hinzugefügt wird. Nach einer zufälligen, exponentiell verteilten Zeit mit Mittelwert 1/µ(Modellierung der Speicherzugriffsdauer) schaltet die Transition t3und die Marke aus p3 verschwindet, während in p1 und p4 jeweilseine neue Marke hinzugefügt wird (Ende des Speicherzugriffs undBusfreigabe).!#" # %& # %'( "% )*,-

PetrinetzePetrinetze als Modellierungswerkzeug für diskrete Simulationsmodelle Zeitbehaftete Petrinetze mit individuellen Marken eignen sich gut alsallgemeines Modellierungskonzept in der diskreten ereignisorientiertenSimulation– nebenläufige Prozesse– Synchronisations- und Aktivierungsbedingungen– Zeitverzögerung– Workflowmodellierung Unterschiedliche diskrete Simulationssysteme basieren auf Petrinetze; sievereinen– Petrinetzdarstellung– Programmiersprache– diskrete Simulationskonzepte Modellierung– Ressourcenpools, Bedingungen, Speicher, Warteschlangen, etc. durch Plätze– Entitäten, Transaktionen, Ressourcen, boolesche Werte durchMarken(-objekte)– Aktivitäten durch Transitionen mit Zeitverzögerung!#" # %& # %'( "% )*,.PetrinetzeSimulationssystem ExSpect Zeitbehaftete Petrinetze mit individuellen Marken Funktionale Programmiersprache– Mengenoperationen– Anweisungen für den Markenfluss– Zeitverzögerung des Markenflusses Simulationssystem– Simulation– Animation– statistische Auswertung!#" # %& # %'( "% )*,/

PetrinetzeSimulationssystem ExSpect: ScreenShot!#" # %& # %'( "% )*,0PetrinetzeZusammenfassung Petrinetze sind gerichtete, bipartite Graphen mit Anfangsmarkierung,Kantengewichtung, Kapazität der Stellen Entsprechend der Struktur werden unterschieden: Zustandsmaschinen,Synchronisationsnetze, FreeChoiceNetze, etc. Eigenschaften wie Sicherheit und Lebendigkeit können bei den einfachenPetrinetzen durch die Analyse des Erreichbarkeitsgraphen gelöst werden. Es existieren unterschiedliche Erweiterungen der Petrinetze, z.B.Petrinetze mit individuellen Marken, Nicht-Standard Netze, z.B. Petrinetzemit Verbotskanten und Petrinetze mit Zeitbegriffen (Verzögerungen)– deterministisch– zufallsverteilt - stochastische Petrinetze können analytisch(Exponentialverteilung) oder simulativ ausgewertet werden (vgl.Warteschlangentheorie)!#" # %& # %'( "% )*,1

Petrinetze ˇ ˆ , ˇ ! " # %& # %'("% ) # * Erweiterte Schaltregel Unter Berücksichtigung von Kapazität von Plätzen und Gewicht von