Dr. Welf Löwe und Markus Noga1 Gliederung: Teil 3 - Anpassungen 1. Einführung –Motivation –Definition, –Konzepte für Komponenten (klassische, kommerzielle,

Dr. Welf Löwe und Markus Noga 1

Gliederung: Teil 3 - Anpassungen

1. Einführung– Motivation– Definition, – Konzepte für Komponenten (klassische, kommerzielle, akademische)

2. Industrielle Komponentensysteme der 1. Generation1. CORBA 2. Enterprise JavaBeans3. (D)COM

3. Anpassungen – Daten und Funktion– Interaktion

• Kommunikation• Synchronisation• Protokolle

– Lebendigkeit


Problem

Komponenten zusammengesetzt

Komponentenprotokoll erzwungen– Guarded methods (Locks)– „Unerwartete“ Methoden werden blockiert

Nichts „Falsches“ passiert

Frage: passiert überhaupt etwas?

Lebendigkeit des Komponentensystems muss garantiert werden.


Beispiel: Telecom-Channel

dial answer

talk

hang up

/ send voice data

signal quitring bell signal answer


Komponentensystem

Caller

Channel

Callee


Caller und Callee symetrisch

Caller

Channel

Callee

send

receivesend

receive

Schnittstellen Sender und Receiver

class Sender{sync dial(int n){

channel.dial(n);}sync answer(){

answered.signal();channel.answer();

}sync talk(VoiceData d){

answered.wait();channel.talk(d);answered.signal();

}sync hangUp(){

channel.hangUp();answered.init();

}}

class Receiver{sync ringBell();

sync signalAnswer() {answered.signal();

}

sync sendVoiveData(VoiceData d);

sync signalQuit() {answered.init();

}}


Petri-Netze

Bipatiter Graph

Stellen- mit Verweis auf Transitionsknoten

Transitions- mit Verweis auf Stellenknoten

Situation:– Markierung der Stellen mit Marken

Lauf: – Übergangsfunktion: Situation Situation– Sind all Vorstellen einer Transition belegt, wird deren Markierung

gelöscht und die Nachstellen markiert– Schalten nichtdeterministisch aber fair

Petri-Nets

dial answer hang upring bell talk send voice data signal quit




dial signal answer hang upring bell talk send voice data signal quit








Problem

Wie zeigt man, dass keiner dieser Läufe verklemmt? – garantiertes Schalten– kein Deadlock

Wie zeigt man, dass lediglich Teile des Netzes schalten?– alle Transitionen schalten irgendwann– kein Livelock

Randbedingung dabei– Simulation zeigt einen Lauf– Allgemein unendlich viele Läufe– Beweis durch Probe ausgeschlossen

dial answer hang upring bell talk signal quit

1 3 6

7

2 4

5

81

2 3

4

5 6

7

8 1110

9

9


Transitionsmatrix C

t1 t2 t3 t4 t5 t6 t7 t8 t9s1 -1 1s2 -1 1s3 1 -1s4 1 -1s5 1 -1s6 1 -1s7 1 0 -1s8 1 1 -1s9 -1 1 -1

s10 1 -1s11 1 -1


Transitionsinvariante

T-Invariante

Vektor entsprechend den Transitionen

Gibt Anzahl von Schaltungen an, die zur Ausgangssituation führt

Bestimmen durch Lösen von:

Cd=0


Lösen von Cd=0

-1 1 d1-1 1 d21 -1 d31 -1 d4

1 -1 d51 -1 d61 0 -1 d7

1 1 -1 d8-1 1 -1 d9

1 -1 d101 -1 d11

= 0

d1=d2=d3=d4=d5=d7=d8=d9=d10=d11=1d6=2


Lebendigkeitsbedingung

di sind verschieden von 0– jede Transition schaltet irgendwann– kein Livelock

Verklemmungsfreie Schaltfolge – aus der initialen Belegung– maximal exponentiell viele Folgen– kein Deadlock

Im Beispiel– t1 t2 t3 t4 t5 t6 t7 t8 t10 t11– jede Transition schaltet einmal


Problem

Betrachtete Systeme sind endlich

Keine dynamische Erzeugung von Objekt

Im Beispiel– Ein Kanal – Beliebig viele potentielle Telefonierer

Schalten an Bedingungen geknüpft, die vom Programmzustand abhängen

Im Beispiel– Anschalten von BND Abhördienst bei „kritischen“ Dateninhalten

Lösung algebraische Petri-Netze


Algebraische Petri-Netze

Idee:– Markiere Stellen mit Termen einer Termalgbra– Konstruiere Terme auf den Kanten– Rechne auf den Stellen entsprechend den Rechengesetzen der

Algebra

Interpretation:– Netz entspricht der Komponente– Term der Algebra entspricht Objekten der Komponente– Stelle und Term entspricht dem Zustand

Algebraic Petri-Nets


Ni i

i i i ii i

ii

i i

i i

i i

i i

Algebraic Petri-Nets


Ni i

i i i (i,d)i i

ii

i i

i i

(i,d) d

i i

ok(d)


Transitionsinvariante

Voraussetzung Wohldefiniertheit– wie bei einfachen Netzen– zusätzlich „Sortenreinheit“: Stellen enthalten nur Terme einer

Algebra

T-Invariante, wenn keine Operationen auf den Kanten– Vektor entsprechend den Transitionen– Gibt Anzahl von Schaltungen an, die zur Ausgangssituation führt– Bestimmen durch Lösen von: Cd=0

Sonst– Beweis durch symbolisches Rechnen– i.a. unentscheidbar


Alternative

Bislang – Deadlockvermeidung– Garantie, das System ist lebendig– Statisch sicher

Alternative– Deadlockerkennung– Erkenne zur Laufzeit, wenn Deadlock eingetreten ist– Dynamisch sicher

Nachteil– Laufzeitprobleme– Was tun, wenn Deadlock erkannt wurde


Problembeschreibung

Abhängigkeitsgraph– Bipatiter Graph– Prozessknoten warten auf Locks– Locks sind von Prozessen aquiriert

Deadlocksituation– Zyklus im Abhängigkeitsgraph


Beispiel

class ProcessOne extends Thread{

public void run(){l1.wait();l2.wait();

doSome();

l2.signal();l1.signal();

}}

class ProcessTwo extends Thread{


doSome();


}}


Abhängigkeitsgraph Beispiel - ok

ProcessOne

ProcessTwo

l1

l2


Beispiel



doSome();


}}



doSome();


}}


Abhängigkeitsgraph Beispiel - deadlock

ProcessOne

ProcessTwo

l1

l2


Klassifikation der Lösungsansätze

Timeout– Nach bestimmter Wartezeit stellt Prozess Erfolglosigkeit des

Wartens fest– Versuch wird mit Fehler abgebrochen– Keine Erkennung im eigentlichen Sinn

Zentrale Erkennung

Dezentrale Erkennung


Zentrale Erkennung

Eine Komponente wird zentraler Deadlockerkenner

Alle Wartesituationen werden– aktiv der Zentrale gemeldet– zyklisch von der Zentrale abgefragt

Zentrale setzt den Abhängigkeitsgraphen zusammen

Stellt fest, ob er zyklisch ist

Löst Zyklus auf, indem ein Prozess mit Ausnahme terminiert, der damit sein Lock freigibt


ProcessOne sendet Abhängigkeit



doSome();


}}



doSome();


}}


ProcessTwo sendet Abhängigkeit



doSome();


}}



doSome();


}}


Phantom deadlock

ProcessOne

ProcessTwo

l1

l2


Auflösung

Theorie:– Mehrphasenprotokolle – dabei Locking des Programmlaufes– ineffizient

Praxis– Man lebt mit Fehlerhafter Erkennung– Nachprüfen des Ergebnissen eliminiert die meisten

Phantomdeadlocks


Dezentrale Erkennung

Keine Zentrale Entscheidungsinstanz

Kein „Bottleneck“ in verteilten Anwendungen

Klassifikation– Pfadsende Algorithmen– Testnachrichten Algorithmen– Globale Zustandserkennung


Pfadsende Algorithmen

Berechnen lokalen Teil des Abhängigkeitsgraphen

Mögliches Unwissen über andere Teile wird explizit in lokalen Graphen codiert– „External“ – Knoten im Graphen für aquirierte oder nachgefragte

Locks von Entfernten Komponenten

– Pfad: Ext P1 ... Pn Ext kann komprimiert werden

Löse lokale Konflikte lokal

Tausche Information über lokale Abhängigkeiten mit entfernten Komponenten aus


Verteilter Abhängigkeitsgraph

ProcessOne

ProcessTwo

l1

l2

Ext Ext

l1 ProcessOne

ProcessTwo


Abgeglichener Abhängigkeitsgraph

ProcessOne

ProcessTwo

l1

l2

ProcessOne

ProcessTwo

l1

l2

Ext Ext


Bewertung

Vorteile– Verteilter Algorithmus – kein Bottleneck

Nachteil– Viel Verkehr– Phantomdeadlocks möglich


Testnachrichten

Kein expliziter Abhängigkeitsgraph

Spezielle Nachrichten– Blockiert ein Prozess wird eine Nachricht gesendet– Erkennen von Deadlocks anhand der Nachrichten, die den Prozess

erreichen

Unterscheidung bezüglich Nachrichtenempfänger– Echobasiert – Senden an alle Nachbarn– Ahängigkeitsbasiert – Senden an den Halter des Locks auf den wir

warten


Echobasierte Testnachrichten

Echo Algorithmus:– Initial: sende Echo (mit eindeutiger Id) an alle Nachbarn, – Empfang von Echo Nachricht:

• sende an alle Nachbarn, außer an den Sender

• ignoriere weitere Echo Nachrichten mit gleicher Id

• wenn kein entsprechender Nachbar mehr vorhanden, sende Echo Antwort an Sender

– Empfang von Echo Antwort: sende Echo Antwort an Sender der Echo Nachricht

Idee: Deadlockinfo aus Echoantwort

Overkill! Nur sinnvoll, wenn Echo aus anderen Gründen sowieso implementiert ist (z.B. zur Hardwarekontrolle)


Abhängigkeitsbasierte Testnachrichten

Kein expliziter Abhängigkeitsgraph

Spezielle Nachrichten– Blockiert ein Prozess wird eine Nachricht an den Halter des Locks

gesendet– Ist der auch blockiert, leitet er die Nachricht weiter an die Halter der

Locks auf die er wartet etc.– Kommt die initiierte Nachricht zum Sender zurück ist ein Zyklus

erkannt

Erkennen von Phantomdeadlocks möglich– Ignoriere Nachrichten über nicht (mehr) aquirierte Locks– Weitersenden nur beim Blockieren und Halten der Locks





//ProcessTwo.probe(l2);

doSome();


}}



//ProcessOne.probe(l1);

doSome();


}}


ProcessTwo sendet Abhängigkeit




doSome();


}}




doSome();


}}


Phantom deadlock

ProcessOne

ProcessTwo

l1

l2

probe(l1)

probe(l2)






doSome();


}}




doSome();


}}


Abhängigkeitsgraph Beispiel - deadlock

ProcessOne

ProcessTwo

l1

l2

probe(l1)

probe(l2)

resendProbe(l1)

resendProbe(l2)


Bewertung

Vorteile– Verteilter Algorithmus – kein Bottleneck– keine Phantomdeadlocks– kein expliziter Aufbau des Abhängigkeitsgraphen

Nachteil– Viel Verkehr– Phantomdeadlocks bei alternativen Locks

• warten auf Lock1 oder Lock2

• dann effizient beim Erkennen dieser


Globale Zustandserkennung

Idee:– konstruiere ein konsistentes Bild des verteilten Systemzustandes

(Abhängigkeitsgraph)– Erkenne Zyklen auf diesem konsistenten Abhängigkeitsgraphen

Lösungen– Mehrere Phasen (Runden) oder Indirektionen– Locking oder Markierung der Nachrichten mit Phasen Ids

Ein Vertreter– Lockverwaltung


Lockverwaltung

Jedes Objekt ist durch einen Lock (oder mehrere) geschützt

Aquirierung über Objekte

Abgabe der Kontrolle der Locks eines Objekts an das aquirierende Objekt

Aquisitionsbaum

Anfragen immer über Wurzel des Aquisitionsbaum

Dadurch relevanter Teil des Abhängigkeitsgraphen


Beispiel

aquire lock

give upcontrol


Deadlock Situation


Anfrage über Lockverwalter


Bewertung

Vorteile– Verteilter Algorithmus – kein Bottleneck– keine Pantomdeadlocks

Nachteil– Viel Verkehr– Viel Verwaltung


Fazit

Deadlockvermeidung ist besser als Deadlockerkennung

Deadlockvermeidung– Spezifikation der Komponenten– u.U. Handbeweise vom Komponentenzusammensetzer

Deadlockerkennung– Laufzeitprobleme– u.U. Phantomdeadlocks– Was tun, wenn Deadlock erkannt wurde?

• Kann nicht geraten werden

• Spezifikation (Exceptionprogrammierung) durch Komponentenentwererfer

Documents

Dr. Welf Löwe und Markus Noga1 Gliederung: Teil 3 - Anpassungen 1. Einführung –Motivation –Definition, –Konzepte für Komponenten (klassische, kommerzielle,