Ausschluss-Synchronisation zusammengesetzter Objekte

WS 2003/04 24.11.2003 1

Ausschluss-Synchronisation zusammengesetzter Objekte

Seminar Objektorientierte

Programmiersprachen

Sofoklis Papadopoulos

Ausschlußsynchronisation zusammengsetzter Objekte

2

Gliederung

1. Einleitung2. Ausschlußalgebra 2.1 Ausschlußpaare, Ausschlußausdrücke 2.2 Sperrsynchronisation 2.3 Verfeinerung von Ausschlußausdrücken3. Objektkomposition

3.1 Erweiterung der Algebra mit Objekten3.2 Objektkomposition (zusammengesetztes Objekt)3.3 Splitten von Objekten 3.4 Abwärtskomposition3.5 Aufwärtskomposition

4. Aktive Objekte (herausgenommen)5. Vererbung6. Deadlock7. Praktische Anwendungen

7.1 Design-Notation7.2 Tool Support7.3 Programmiersprachenunterstützung und Optimierung


3

1. Einleitung


4

1. Einleitung• Nebenläufige OO-Programmmierung begann in späten 60er Jahre mit Simula

• erreichte 30 Jahre später durch JAVA einen ersten Höhepunkt

• Beide Sprachen übernahmen Konzept des „passiven“ -oder „threads-plus-objects“- Modell der Neben-läufigkeit:

– Threads haben keinen klaren Zustand – Objekte sind solange passiv, bis sie durch Threads animiert werden

• Aktionen der Threads synchronisieren, um Interferenzen (Störungen) zu vermeiden

• Frühe „threads-plus-objects“-Sprachen (z.B. Smalltalk) verwendeten Semaphore

• Bei Modula-3 und Java basiert Synchronisation zwischen Threads direkt auf

- Objekten, die Threads teilen

- Methoden, die Mechanismus besitzen um andere Methoden auszuschließen


5

1. Einleitung

• Nebenläufige OO-Programme zu entwickeln ist schwierige & aufwendige Aufgabe

• Korrekte Programme müssen Koordination zwischen multiplen Threads, die auf (zusammengesetzte) Objekte zugreifen, korrekt durchführen

• Effiziente Programme müssen Ausgewogenheit zwischen Komplexität und Kosten der Koordinationsmechanismen auf der einen Seite und steigender Performance, möglich durch Nebenläufigkeit, auf der anderen Seite ausbalancieren

???


6

1. Einleitung

• Das Problem hierbei: Wie kann man Ausschlußbedingungen für System zusammengesetzter Objekte designen, die gleichzeitig:

– Interferenzen der Threads vorbeugen

– Nebenläufigkeit im System maximieren

– Die Unkosten, die dabei anfallen minimieren


7

1. Einleitung

• Programmierer, der Nebenläufiges System implementiert, hat folgende Möglichkeiten:

– Einprozessorzugriff des Systems

– Maximale Nebenläufigkeit auf alle Komponenten des Systems ermöglichen, mit Locks auf einzelnen Objek-ten, falls nötig

– Ausschlußschema gesamte System entwickeln, dass individuelle Locks benutzt , um Nebenläufigkeitsan-forderungen der Komponenten zu erfüllen und dabei einen hohen Grad an Nebenläufigkeit realisiert


8

1. Einleitung

• Einprozessorzugriff des Systems (single threading):– Keine Interferenzen zwischen Komponenten des Systems

– Geringe Kosten (ein Lock)

– Eliminiert aber Nebenläufigkeit des Systems

• Maximaler Nebenläufigkeitszugriff:– Erhöht # Threads im Programm

– Erfordert hohen Grad an Sperrsynchronisation, um Interferenzen zu vermeiden

– Mit dementsprechend hohen Kosten

• Ausschlußschema für das gesamte System:– Liefert vernünftigen Grad an Nebenläufigkeit

– Vermeidet Interferenzen

– Minimiert Implementierungskosten


9

Gliederung1. Einleitung2. Ausschlußalgebra 2.1 Ausschlußpaare, Ausschlußausdrücke 2.2 Sperrsynchronisation 2.3 Verfeinerung von Ausschlußausdrücken3. Objektkomposition


4. Aktive Objekte5. Vererbung6. Deadlock7. Praktische Anwendungen



10

2. Ausschlußalgebra


11


• Wissenschaftliche Arbeit von:

– James Noble– David Holmes– John Potter

• aus dem Jahre 2000


12


Lösung des Design-Problems: Die Ausschlußalgebra

Anforderungen

• Einfaches Modell zur Modellierung von Ausschlußbedingungen

• Ausschlußanforderungen bei zusammengesetzten Objekten

• Betrachtet werden Methoden und ihre Ausschlußbedingungen (zusammengesetzter Objekte)

• Beschreibt welche Methoden nebenläufig ausgeführt werden können & welche nicht


13


• basierend auf diesen Anforderungen bestimmt die Algebra wie explizit die Ausschlußbedingung dem zusammenge-setzten Objekt beigefügt wird

• Ausschlußbedingungen können innerhalb von zusammen-gesetzten Objekten aufwärts bzw. abwärts entwickelt werden

• Entfernen von redundanter Sperrsynchronisation

• Demonstrieren, dass das potentielle Schema wirklich alle Ausschlußanforderungen eines jeden Objektes erfüllt


14


• Kalkulationen, werden auf einem abstrakten Level gehalten

• Nutzen beim Design von Nichtsequentiellen OO-Systemen

• Programmierer können Alternativen ausloten & können

Zuversicht in ihr Design gewinnen

• Erlaubt die Anforderungen und Bedingungen von Container-Objekten (Nebenläufigkeit) und ihrer Kompo-nenten auszudrücken


15


• Synchronisation von Threads hat verschiedene Aspekte

- ausschlußbedingt

Threads werden ausgeschlossen, falls andere Threads

auf das gleiche Objekt schon zugreifen

- statusbedingt:

Zugriffe, werden solange das Objekt nicht im „korrekten“ Zu-

stand ist verzögert

- koordinationsbedingt:

kontrollieren multipler Methodenaufrufe durch versch. Objekte


16


• Die Ausschlußalgebra:

– Modelliert methodenbasierten Ausschluß zwischen Objekten

– man betrachtet die Bedingungen unter denen Methoden durch Objekte entweder ausgeführt werden oder nicht ausgeführt werden

– Annahme: multiple Nachrichten können gleichzeitig von multiplen Threads gesendet werden

– Es werden nur Methoden betrachtet, die innerhalb des Objekt benutzt werden (nicht der Status des Objektes)


17






18

2. Ausschlußalgebra 2.1 Ausschlußpaare, Ausschlußausdrücke

• Modellierung von Methodenausschluß durch Mengen von Ausschlußpaaren (oder äquivalente Ausschlußmatrix)

Complex Number Class:

Class Complex {

private long re;

private long im;

public long a() {return re;}

public long b() {return im;}

public void c(long re_, im_) {re = re_; im = im_;}

}

• Menge von Methodennamen: {a,b,c}• Menge von Ausschlußpaaren: {(a,c),(b,c),(c,c)}

a b c

a x

b x

c x x x


19


• Menge von Methodennamen: {a,b,c} Namen der Methoden

• Menge von Ausschlußpaaren: {(a,c),(b,c),(c,c)}– (a,c) bedeutet, wenn Methode a innerhalb des Objektes ausge-

führt wird, dann muß die Methode c solange ausgeschlossen werden, bis a seine Ausführung komplettiert hat

– (b,c) dementsprechend die gleiche Bedeutung

– (c,c) hat die Bedeutung des gegenseitigen Ausschlusses

c schließt sich selber aus, falls c im Thread ausgeführt wird, darf ein anderer Thread zur gleichen Zeit c nicht auf demselben Objekt ausführen

– Ausschlußrelation und Matrix = symmetrisch, d.h. falls a b ausschließt, dann muß b auch a ausschließen


20


• Ausschlußausdrücke liefern kürzere Beschreibung von

Auschlußbedingungen als Ausschlußpaare

• Ausdrücke basieren auf 3 Operatoren:– Konjunktion „e | e“

– Ausschluß „e X e“– Gegenseitigen Ausschluß „ e “

– e1 X e2 sagt aus, dass Methoden benannt in e1 Methoden in e2 ausschließen (gilt auch andersherum)


21


• Bei Gültigkeit dieser Operatoren drückt der Ausdruck (a | b) X c (dasselbe wie die Matrix von vorhin ausdrückt) folgendes aus:

Paare Namen

a { } {a}

(a | b) { } {a,b}

c {(c,c)} {c}

(a | b) X c {(a,b),(b,c),(c,c)} {a,b,c}

• Namen eines Ausdrucks, sind Namen der Methoden benutzt in die-sem Ausdruck

• Paare, ist die Menge der Ausschlußpaare, die durch die Ausschluß-operatoren beschrieben werden


22


• Manche Ausdrücke wie a | b besitzen keine Paare aber haben dafür einen oder mehrere Namen (in diesem Fall {a,b})

• Der Konjunktions-Operator ist („|“): idempotent, assoziativ und kommutativ

• Der Ausschluß-Operator ist („X“):

assoziativ, kommutativ und X hat höhere Priorität als |

• Beide Binär-Operatoren haben eine Identität „0“, d.h. keine Namen und Paare

• Syntaktische Abkürzung für e1 | e2 | … | e1 ist e1e2…e1


23






24

2. Ausschlußalgebra 2.2 Sperrsynchronisation

• Mit den Operatoren lassen sich Sperrsynchronisationspolicen be-schreiben, z.B.:

- einfache Sperr-Policy, um die Ausführung von Methoden

(m1m2…mN) zu kontrollieren

- eine Methode kann die Sperre halten und Methode ausführen

- also jede Nachricht gebunden an die Sperre ist selbstaus- schließend und schließt jede andere Nachricht aus


25


• Solch eine Sperre kann so definiert werden:

LOCK(m1m2…mN) = (m1 X m1) X (m2 X m2) X…X (mN X mN)

• Besitzt folgende Menge von Ausschlußpaaren:

{(mi,mj) | i,j ∈ 1..N}

kürzere Schreibweise

LOCK(m1m2…mN) = m1m2…mN


26


• Erweiterung zur Lese/Schreibe-Menge jede Anzahl an Lese-Methoden kann ausgeführt werden, aber nur eine Schreibe-Meth.

• READ-WRITE-SET(r1r2..rN,w1w2..wM) =

(r1| r2|…| rN) X (w1 X w1) X (w2 X w2) X…X (wM X wM)

• Man nutzt die abkürzende Schreibweise:

READ-WRITE-SET(r1r2...rN,w1w2..wM) = r1r2…rN X w1w2…wM


27


• Algebra kann verschiedene Möglichkeiten von Lese/Schreibe- Mengen illustrieren

• z.B. zwei Lese/Schreibe-Mengen, die dieselbe Menge an Schreibern

teilen ( ≙ mit einer einzigen Menge Schreibern und alle Lesemeth.)

r1 X w1 | r2 X w1 ≡ (rwset)

r1 X w1 | w1 X w1 | r2 X w1 | w1 X w1 ≡ (idem)

r1 X w1 | w1 X w1 | r2 X w1 ≡ (rwset)

r1r2 X w1• Eine Lese/Schreibe-Menge effizienter zu implementieren, obwohl

vielleicht zwei einzelne Ausdrücke einfacher zu spezifizieren


28






29

2. Ausschlußalgebra 2.3 Verfeinerung von Ausschlußausdrücken

• Verfeinerung von Ausschlußausdrücken unterliegt der Semantik der Ausschlußpaare

• Ein Ausschlußausdruck e wird durch einen anderen Ausschluß-

ausdruck f verfeinert, falls die Werte (Namen und Paare) von e eine

Untermenge der Werte von f ist

• Wir schreiben dann: e ⊑ f

• z.B.: a X b ⊑ a X b X c , da die Namen und Paare

des ersten Ausdrucks ({a,b} und {(a,b),(b,a)}) Untermengen der

Namen und Paare des zweiten Ausdrucks ({a,b,c} und {(a,b),(b,a), (a,c),(c,a),(b,c),(c,b)}) ist


30


• Beispiel, Verschmelzen von Sperren:

Sperren während Laufzeit teuer, jede Sperre im Programm benötigt Datenstrukturen, die diese Funktion unterstützen. Kosten zur Aus-führung viel Zeit, wenn ein Thread sie anfordert.

-Objekt, dass zwei private long Integer-Variablen v1 und v2 enthält und

mittels zwei Lese-Methoden (r1 und r2) zugreifbar und werden durch

zwei Schreibe-Methoden (w1 und w2) aktualisiert

-Ausschlußanforderungen: r1 X w1 | r2 X w2


31


• Beispiel:

r1 X w1 | r2 X w2 ⊑ (|) (r1 | r2) X w1 | (r1 | r2) X w2 ⊑ (X)

(r1 | r2) X (w1 X w2) | (r1 | r2) X (w1 | w2) ≡ (idem) (r1 | r2) X (w1 X w2) ≡ r1r2 X w1 w2

• resultierender Ausschlußausdruck beschreibt alle Ausschluß-paare des Originalausdrucks, aber schließt noch andere Paare mit ein hier: (w1,w2), (r1,w2) und (r2,w1)


32






33

3. Objektkomposition

• Ausschlußausdrücke bis jetzt Ausschluß eines einzigen, einfachen Objekts

• Aber in Realität bestehen die meisten OO-Systeme aus mehr als einem Objekt

• Objekt-Komposition (zusammengestzte Objekte) kann eine bessere Kontrolle über Objekte und ihre Ausschlußanforderungen liefern

• Als auch die Funktionalität größerer Systeme bewahren

• Wie können Objekte und zusammengesetzte Objekte in der Algebra explizit behandelt werden ?


34






35

3. Objektkomposition3.1 Erweiterung der Algebra mit Objekten

• Modellierung von Systemen mit multiplen Objekten

• Objekte beschrieben in „☾“ -und „☽“-Klammern

• Objekte können folgende Definitionen enthalten:

– req: e = zeigt die Ausschlußbedingung an, die vom Objekt ge-fordert wird

– Ein anderer Ausschlußausdruck e, der die aktuell implemen-tierte Ausschlußbedingung angibt

– Mögliche interne Komponenten


36


• Beispiel: zwei einfache unabhängige Objekte a und b

• a = ☾ m = (body of method m…) n = (body of method n…)

m X n ☽ b = ☾ m = (body of method m…) n = (body of method n…) mn ☽• Gesamtausdruck des einfachen Systems mit 2 Objekten:

(a.m X a.n) | b.m b.n


37


• Ein Ausschlußausdruck gilt für das Objekt, dass es beinhaltet

• Ein Ausdruck für ein Objekt, ist unabhängig vom Ausdruck eines anderen Objektes

• Kombinierter Ausdruck von verschiedenen Objekten wird durch das „joinen“ der einzelnen individuellen Ausdrücke mit „|“-Opera-tor

• Haben die Methoden der Objekte gleiche Namen, dann Methoden-namen durch prefixing mit Objektnamen definieren (renaming)


38






39

3. Objektkomposition 3.2 Objektkomposition (zusammenges. Objekt)

• Objekte können selber wieder aus Objekten bestehen, die wieder-um auch Methoden und Ausschlußausdrücke enthalten können

• z.B. 2 unabhängigen Objekte a und b (voriger Abschnitt) könnten zu einem umschließenden Container-Objekt umdefiniert werden:

c = ☾ a = ☾ m = (body of method m…) n = (body of method n…) m X n ☽ b = ☾ m = (…) n = (…) mn ☽ y = (a.n;b.n) z = (a.m;b.m ☽


40


• Die Algebra benutzt ein restriktives Modell der Objektkomposition

• Struktur der Komposition ist fix und die Komponentenobjekte

sind nur über ihren direkt umschließenden Container sichtbar und zugreifbar

• In der Praxis bei jeder Implementation der Komposition muß

Container-Objekt die Komponenten privat speichern und exportiert keine Referenzen an Komponenten anderer Objekte

• (Obwohl restriktiv soll es sich nah an Programmierstilen, wie

Balloon Types, Confined Types und Flexible Alias Protection

halten)


41


• Eine Implementation der Algebra folgend könnte in der Praxis flex-ibler sein

• Ausdrücke eher Spezifikationen als finale Beschreibung der Impl.

• Objekte könnten ausgetauscht werde, vorausgesetzt sie erfüllen die passende Spezifikation

• fixe Struktur unterstützt Analyse und Modellierung

z.B. die Aufrufer einer Methode bestimmen

• Container-Methode kann nur Methoden seiner direkten Komponen-ten aufrufen und Komponenten-Methoden können nur vom um-schließenden Container aufgerufen werden


42






43

3. Objektkomposition 3.3 Splitten von Objekten

• Ausschlußanforderungen, Verhalten und Invarianten einiger Obj.

können in unabhängige Untermengen partitioniert werden

• In solchen Fällen sinnvoll, wenn man das Original-Objekt in eine Komposition aufteilt

• Jede Untermenge ist separate Komponente, die von einem Con-tainer umschlossen

• Container ruft eigene Methoden der passenden Komponenten auf

Objekt-Splitten Gegenteil von Sperren-Verschmelzung

-Splitten teilt Objekte um Nebenläufigkeit zu erhöhen

-Verschmelzung kombiniert Objekte um Nebenl. zu reduzieren


44


• Original-Objekt:

☾ a = (body of method a…) r1 = (body of method r1…) r2 = (…) w = (…) a = (…) a | r1 r2 X w ☽

a | r1 r2 X

w =

• Aufgesplittetes Objekt:

☾ c_a = ☾ a = (body of method a…) a ☽ c_rw = ☾ r1 = (body of method r1…) r2 = (body of method r2…) w = (…) r1r2 X w ☽ a = (c_a.a) r1 = (c_rw.r1) r2 = (c_rw.r2) w = (c_rw.w) ☽

c_a.a | c_rw.r1 c_rw.r2 X c_rw.w


45


• Ausschlußanforderungen splitten sich in 2 unabhängige Teilaus-drücke auf in a und r1r2 X w (Original-Objekt)

• Sind unabhängig, da sie keine gemeinsamen Namen besitzen

• In dieser Komposition Container-Methoden unsynchronisiert

(haben keine Ausschlußbedingungen)

• Ausschlußbedingungen für gesamte Komposition berechenbar

solange Komponentenseparat sind, keine Namen gemein haben

und das Container-Objekt keinen Ausschluß definiert

a | r1 r2 X w = c_a.a | c_rw.r1 c_rw.r2 X c_rw.w


46






47

3. Objektkomposition 3.4 Abwärtskomposition

• Abwärtskomposition erlaubt einem Container-Objekt seinen inter-nen Komponenten Ausschlußbedingungen bereitzustellen

• Kann die Implementation eines zusammengestzten Objektes optim.

• da Komponenten keine expliziten Ausschlußbedingungen benöt.

wenn Container- Ausschlußbedingungen sichern, dass die Kom-ponenten-Anforderungen getroffen werden


48


• Beispiel: ZusammengesetztesObjekt mit unsynch.Methoden

c = ☾ o1 = ☾ x = (…)☽ o2 = ☾ y = (…) ☽

a = (o1.x) b = (o1.x; o2.y) a X b ☽

• Mit der Algebra kann man den effektiven Ausdruck einer Komponente bestimmen

• Durch inspizieren der aufrufenden Methoden (callers)

• Container kapselt die Komponenten

-somit einzige Methode die Komponen tenmethoden aufzurufen durch

Containermethoden


49


• Regel für die Abwärtskomposition:

Für eine Komponentenmethode o.m1, die andere Komponentenme-

thode o.m2 ausschließt, müssen alle Methoden ihres umschließen

den Containers c, die o.m1 aufrufen, alle Methoden des umschlie-

ßenden Containers, die o.m2 aufrufen, ausschließen.

callers(o.m1) X callers(o.m2) ⊑ c


50


• Eine Komponente erhält einen o^downward-Ausschluß seines um- schließenden Containers, wenn:

o^downward [callers(o.m1) / m1, callers(o.m2) / m2, … ,

callers(o.mN) / mN] ⊑ c, wobei callers (o.mi) die Konjunktion („|“) aller Container-

Methoden, die o.mi der Komponente o aufrufen und e [T1 / t1,…,TN / tN] ist e mit Ti substituiert an Stelle von ti


51


• Diese Definition fordert nicht, weder von Komponenten noch vom

Container das sie Single-Threaded sind

• Bedingungen, die es erlauben Multi-Threads auszuführen werden ebenfalls von dieser Def. Unterstützt (z.B. Lese/Schreibe-Mengen)

• Auch Selbstausschluß wird gesichert

(z.B, wenn Komponente o.mi sich selbst ausschließt, dann müssen

alle Aufrufer von o.mi sich ebenfalls selbst ausschließen)


52


c = ☾ o1 = ☾ x = (…)☽ o2 = ☾ y = (…) ☽

a = (o1.x) b = (o1.x; o2.y) a X b ☽

• y [callers(o2.y) / y] ≡ (callers)

y [b / y] ≡ (subst)

b ⊑ (intro) a X b

• x [callers(o1.x) / x] ≡ (callers)

x [ab / x] ≡ (subst)

a | b ⊑ (intro) a X b

• x [callers(x) / x] ≡ (callers)

x [ab / x] ≡ (subst)

ab ⋢ a X b


53


• Löschen redundanter Ausschlußbedingungen:

• cache = ☾ ram = ☾ (req: get X put); get put☽ disk = ☾ (req: get X put); get put☽ get‘ = (ram.get; disk.get) put‘ = (ram.put; disk.put) get‘put‘ ☽ Manche Synchronisation ist redundant

• disk[callers(disk.get) / get‘, callers(disk.put) / put‘] ≡

get X put[get‘ / get, put‘ / put] ≡

get‘ X put‘ ⊑ get‘ put‘• cache-Container Objekt-Ausschluß kann sicher zu get‘ X put‘

reduziert werden, da Unterkomponentenanforderungen ge-troffen


54






55

3. Objektkomposition 3.5 Aufwärtskomposition

• Aufwärtskomposition erlaubt Container von den Ausschlußbedingungen seiner internen Komponenten zu profitieren

• Beispiel C++-Version der Complex Number-Class:

class RWComplex{ private: long re;

long im; ReadWriteLock rw; public: long a() {Guard guard(rw.readLock); return re;} long b() {Guard guard(rw.readLock); return im;} void c(long re_, long im_){ Guard guard(rw.writeLock); re = re_; im = im_;}

Benutzt Aufwärtskomposition um Lese/Schreibe Sperrsynchronisation

zu ermöglichen


56


• Vorteil von Aufwärtskomposition, dass Container seine Methoden ausführt, während er die Sperrsynchronisation an seine internen

Komponenten deligiert

• Kein Vergleich zu Standard Methodenaufruf, da Container-Methode

Irgendwie eine Sperre der Komponente anfordern muß, sie solange

hält, bis die Methode komplett ausgeführt wurde, um sie dann frei-zugeben

• In der Algebra modelliert mittels Wächter-Methoden (guarded methods)


57


• Eine Wächter-Methode beginnt mit einer Serie von Wächtern, ge-folgt von einem „“ und einem Methoden-Block

• Eine Wächter-Methode kann nur dann ausgeführt werden, wenn

alle seine Wächter simultan ausgeführt werden dürfen

• Beispiel: m = (o1.a, o2.b … body of method m) • o1.a und o2.b simultane Ausführung zulässig, dann m ausführen

• Similar zur C++-Funktion:

public void m(){ Guard guard(o1.a); Guard guard(o2.b); //…….Block von m }


58


public void m(){ Guard guard(o1.a); Guard guard(o2.b); //…….Block von m }

• Wächter Modellieren „schützende“ Methodenaufrufe mit spezifi- zierter Sperrsynchronisation (keine statusbedingte Synchroni-

sation) co = ☾ l1 = ☾ r X w☽ l2 = ☾ e ☽ a = (l1.r …body of method a) b = (l1.w…body of method b) c = (l1.w,l2.e …body of method c) d = (l2.e …body of method d) ☽


59


• Gegeben: eine Wächter-Methode

o1.g1,…,oN.gN auf die Ausschlußbedingungen

des Containers schließen, gegeben durch jede Methode oi.gi

• Nicht immer einfach, da Ausschlußbedingungen mehr als eine Me-thode betreffen können

• Eine Container-Methode oi.gi sollte jede andere Container-Methode

oi.gj ausschließen, falls die oi-te Komponente Methhode oi.gj ausschließt


60


• Ausschlußbedingungen beigesteuert von Komponente co_i-up

• co_i-up = oi [guards(oi.g1) / m1,…,gurads(oi.gN / mN],

wobei

guards(oi.gj) sind Container-Methoden, die Wächter Methode gj der oi-ten Komponente besitzen


61


co =☾

l1 = ☾ r X w☽

l2 = ☾ e ☽

a = (l1.r …body of method a)

b = (l1.w…body of method

b)

c = (l1.w,l2.e …body of

method c)

d = (l2.e …body of method d)

☽

• Gesamter Ausschlußausdr. ist

l1[guards(l1.r) /r,guards(l1.w) /w] ≡ (grds)

r X w[a/r,bc/w] ≡ (sub)

a X bc• Sichert, dass a und bc eine Lese/

Schreibe-Menge a X bc darstellen

l2[guards(l2.e) /e] ≡ (grds)

e[cd/e] ≡ (sub)

cd• Sichert, dass c und d sich gegen-

seitig ausschließen und eine Schreibe-Menge dartsellen

Konj. der Ausschlüsse (a X bc) | cd


62

Gliederung1. Einleitung2. Ausschlußalgebra 2.1 Ausschlußpaare, Ausschlußausdrücke 2.2 Nebenläufigkeitskontrolle 2.3 Verfeinerung von Ausschlußausdrücken3. Objektkomposition





63

4. Aktive Objekte

• Sind Objekte, die eigene Threads besitzen

• Falls Komponente aktiv, dann ruft sie eigenen internen Thread

• In der Algebra ein „∗“ vor Definition eines aktiven Objektes setzen

• Ausschlußbed. eines aktiven Objektes werden auf Threads intern

und auf Threads extern angewendet

• Alle Mechanismen der Algebra können auf aktive Threads ange-

wendet werden, außer Abwärtskomposition• ?


64

4. Aktive Objekte

• Bei Abwärtskomposition, nehmen wir an, dass Threads eine in-terne Komponente nur durch ihren dazugehörigen umschließenden Container ansprechen dürfen !!!!

• Und müssen somit die Ausschlußbedingungen des Containers treffen

• Gleichzeitig gibt es keine Einschränkung bei der Aufwärtskompo-sition, da Wächter-Methoden keine Voraussetzungen an ihren umschließenden Container stellen


65






66

5. Vererbung• Vererbung wird in der Algebra dadurch dargestellt, dass Kombina-

tion der Ausschlußausdrücke von Klassen und ihrer Super-Klassen JAVA-CLASS (u,s) = u | s , u = unsynchr. & s =

synchr. • Erweiterung der Basisdefinition durch Vererbung JAVA-CLASS-I (u,v,s,t) = (u | v‘) | (s X t‘) where v‘ = v [u‘ / u, s‘ / s] t‘ = t [u‘ / u, s‘ / s ]

• Lokale Definitionen u = unsynchr. & s = synchr. plus geerbte Me- thoden v (unsynchr.) & t (synchr.)

• Substitution sichert, dass überschriebene Methodennamen mit „‘“ benannt werden


67

5. Vererbung• Similar zu super in Java oder Smalltalk, oder prefixing Basis-

klassenmethoden mit dem Basisklassenname in C++

• Resultierende Klasse besitzt alle, lokale wie auch geerbte Metho-den mit den überschriebenen veerbten Methoden neu benannt

• diese Formulierung impliziert nicht Verfeinerung, da Vererbung den

Status der Methoden verändern kann , z.B.:

JAVA-CLASS(aby, cdz, 0, 0) ≡ aby | cdz

JAVA-CLASS-I(aez, cfy, aby, cdz) ≡ (aez | a‘by‘) | (cfy X c‘dz‘) ≡ !!! Siehe y

und z aa‘bey‘z | cc‘dfyz‘

• aby | cdz ⋢ aa‘bey‘z | cc‘dfyz‘


68






69

6. Deadlock• Algebra konzentriert sich auf Sicherheitsaspekt (Threads stören

sich nie gegenseitig) und vernachlässigt Lebendigkeit (ein Thread

mindestens schreitet immer fort in seiner Ausführung)

• Verfeinerung fordert, dass jeder Ausdruck egal in welchem Kon-text verstärkt wird, obwohl dieses zum Deadlock führen kann

• Sicherheit ist ein lokaler Aspekt, während Lebendigkeit ein globa-ler Aspekt ist bei der Untersuchung der Objektkomposition und dem System in das es eingebettet ist

• Deswegen müssen die beiden Punkte individuell analysiert werden

(Sicherheit = lokale Analyse und Lebendigkeit = globale Analyse)


70






71

7. Praktische Anwendungen 7.1 Design-Notation

• Benutzt bei Modellieren von Auschlußbedingungen in existier-enden oder geplanten Software-Designs

• In drei Phasen:

– Modellieren der Basis der Unter-Komponenten-Struktur des Systems

– Modellieren der verkürzten Ausschlußanforderungen jeder Kompo-nente

– Verteilung der Sperrsynchronisation auf die Zusammengesetzte Struk-tur


72






73

7. Praktische Anwendungen 7.2 Tool Support

• Experimente mit Prototyp, der Kalkulationen der Ausdrücke über-nimmt

• Erlaubt Benutzer Ausschlußausdrücke zu manipulieren, Verfein-erungen vorzunehmen und sie zu verifizieren

• Werkzeug kann Ausschluß innerhalb der Komposition analysieren

• Kann effektive totale Ausschlußanforderung berechnen

• Wird erweitert um den Prozess visualisiert darzustellen


74

Zusammenfassung

• Ausschlußalgebra beschreibt die Ausschlußbedingungen in zusammengesetzten Objekten

• Durch Upwards-und Downwards-Komposition besteht Möglichkeit für Programmierer mit ihrem Design zu experimentieren, es zu verifizieren und es ggf. zu optimieren

trotz evtl. sehr hohen Grad an Multithreading im Design

• Durch abstrakte Beschreibung des Designs kann die Ausschlußalgebra als Notation während der gesamten Software-Entwicklungsphase benutzt werden


75

[email protected]

Danke für‘s Zuhören

einen schönen Abend…

mailto:[email protected]

Documents

Ausschluss-Synchronisation zusammengesetzter Objekte