close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

21 Wie kann man Nebenläufigkeit modellieren (Petri- Netze) ?

EinbettenHerunterladen
21 Wie kann man Nebenläufigkeit modellieren (PetriNetze) ?
Entwickelt wurden Petri-Netze von C. A. Petri21. Ihren Einsatz findet man in vielen Bereichen
der Datenverarbeitung, z.B. Modellierung von Kommunikationsprotokollen für verteilte Systeme
(Datenbanken, nebenläufige Programme), insbesondere auch im Requirements Engineering und
in der derzeit hochgelobten UML.
Allgemein: Sie sind geeignet für die Modellierung dynamischen Geschehens. Ein schönes Buch
ist das von W. Reisig "Systementwurf mit Netzen" bzw. "Petri-Netze".
Klassisches Beispiel: Erzeuger/Verbraucher-Problem
Abb. 39
Bedingungen/Ereignis-Netze (B/E-Netze) sind gegeben durch Bedingungen, als Kreise dargestellt, aus Ereignissen, als Rechtecke repräsentiert, sowie durch zwei Relationen, mit Pfeilen
modelliert, die zwischen Vorbedingungen und Ereignissen bzw. Ereignissen und Nachbedingungen verlaufen. Außerdem gibt es Marken (manchmal auch Tokens genannt), die sich in einigen
Bedingungen befinden, was dargestellt wird durch "C".
Eine Bedingung mit Marke heißt erfüllt, andernfalls unerfüllt. Ein Ereignis e in einem B/E-Netz
kann eintreten bzw. e kann schalten, wenn alle seine Vorbedingungen Ce erfüllt und alle Nachbedingungen eC unerfüllt sind.
Nach dem Eintritt eines Ereignisses sind die Vorbedingungen unerfüllt und die Nachbedingungen erfüllt. Beides zusammen ist die "Schaltregel eines B/E-Netzes".
21
"Kommunikation mit Automaten", Schriften des Instituts für Instrumentelle Mathematik, Bonn,
1962.
178
Beispiele:
Im folgenden Netz kann nur entweder a oder b einmal schalten:
Abb. 40
Das folgende Netz enthält eine (unzulässige) Kontaktsituation. (Solche lassen sich aber auflösen.)
Abb. 41
179
Das folgende Netz verklemmt sich rasch, weil nur Marken generiert aber nicht konsumiert
werden.
Abb. 42
Im ersten folgenden Netz ist eine Fairness garantiert, im zweiten nicht.
Abb. 43
Abb. 44
Ê
180
Der Bezug zu den bislang bekannten Automaten ist offensichtlich. Leider liegen die Sprachen,
die von Petrinetzen erkannt werden können, unschön “quer” in der Chomsky-Hierarchie. Je nach
Typ - im Folgenden werden einige noch vorgestellt - reichen sie vom Endlichen Automaten bis zur
Turing-Maschine. Also sind viele Eigenschaften von Petrinetzen entscheidbar, manche aber nicht.
Ein Petrinetz heißt lebendig, wenn es immer ein Ereignis gibt, das eintreten kann, d.h. es darf
insbesondere kein (erreichbares) Ereignis e geben, mit |eC| = 0. (Eine solche Forderung ist notwendig für persistente Systeme wie Betriebssysteme.)
Die Funktion M : B 6 {g, C}, die den Bedingungen eine Marke "C" zuordnet (oder auch keine;
"g" steht für unmarkiert), heißt Markierungsfunktion. M' ist die Markierung eines Petrinetzes,
nachdem bei einer Markierung M das PN geschaltet hat, also
M'e(b) = g
œ b 0 Ce
œ b 0 eC
M'e(b) = C
M'(b) = M(b) sonst
Ist M so, dass ein Petrinetz nicht mehr schalten kann, liegt eine Verklemmung (deadlock, deadly
embrace) vor.
Verklemmungen können leicht eintreten. Beispiel: Zwei Prozesse P1 und P2 brauchen die zwei
selben Betriebsmittel (z.B. zwei Dateien D1 und D2). Wird P1 die eine, z.B. D1, zugeordnet und
gleich danach P2 die Datei D2, kann keiner der Prozesse fertig werden, wenn sie “stur” an ihren
zugeteilten Betriebsmitteln festhalten.
In der Informatik wurden verschiedene Methoden zur Lösung des Verklemmungsproblems entwickelt, eine ist die Einführung von Semaphoren, die den wechselseitigen Ausschluss des Zugriffs
auf die gemeinsamen Betriebsmittel koordinieren können.
181
Beispiel: Philosophenproblem (E.W. Dijkstra)
Abb. 45
Die Philosophen (Prozesse) können sich in 3 Zuständen befinden: denkend, hungrig und essend.
Für das Essen benötigen sie zwei Gabeln, zu denen sie immer nur in fester Reihenfolge greifen,
wenn sie hungrig sind, z.B. zuerst nach der links liegenden, dann nach der rechten. Stellt man sich
die Philosophen als stur vor, warten sie auf die rechte, nachdem sie die linke Gabel ergreifen
konnten, sind aber nicht bereit, nach einer gewissen Zeit (time-out), in der sie keine rechte bekommen haben, die linke Gabel wieder hinzulegen. Nach dem Essen legen sie beide Gabeln
wieder hin. Je nach Problemsicht könnte man annehmen, dass sie nach dem Essen erst eine
Denkpause einlegen oder gleich wieder hungrig sind.
Ê
182
Der Übersichtlichkeit wegen machen wir es zum 3-Philosophenproblem:
Abb. 46 3-Philosophen-Problem einfachste Version; unfaires Verhalten möglich
G1#i#3:
H1#i#3:
E1#i#3:
b1#i#3:
e1#i#3:
Gabel
Philosoph
Philosoph
Philosoph
Philosoph
M(Gi) = 1 Y Gabel liegt auf dem Tisch
M(Hi) = 1 Y Philosoph ist hungrig
M(Ei) = 1 Y Philosoph isst
beginnt zu essen
beendet das Essen
Frage: Wie kann man erzwingen, dass die Philosophen nicht zu dick werden, z.B. maximal 3 Mal
essen? Antwort: (ei,Hi)-Kante weg und in Hi 3 Token legen. (Siehe spätere Verallgemeinerung)
183
Abb. 47 3-Philosophen-Problem mit weiterem Prozesszustand; immer noch ist Unfairness
möglich
G1#i#3:
H1#i#3:
E1#i#3:
b1#i#3:
e1#i#3:
Gabel
Philosoph
Philosoph
Philosoph
Philosoph
M(Gi) = 1 Y Gabel liegt auf dem Tisch
M(Hi) = 1 Y Philosoph ist hungrig
M(Ei) = 1 Y Philosoph isst
beginnt zu essen
beendet das Essen
Hinzunahme eines weiteren Prozesszustands, z.B.:
D1#i#3: Philosoph
M(Di) = 1 Y Philosoph denkt
184
Abb. 48 3-Philosophen-Problem; Version 1 zur Vermeidung von Unfairness
G1#i#3:
H1#i#3:
E1#i#3:
D1#i#3:
b1#i#3:
e1#i#3:
Gabel
Philosoph
Philosoph
Philosoph
Philosoph
Philosoph
M(Gi) = 1 Y Gabel liegt auf dem Tisch
M(Hi) = 1 Y Philosoph ist hungrig
M(Ei) = 1 Y Philosoph isst
M(Di) = 1 Y Philosoph denkt
beginnt zu essen
beendet das Essen
Dieser Versuch mit dem Token am rechten Rand der Abbildung zur Erzwingung von Fairness
ist problematisch, wenn der hungrige Philosoph 1 nicht zu essen beginnt, bleiben die anderen auch
hungrig.
185
Abb. 49 3-Philosophen-Problem; Version 2 zur Vermeidung von Unfairness durch
Einführung eines sogen. Tokenrings
G1#i#3:
H1#i#3:
E1#i#3:
D1#i#3:
b1#i#3:
e1#i#3:
Gabel
Philosoph
Philosoph
Philosoph
Philosoph
Philosoph
M(Gi) = 1 Y Gabel liegt auf dem Tisch
M(Hi) = 1 Y Philosoph ist hungrig
M(Ei) = 1 Y Philosoph isst
M(Di) = 1 Y Philosoph denkt
beginnt zu essen
beendet das Essen
186
Petrinetze werden zu Stellen/Transitions-Netzen verallgemeinert: Es können mehr als eine
Marke in einer Stelle (vorher: "Bedingung") vor bzw. nach einer Transition (vorher: "Ereignis")
liegen. Die Markierungsfunktion M ist entsprechend umzudefinieren:
M't(b) = Mt(b) - 1
M't(b) = Mt(b) + 1
M'(b) = M(b)
œ b 0 Ct
œ b 0 tC
sonst
Dies erlaubt die Modellierung von Kapazitätsproblemen bei Puffern.
187
Eine weitere Verallgemeinerung: Einführung eines Pfeilgewichtes g. Um g wird die Markenzahl
der Vor- und Nachstellen einer Transition t verringert bzw. erhöht, also z.B.
M't(b) = Mt(b) - g
œ b 0 Ct .
Noch weitergehende Modellierungsmöglichkeiten bieten Netze mit individuellen Marken und
konstanten Pfeilanschriften
Y
Abb. 50
Abb. 51
Schließlich kann man auch die Pfeilanschriften variabel machen. Beispielsweise würde ein x
statt dem A am Pfeil von 1 nach t bedeuten, dass irgendeine der Marken, also A oder C, verbraucht
wird.
Meist kann man sich nur mittels Simulationen ein Bild über die Eigenschaften eines Petrinetzes
verschaffen. Es gibt auch einige (wenige) analytische Methoden zum Auffinden von Netzinvarianten.
Ein wichtiger Problemkreis ist die Strukturierung von Petri-Netzen mit vielen Knoten im Sinne
von Vergröberungen und Verfeinerungen.
188
22 Graphentheorie
Erste Definitionen und Beispiele
Definitionen:
Ein gerichteter Graph ist ein Tupel G = (Kn, Ka) mit zwei nichtleeren endlichen22 Mengen Kn,
den Knoten(-Bezeichnern), und Ka f Kn × Kn, den Kanten. Die Funktion q : Kn1 × Kn2 6 Kn1
liefert die Quelle einer Kante und analog z : Kn1 × Kn2 6 Kn2 das Ziel. GKn oder Kn(G) bezeichnen
die Knotenmenge eines Graphen und GKa bzw. Ka(G) die Kantenmengen. Zwei Knoten kn1 und
kn2 heißen adjazent oder benachbart, wenn entweder (kn1, kn2) 0 Ka oder (kn2, kn1) 0 Ka ist. Ein
Graph ohne Elemente (kn, kn) in der Kantenmenge heißt schlicht oder schlingenfrei. Ist ka = (kn1,
kn2), so heißen kn1 und kn2 inzident zu ka.
Ê
Beispiel:
Seien für einen Graphen G die Mengen Kn = {1, 2, 3, 4} und Ka = {(1, 2), (2, 4), (4, 2)}. Dann
könnte G so dargestellt werden:
Abb. 52
Dabei ist etwa q((4, 2)) = 4 und z((4, 2)) = 2.
Ê
22
Man kann natürlich auch mit der nichtendlichen Variante arbeiten.
189
Man könnte daran denken, Kn und Ka "unabhängig" voneinander zu wählen. Dann gibt es zwei
Möglichkeiten:
a)
Es gibt inkompatible Bestandteile, wobei z.B. G = ({1, 2, 3, 4}, {(1, 3), (4, 5)}) nicht viel
Sinn ("partielle Graphen") macht.
b)
Man führt eine Korrektur noch mit ein.
Als eine Lösung für b) kann folgendes gelten: Es sei E eine Menge und F eine Tupelmenge.
Dann bezeichne con(E, F) den Graphen mit folgenden Eigenschaften:
Kn(con(E, F)) = E
Ka(con(E, F)) = F 1 E × E .
D.h. also, con "filtert" die brauchbaren Bestandteile von F heraus, wobei die Knotenmenge quasi
höhere Priorität hat.
Z.B. ist con({1, 2, 3, 4}, {(1, 3), (4, 5)}) = ({1, 2, 3, 4}, {(1, 3)}).
Man kann den Kanten die höhere Priorität geben, d.h. die Angabe der Kanten durch Tupel
definiert die Knoten gleich mit. Dann könnte man aber auf die Knoten verzichten.
Wenn man schon liberal ist, warum sollte dann eine Kante nur aus 2 Knoten bestehen?
Sei K eine endliche Menge. Ein Hypergraph H ist dann eine Teilmenge von Kn c Kn×Kn c ...
c Kn × Kn × ... × Kn.23
Sei Kn = {1, 2, 3, 4, 5} und z.B. H = {<1>, <2, 2>, <1, 3, 2>, <5, 4>, <5, 3>}
Abb. 53
Beachte den nichtausgefüllten Kringel bei der Hyperkante 1. Er ist hier nur ein Knoten.
Hypergraphen können also zur Modellierung von Relationen mit einer Stelligkeit > 2 dienen.
(Sonst bedarf es "Klimmzüge" nach einem Satz von Trahtenbrot: "Jede Relation kann als binäre
Relation repräsentiert werden".)
23
Ein Hypergraph ist demnach auch als eine Sprache aus Kn+, ggf. auch aus Kn* aufzufassen.
190
Beispiel:
Eine Familiensituation: "Vater, Mutter, Kinder"
Abb. 54
Anmerkungen:
>
Man kann Bedingungen über die Gestalt von Graphen formulieren, z.B.: Jede Person muss
als Komponente einer Hyperkante auf einer Position $3 im Hypergraphen auftauchen.
Sonst ist sie kein Kind irgendwelcher Eltern, also ein Alien. Diese Bedingung würde zu
einem unendlichen Graphen führen. Oder: "keine Bigamie erlaubt".
>
Man könnte sich die Frage nach einem Erzeugendensystem, also eine Art Graphgrammatik, stellen, deren Anwendung nur "korrekte Familiengraphen" ergibt.
>
Die Funktionen zum Holen von Quelle und Ziel müssten bei den Hypergraphen noch auf
die anderen Komponenten erweitert werden.
Bis auf Weiteres werden nur gewöhnliche Graphen betrachtet.
191
Definitionen:
Die Zahl der von einem Knoten kn ausgehenden Kanten heißt Ausgangsgrad g+(kn); analog die
Zahl der eingehenden Kanten g-(kn) der Eingangsgrad. Die Summe von beiden ist der Grad g(kn)
des Knotens. Eine Kante (kn, kn) heißt Schlinge (und würde doppelt gezählt werden).
Ein Knoten kn mit g-(kn) = 0 heißt Startknoten, einer mit g+(kn) = 0 heißt Endknoten des
Graphen. Ein Knoten k mit g-(kn) = g+(kn) = 0 heißt isoliert.
Ein (ungerichteter) Weg/Pfad (manchmal Semiweg) zwischen zwei Knoten kn1 und knn eines
Graphen G ist eine Folge w = <kn1, ka1, kn2, ka2,...,knn-1, kan-1, knn>, wobei Knoten über die Kanten
"passend" miteinander verbunden sind, also (œi 0 {1, ..., n-1})((q(kai) = kni v z(kai) = kni+1) w
(z(kai) = kni v q(kai) = kni-1))
Die Knoten kn1 bzw. knn heißen Start- bzw. Endknoten des Weges. Bei einem gerichteten
Weg/Pfad vom Knoten kn1 zum Knoten kn2 stimmt auch die Richtung. Demnach muss (œi 0 {1, ...,
n-1})(z(kai) = q(kai+1)) sein. Ein Weg heißt geschlossen, wenn kn1 = knn ist. Ein Weg heißt
einfach, wenn ein Knoten nicht mehrmals besucht wird, d.h. (œi,j 0 {1, 2, ..., n})(kni … knj). Ein
gerichteter, geschlossener Weg heißt Zyklus. Ein Knoten knj heißt Nachfolger eines Knotens kni,
wenn es einen gerichteten Weg von kni zu knj gibt. Analog ist kni Vorgänger von knj. Gibt es
zwischen zwei Knoten kn1 und kn2 eine Kante (kn1, kn2), so nennt man k1 = q((kn1, kn2)) auch
direkten Vorgänger von kn2 und entsprechend k2 = z((kn1, kn2)) den direkten Nachfolger.
Ein Graph G heißt (schwach) zusammenhängend, wenn zwischen je zwei Knoten knr, kns 0
Kn(G) ein ungerichteter Weg (knr, kar, ..., kas-1, kns) existiert. Er heißt stark zusammenhängend,
wenn zwischen je zwei Knoten ein gerichteter Weg existiert.
Ein Knoten kn eines zusammenhängenden Graphen G heißt Artikulation, wenn ein neuer Graph
G' = con (Kn(G) \ {kn}, Ka(G)) nicht mehr zusammenhängend ist, also durch Wegnahme von kn
und der Kanten, zu denen er inzident ist, der Graph in zwei nichtverbundene Teile zerfällt.
Eine Kante ka eines Graphen G heißt Brücke, wenn der neue Graph G' = con(Kn(G), Ka(G) \
{ka}) nicht mehr zusammenhängend ist.
192
Ein Graph G heißt ungerichtet, wenn zu jeder Kante ihre inverse in der Kantenmenge ist, d.h.
also (œ(kn1, kn2) 0 Ka(G)) ((kn2, kn1) 0 Ka(G)).
Statt
wird nur gezeichnet:
Ein ungerichteter Graph heißt vollständig, wenn zwischen je zwei Knoten eine Kante existiert.
Ê
Graphen lassen sich durch Adjazenzmatrizen darstellen. Z.B. hat der folgende Graph
die Adjazenzmatrix
nach
\
1
2
3
4
5
6
7
1
0
1
1
0
0
0
0
2
0
0
0
1
0
0
0
3
0
0
1
0
0
0
0
4
0
1
1
0
0
0
0
5
0
0
0
0
0
1
0
6
0
0
0
0
0
0
0
7
0
0
0
0
0
0
0
von
193
Eine andere Form der Repräsentierung von Graphen geschieht durch direkte Nachfolger- und
Vorgängerlisten. Diese Darstellung eignet sich besonders dann, wenn die Matrix "dünn besetzt"
ist:
Vorgängerliste
Nachfolgerliste
kn1 : i
kn2 : kn1, kn4
kn3 : kn1, kn3, kn4
kn4 : kn2
kn5 : i
kn6 : kn5
kn7 : i
kn1 : kn2, kn3
kn2 : kn4
kn3 : kn3
kn4 : kn2, kn3
kn5 : kn6
kn7 : i
Ein Graph F ist Teilgraph eines Graphen G (Abk.: F # G), gdw. Kn(F) f Kn(G) und Ka(F) f
Ka(G) 1 (Kn(F) × Kn(F)). Also, in der Kantenmenge von F müssen nicht auch alle Kanten von G
sein, die zwischen den gemeinsamen Knoten verlaufen.
Gilt Ka(F) = Ka(G) 1 (Kn(F) × Kn(F)), dann heißt F Untergraph von G, (FfG).
Ein Untergraph Z f G heißt Zusammenhangskomponente von G, wenn Z (schwach) zusammenhängend ist und es in Kn(G) \ Kn(Z) keinen Knoten kn und in Kn(Z) keinen Knoten kn' so
gibt, dass ein ungerichteter Weg zwischen kn und kn' existiert.
Man nennt eine Zusammenhangskomponente auch einen maximalen Untergraphen.
Abstrahiert man von den Bezeichnermengen, und betrachtet man nurmehr die Struktur, so nennt
man zwei übereinstimmende Graphen F und G isomorph (Abk.: F . G). Dies ist genau dann der
Fall, wenn es eine Funktion f : Kn(F) c Ka(F) 6 Kn(G) c Ka(G) so gibt, dass die Restriktion von
f bezüglich der Knoten- und Kantenmengen jeweils eine Bijektion ist, und außerdem gilt:
(œka0Ka(F)) (f(q(ka)) = q(f(ka)) v f(z(ka)) = z(f(ka)))
Ist bei der Isomorphiedefinition F = G, dann nennt man dies einen Automorphismus. Wenn nicht
die triviale Identität gemeint ist, weist die Existenz von Automorphismen auf Symmetrien im
Graphen hin.
Die Begriffe "Isomorphie", "Teil-" und "Untergraph" lassen sich kombinieren, so dass man von
isomorphen Teil- bzw. Untergraphen sprechen kann.24
24
Die Problematik, ob zwei Graphen isomorph sind, oder ob der eine ein isomorpher Untergraph des
anderen ist, wird uns noch im folgenden beschäftigen. Diese Fragen sind im Sinne der Berechenbarkeitstheorie
entscheidbar, denn man braucht "nur" alle Möglichkeiten auszuprobieren, die Graphen aufeinander abzubilden.
Die Komplexitätstheorie beschäftigt sich mit der Frage, wie effizient die Algorithmen sind. Für Probleme aus
der Klasse P kennt man schnelle Algorithmen, für die aus der Klasse NP-vollständig kennt man keine.
Schlimmer noch: Man muss annehmen, dass es überhaupt keine gibt.
Das in der Problemklasse NP liegende Graphisomorphie-Problem ist "offen" in dem Sinn, dass es (noch) nicht
als NP-vollständig bewiesen ist. Es gibt allerdings auch Gründe anzunehmen, dass es das nicht ist. Aber es
spricht einiges dafür, dass es auch nicht in der Problemklasse P ist. Es liegt also in seiner Schwierigkeit quasi
194
Document
Kategorie
Seele and Geist
Seitenansichten
7
Dateigröße
544 KB
Tags
1/--Seiten
melden