S Synchronisation und Koordination - lsw.ee.hm.edulsw.ee.hm.edu/~tasin/vorlesung_vs/paul/Verteilte_Systeme_S.pdf · Dies impliziert Verklemmungs-Freiheit (engl.: deadlock free) und

Verteilte Systeme Synchronisation und Koordination Prof.Dr.Rainer Seck V1.3 Seite 1 von 58

S Synchronisation und Koordination

In diesem Kapitel werden wesentliche Verfahren und Algorithmen eingeführt, die der Synchronisation und

Koordination von verteilten Prozessen dienen. Randbedingungen: • Die relevante Information ist über mehrere Maschinen verteilt. • Entscheidungen werden auf lokalen, eventuell unvollständigen Informationen gefällt. • Das verteilte System arbeitet mit nebenläufigen Prozessen ohne gemeinsamen Adreßraum. • Ein Single-Point-of-Failure sollte vermieden werden. • Es gibt keine gemeinsame Zeitbasis.


S.2 Heartbeat-Algorithmen In vielen Anwendungen verteilter Systeme müssen mehrere Prozesse gemeinsam eine Aufgabe erfüllen. Randbedingungen und Aufgabe • die Prozesse erledigen jeweils eine Teilaufgabe und • können nur mit ihren direkten Nachbarn kommunizieren. • Es besteht keine voll vermaschte Kommunikationstopologie - aus Gründen der Netzwerktopologie, oder - weil weit entfernte Teilnehmer dem lokalen Prozeß nicht bekannt sind. • Alle Prozesse sind in der Lage, das globale Endergebnis zur Verfügung zu stellen. Klasse von verteilten Algorithmen, die dieses Problem löst, sind die Heartbeat-Algorithmen. • Heartbeat-Algorithmen arbeiten in zwei Phasen - Expansionsphase: senden von Information zu den nächsten Nachbarn - Kontraktionsphase: neue Information von Nachbarn einsammeln. • Nach lokaler Verarbeitung der erhaltenen Information wiederholt sich dies in Runden, bis das Gesamtergebnis

berechnet ist.


Basisalgorithmus info_0 := local_information; repeat send (neighbour_1, info_0); … send (neighbour_N, info_0); receive (neighbour_1, info_1); … receive (neighbour_N, info_N); info_0 := F(info_0,…, info_N); until (termination_condition); Manchmal ist es zusätzlich notwendig, daß alle Prozesse die Runden immer im gleichen Raster ausführen. Anwendungen: u.A. paralleles Sortieren, Matrizenberechnungen, Bildverarbeitung


S.2.1 Beispiel: Bestimmung der Netzwerktopologie

Annahmen: • alle Prozesse kennen zunächst nur ihre direkten Nachbarn • die Nachbarschaftsrelationen zwischen den Prozessen sind symmetrisch (Verkehr bidirektional) • die Topologie ist statisch für die Dauer der Bestimmung der Netzwerktopologie • die Nachbarn eines Prozesses werden in einem booleschen Array der Länge n abgelegt Ergebnis: die Topologie des Netzes in einer Adjazenzmatrix (Verbindungsmatrix) 1. Idee: zentraler Sammelprozeß Ein dedizierter Prozeß sammelt von allen Prozessen deren Nachbarschaftsinformation ein und erstellt daraus

lokal die Adjazenzmatrix. Bewertung: Es wird impliziert, daß der Sammelprozeß mit allen anderen kommunizieren kann sehr

asymmetrische Lösung dar. è Verteilung des Ergebnisses? 2. Idee: verteilter Heartbeat-Algorithmus è symmetrischer Heartbeat-Algorithmus:

• Alle gleichzeitig(Trigger?): Man fragt seinen Nachbarn und erhält dessen Information. • In der zweiten Runde erfährt man die Information der übernächsten Nachbarn usw. • Nach maximal D Runden (D = Durchmesser des Netzes) hat jeder Teilnehmer das Endergebnis.


Algorithmus für einen beteiligten Prozeß P var neighbours [1..n] : boolean; topology [1..n, 1..n] : boolean; new_topology [1..n, 1..n] : boolean; r : integer := 0; ∀ Q ∈ (neighbour of P) neighbours [Q] := true; topology [P, 1..n] := neighbours; while r<D do ∀Q: (neighbours [Q]= true) send (Q, topology); ∀Q: (neighbours [Q]= true) [ receive (Q, new_topology); topology := topology OR new_topology; ] r := r + 1; endwhile;

Beispiel:

Topologie: p1-p2-p3-p4 è in p1 Beobachter è sendet seine Matrix , D=3 è p1->p2->p3->p4 è nach D = 3 Iterationen hat p4 die Matrix von p1 è jeder Prozess läuft 'blind' D mal in der Interationsschleife!


Bewertung

• Nachteil: zur Terminierung muss zunächst der Durchmesser D des Netzwerkes bekannt sein • Nachteil: hoher Kommunikationsaufwand - Anzahl der Nachrichten ist nach oben beschränkt durch AnzMax <= n · m · D (n = Anzahl Prozesse, m = Wost case: maximale Anzahl Nachbarn) • Verbesserung: Anpassung auf unbekannte Netzwerkdurchmesser möglich è Sobald in einer Reihe der topology Matrix ein true-Wert steht, ändert sich da nichts mehr è Ende wenn mindestes ein true-Wert in jeder Reihe


S.3 Probe/Echo-Algorithmen

• weitere Klasse von Algorithmen zur verteilten Lösung eines Gesamtproblems in vorher beschriebenen Szenarien

• Probe/Echo-Algorithmen realisieren einen virtuellen Broadcast Idee des Basisalgorithmus • Initiator schickt eine PROBE an alle seine ihm bekannten direkten Nachbarn und verhält sich anschießend so

wie ein Prozeß der einmalig seine PROBES verschickt hat. Besonderheit: Der Initiator hält zuletzt die Gesamtinformation in Form aller ECHOS. è Ergebnis: Spannbaum

• Jeder der erstmalig eine PROBE empfängt merkt sich diesen als ersten PROBE-Sender und versendet dann einmalig je eine PROBE an alle weiteren Nachbarn.

• Nachdem einmalig in einem Prozeß PROBEs versandt wurden, wird auf ECHOs oder weitere PROBEs

gewartet. Der Prozeß beendet das Warten, verschickt sein ECHO an den Nachbarn, von dem er die erste PROBE erhalten hat und beendet den Algorithmus wenn: die Summe der ECHOs und weiteren empfangenen PROBES gleich der Anzahl der Nachbarn ist, an die der Prozeß einmalig seine PROBEs verschickt hat.

• Hat ein Empfänger einer PROBE keine weiteren Nachbarn, so schickt er sein 'persönliches' ECHO an den Nachbarn, von dem er die erste PROBE erhalten hat und beendet den Algorithmus.

• Erhält ein Empfänger ein beliebiges ECHO, reicht er dieses ECHO unverändert an seinen ersten PROBE-Sender weiter.

è Das Vorgehen entspricht der klassischen Tiefensuche in Graphen. è Inhalt eines ECHOs: Verbindung Sender-Empfänger


S.4 Election-Algorithmen In einem verteilten System wird oft ein ausgezeichneter Prozeß als Koordinator benötigt. Fragestellung: • Wie ist dieser zu bestimmen? Anwendungsbeispiele: • wechselseitiger Ausschluß • Ausfall eines vorhergehenden Koordinators Klasse der Algorithmen nennt man Election-Algorithmen. Election ist dabei meist eine Bestimmung eines Extremwertes auf einer Ordnung von beteiligten Prozessen.


S.4.1 Bully-Algorithmus einfacher Election-Algorithmus von Garcia-Molina Annahmen: • alle Prozesse haben eine eindeutige Identifikation ('Prozeßnummer') • die Identifikation aller anderen Prozesse ist bekannt • die Identifikatoren lassen sich ordnen • es ist den Prozessen nicht bekannt, ob ein anderer Prozeß noch aktiv oder ausgefallen ist • Nach Anwendung des Algorithmus ist der Prozeß mit der 'numerisch höchsten' Identifikation der Koordinator Ziel: • bei Ausfall des bisherigen Koordinators, denjenigen Prozeß zu finden, der noch aktiv ist und den 'höchsten'

Identifikator trägt • dieser wird dann als neuer Koordinator eingesetzt Idee des Algorithmus: • Ein Prozeß P, der den Ausfall des Koordinators bemerkt, schickt ELECTION an alle Prozesse mit höherem

Identifikator. • Geht eine Antwort (OK) ein, wartet P auf die Nachricht des endgültig gewählten, neuen Koordinators. • Falls keine Antwort eingeht, dann ist wohl keiner der Prozesse mit höherem Identifikator verfügbar und P

damit selbst der Gewählte. • Dann schickt P die Nachricht COORDINATOR an alle restlichen Prozesse.


Algorithmus • P bemerkt, daß der Koordinator nicht mehr antwortet und fordert alle potentiellen 'höheren' Identifikatoren Id(Q) > Id(P) auf die Koordinatorenrolle zu übernehmen: ∀Q: (Id(Q) > Id(P)) send (Q, ELECTION); /*...warten auf OK oder ELECTION siehe auch# */ if ∃Q: (receive (Q, OK)) then do_something_else; else /*TIMEOUT*/ ∀Q: (Id(Q) < Id(P)) send(Q, COORDINATOR); endif; • #: P empfängt ELECTION, gesendet von Prozeß A ∀Q: (Id(Q) > Id(P)) send(Q, ELECTION); send (A, OK); /* id(A) < id(P) !! */

è Startet ein ausgefallener Prozeß wieder neu, veranlaßt er eine Election. Dadurch bleibt der Prozeß mit dem höchsten Identifikator immer der Koordinator. Ist der ausgefallene Prozeß der mit der 'höchsten' Nummer, so sendet er einfach eine COORIDINATOR-Nachricht an alle.

Nachteile: • hohe Nachrichtenkomplexität è im schlechtesten Fall O(n2) Nachrichten. èim besten Fall (n - 2) Nachrichten • alle Prozesse mit ihren Identifikatoren müssen allen bekannt sein


Bild S.7 Bully - Algorithmus


S.5 Schnappschüsse Für viele Problemstellungen in verteilten Systemen ist es notwendig, den globalen Zustand des Systems zu

kennen. Definition: Globaler Zustand Der globale Zustand eines verteilten Systems besteht aus den loka len Zuständen aller Prozesse und allen

unterwegs befindlichen Nachrichten. Einen globalen Zustand festzuhalten, heißt Schnappschuß Ausgangssituation: • keine globale Zeit zur Verfügung • System darf für den Schnappschuß nicht angehalten werden Prinzip eines Schnappschusses: • Schnittbildung durch das Zeitdiagramm aller Ereignisse die Zustandsinformationen wird bei den einzelnen Prozessen zu beliebigen physikalischen Zeitpunkten abgeholt, daraus folgen: • konsistente Schnitte • inkonsistente Schnitte


a) konsistenter Schnitt

b) äquivalente Berechnung nach „Gummibandtransformation”


c) inkonsistenter Schnitt

d) nach „Gummibandtransformation”: Nachricht aus der Zukunft Bild S.17 Schnitte im Zeitdiagramm


Merkmal inkonsistenter Schnitte: • eine Nachricht wird nach Festhalten des Zustands bei einem Prozeß losgeschickt und von einem anderen

Prozeß vor dessen Zustandserfassung empfangen • „Nachricht aus der Zukunft“ verletzt die Kausalität Begriffe konsistenter Schnitt und konsistenter Zustand werden äquivalent benutzt


Algorithmus, der konsistente globale Zustände festhält (Chandy und Lamport) Definition: Lokaler Zustand Der lokale Zustand ist die Historie der Ereignisse nach der Happened-before-Relation. Definition: Schnitt Ein Schnitt c der Ereignismenge E ist eine Partitionierung von E in die Mengen Pc und Fc (Past / Future). Ein Schnitt c ist konsistent, wenn für e∈Pc mit e’→e gilt, daß e’∈Pc, und

wenn für e∈Fc mit e→e’ gilt, daß e’∈Fc,

d.h. c ist abgeschlossen unter der Happened-before-Relation.


Algorithmus: • Alle Prozesse und die Basisnachrichten kennen zwei Zustände (schwarz/rot) • schwarz: vor dem Schnappschuß • rot: nach dem Schnappschuß • Start - Schnappschuß-Initiator markiert sich rot und - sendet eine Schnappschuß-Aufforderung an alle Prozesse • Ein Prozeß erhält eine Schnappschuß-Aufforderung - Prozeß markiert sich rot und - sendet eine Kopie seines momentanen lokalen Zustands an den Initiator - ab diesem Zeitpunkt sendet er nur noch rote Basisnachrichten • Prozeß ist schwarz markiert und erhält eine rote Basisnachricht - Dies entspricht dem Erhalt einer Nachricht aus der Zukunft. - zwei Verhaltensmöglichkeiten: - Die Bearbeitung der Nachricht wird verzögert, bis die tatsächliche Schnappschuß-Aufforderung eintrifft. - Prozeß markiert sich vorzeitig rot und schickt seinen lokalen Zustand • Behandlung unterwegs befindlicher Basisnachrichten - Rote Prozesse senden Informationen über eingehende schwarze Basisnachrichten nachträglich an den

Initiator -Problem: wann ist die letzte schwarze Nachricht eingetroffen -Lösung: Prozesse übermitteln mit ihrem lokalen Zustand Zählerstände ihrer empfangenen und

abgeschickten schwarzen Nachrichten


Bild S.18 Schnappschußprinzip


S.6 Verteilter wechselseitiger Ausschluß Systeme, die aus mehreren Prozessen bestehen, müssen häufig auf gemeinsame Daten oder Ressourcen zugreifen. Konsistenzwahrung: • kritische Regionen • wechselseitiger Ausschluß beim Zugriff In Einprozessor-Systemen: • Semaphore • Monitore, ... Im verteilten System nicht möglich: • kein gemeinsamer Speicher • keine gemeinsamen Variablen

Ziel: Verfahren, die verteilt kritische Regionen verwalten können


Anforderungen an wechselseitigen Ausschluß: • Sicherheit (engl.: safety) è Höchstens ein Prozeß darf sich in der kritischen Region befinden. • Lebendigkeit (engl.: liveness) è Ein Prozeß, der den Eintritt in die kritische Region beantragt, darf auf jeden

Fall irgendwann eintreten. Dies impliziert Verklemmungs-Freiheit (engl.: deadlock free) und kein Verhungern (engl.: starvation) der Prozesse.

zusätzlich oft folgende Forderung: • Ordnung (engl.: ordering) è Ein Eintritt in die kritische Region erfolgt nach der Happened-before-Relation. èD.h.: Falls ein Prozeß PX, der auf den Eintritt in die kritische Region wartet, eine Nachricht an einen

anderen Prozeß PY schickt, der daraufhin ebenfalls in die kritische Region will, dann darf der Sendeprozeß PX vor dem Empfangsprozeß PY in die kritische Region.


S.6.1 Ein zentralisierter Algorithmus zentraler Koordinationsprozess bzw. -Server verwaltet den Zugriff auf die Ressourcen und damit den

wechselseitigen Ausschluß Idee: • die Klienten schicken eine Anfrage für den Zugriff auf eine Ressource an den Server:

• ist die gewünschte Ressource frei, gibt der Server die Erlaubnis zum Zugriff • ansonsten wird die Anfrage in eine Warteschlange gelegt und nach Freiwerden der Ressource behandelt

Algorithmus beim Anforderer Px:

• Es sei S der zentrale Verwalter der Zugriffsberechtigung .... send (S, request); /*..warten auf Zutrittsberechtigung...*/ receive (S, grant); /*... geschützte critical region */ /*..freigeben der Zutrittberechtigung*/ send (S, release);


Bild S.10 Zentralisierter wechselseitiger Ausschluß Aufwertende Alternative: • Um das blockierende Warten bei Px zu vermeiden, wenn bereits ein Anderer Zugang hat, schickt der

Verwalter permission_denied è a) kein Warteschlageneintrag, Px wiederholt Anfrage b) Warteschlangeneintrag, Px pollt immer wieder ob grant erteilt

• Der Verwalter schickt das grant nicht selbs als Quittung, sondern Px ruft die Antwort extra ab (Polling)


Bewertung: • die Basisbedingungen Sicherheit und Lebendigkeit sind erfüllt • Fairness in Bezug auf die Zugriffsreihenfolge • Aber: ordering nach Happened-before-Relation ist nicht gewährleistet Vorteile: • einfachen realisierbar • Nachrichtenkomplexität: maximal drei Nachrichten für den Eintritt Nachteile: • zentralisierter Algorithmus: single-point-of-failure - Server kann abgestürzt sein, d.h. Klient weiss nicht, ob er noch auf die Zusage für den kritischen Abschnitt

warten muß. • Ausfall eines Klienten innerhalb des kritischen Abschnitts oder der Verlust von Nachrichten kann zu einem

Deadlock führen


S.7 Transaktionen Der bereits besprochene wechselseitige Ausschlusses befindet sich auf einer systemnahen Abstraktionsebene. wünschenswert: • atomare Operationen oder Transaktionen „abstrakt“ zur Verfügung stellen, ohne daß die

Synchronisationsproblematik sichtbar wird. Beispiel: Auftrag 1: A = A + 3; Auftrag 2: A = A + 5; Lies von Server A Lies A Lokal A := A+5 Schreibe neuen Stand Lokal A:= A +3 Schreibe neuen Stand Lokal: Ausgabe A ; Lokal Ausgabe A; Bild S.14 Fehlerhafter Ablauf zweier Bankaufträge • Synchronisation der Bearbeitung der beiden Aufträge notwendig. Lösung: è zusammengehörige Operationen zu einer Sequenz zusammenfassen, die nach außen als eine geschlossene

Einheit wirkt.

Begriff: Transaktion.


ACID-Eigenschaften einer Transaktion • Atomarität (engl.: Atomicity) çè entweder alle oder keine der Operationen einer Sequenz ausführen a) eine Transaktion ist erfolgreich (Commit) –damit sind alle Operationn einer Sequenz gültig- b) eine Transaktion ist nicht erfolgreich (Abort) - keine der Operationen wurde ausgeführt - - Zwischenzustände innerhalb einer Sequenz von Operationen sind nie nach außen sichtbar • Konsistenz (engl.: Consistency) çèTransaktion überführt System von einem konsistenten Zustand in einen anderen - Während der Ausführung können lokal inkonsistente Zustände durchlaufen werden, die aber nie nach außen

sichtbar sein dürfen • Serialisierbarkeit (engl.: Isolation) çè Eine noch nicht abgeschlossene Transaktion gibt auch intern ihre Resultate nicht an andere

Transaktionen weiter vor ihrer Beendigung è die nebenläufige Ausführung von Transaktionsaufträgen wird serialisiert und ist identisch mit einer

seriellen Ausführung • Dauerhaftigkeit (engl.: Durability) çè dauerhafte Persistenz. Wenn die Transaktion erfolgreich beendet wurde, sind die Ergebnisse dauerhaft

gespeichert, auch bei nach der abgeschlossenen Transaktion darauffolgenden Systemfehlern/Systemabstürzen.


Bei mehreren verteilt ablaufenden Transaktionen –auf unterschiedlichen Objekten- können die Teiloperationen der verschiedenen Transaktionen zeilich parallel (unterschiedliche Kästchenfarbe) aber je in sich (gleiche Kästchenfarbe) seriell ablaufen

Bild S.15 Synchronisation durch Serialisierung und Verschränkung von Operationen


S.7.1 Basisprimitive für Transaktionen BeginTransaction (Tid); -- Tid = transaction identifier EndTransaction (Tid); Read (Tid, Parameter); Write (Tid, Parameter); Commit (Tid); Abort (Tid); geschachtelte Transaktionen (engl.: nested transactions): è innerhalb einer Transaktion werden weitere Transaktionen aufgerufen, diese werden erst nach Abschluß der gesamten Transaktion nach außen sichtbar Recovery:

• Wird eine Transaktion mit Abort oder durch einen Fehler abgebrochen, muß das System automatisch wieder auf den konsistenten Zustand vor dem Aufruf der Transaktion gebracht werden d.h.: èAlle bis zu diesem Zeitpunkt bereits ausgeführten Teiloperationen müssen wieder rückgängig gemacht werden.

• Bei verschachtelten Transaktionen müssen auch die bereits mit commit abgeschlossenen ‚inneren’ Transaktionen wieder zurückgenommem werden!

Fehlermöglichkeiten: • Abbruch einer Transaktion • Prozeßabsturz • Plattencrash


S.7.2 Implementierungsaspekte Transaktionen impementiert durch privater Arbeitsbereich • Prozeß startet eine Transaktion. Er erhält vor jeder (Teil-)Transaktion eine Schattenkopie aller benötigten

Objekte und arbeitet auf der Kopie: • bei einem Abort muß lediglich die Kopie gelöscht werden • bei (insgesamten) Commit wird das Original atomar durch die Kopie überschrieben

• bei geschachtelten Transaktionen entsteht bei diesem Konzept quasi ein Stack von Kopien, der bei einem Gelingen der gesamten Transaktion atomar über das Original geschrieben wird.

è dies entspricht einem pessimistischen Vorgehen • sinnvoll, wenn Transaktionen oft fehlschlagen • Nachteil: - besonders im geschachtelten Fall hoher Speicherplatzaufwand • optimierte Varianten unterscheiden Lese- und Schreibzugriffe und verwenden Einstiegszeiger in

Speicherbereiche, um unnötiges Kopieren zu vermeiden.


Transaktionen impementiert durch sog. Intentionenliste • vor allen Teiloperationen einer Transaktion werden der alte Wert eines Objektes und der neue Wert eines

Objektes in einer seperaten Logdatei (engl.: writeahead log) mitgeschrieben. Zwei Implemetierungsvarianten:

optimistische Variante „Update-in-place“ • Write Der Schreibzugriff erfolgt direkt auf den echten Daten. Es wird ein UNDO-Satz in der Logdatei gespeichert. • Read Es können direkt die echten Daten gelesen werden. Die Logdatei bleibt unverändert. • Commit Es genügt, die UNDO-Sätze dieser Transaktion in der Logdatei zu löschen. • Abort Alle ausgeführten Änderungen der Daten müssen unter Verwendung der UNDO-Sätze zurückgenommen

werden.


pessimistische Variante „Deferred-update“ • Write Es erfolgt die Speicherung eines REDO-Satzes, wobei die echten Daten unverändert bleiben. • Read Der aktuelle Wert muß aus den REDO-Listen und den echten Daten ermittelt werden. • Commit Alle Änderungen müssen unter Verwendung der REDO-Sätze nachvollzogen werden. • Abort Es genügt, die REDO-Sätze der Transaktion zu löschen. Bewertung Die optimistische Variante favorisiert man, wenn die Wahrscheinlichkeit eines Abort deutlich geringer ist, als

die eines Commit. Für die pessimistische Variante sollten die Wahrscheinlichkeiten umgekehrt verteilt sein.


S.7.3 Zwei-Phasen-Commit-Protokoll Ausgangspunkt: • Im verteilten System greifen Transaktionen auf Daten zu, die über mehrere Rechner verteilt sind und von

mehreren Prozessen verwaltet werden. • Das Commit einer Transaktion muß jedoch atomar unter allen beteiligten Prozessen ablaufen Algorithmus, der i.d.R. eine verteilte Transaktion beendet, ist das Zwei-Phasen-Commit-Protokoll: • Jeder Prozeß entscheidet dabei zunächst, ob er für seine eigene Teiloperation Commit oder Abort

ausführen will • Dann einigen sich über einen Koordinator alle Prozesse über ein Gesamtergebnis • Ist unter den Prozessen mindestens einer, der sich für Abort entschieden hat, so ist auch das

Gesamtergebnis Abort und alle Teiloperationen müssen rückgängig gemacht werden • Andernfalls können alle das finale Commit ausführen.


Zwei-Phasen-Commit-Protokoll: • Abstimmungsphase (engl.: voting phase) - Der Koordinator schickt CanCommit? an alle Teilnehmer. -Jeder Teilnehmer entscheidet sich für ein Ergebnis und schickt entsprechend Yes oder No zum Koordinator

zurück. • Abschlußphase (engl.: completion phase) -Der Koordinator sammelt die Abstimmungsergebnisse ein und entscheidet. -Basierend auf dem Gesamtergebnis schickt der Koordinator dann an alle Teilnehmer DoCommit oder

DoAbort . - Im Falle einer Aufforderung zum DoCommit schicken die Teilnehmer als Quittung HaveCommitted

zum Koordinator. Nachteil: • blockierendes Protokoll und ggf. nicht eineindeutig im Ausgang wenn: 1. z.B. DoCommit verschickt

wurde, aber die Quittung HaveCommitted eines Teilnehmer nicht ankam è Was tun? è Problem der Quittung der Quittung der Quittung....

Abschwächung Blockierung: • man setzt das Gesamtergebnis frühzeitig auf Abort, falls nach einer gewissen Zeit noch nicht alle

Antworten eingegangen sind


S.7.4 Kontrolle nebenläufiger Zugriffe während einer Transaktion auf die beteiligten Objekte Ausgangspunkt: • mehrere Transaktionen laufen gleichzeitig und verschränkt ab • sie sollen sich nicht gegenseitig bei der Verwendung von Objekten stören Pessimistische Kontrollverfahren èZwei-Phasen-Sperrprotokoll (engl.: two phase locking) • Anforderungsphase (engl.: growing phase) Werden Datenobjekte für eine Transaktion benötigt, werden diese nacheinander für den weiteren Verlauf

gesperrt. • Freigabephase (engl.: shrinking phase) Werden die Objekte nicht mehr benötigt, werden die Sperren freigegeben. • Variante 1: - entgegen der Reihenfolge bei der Sperrung der Objekte, werden alle nicht mehr benötigten Objekte wieder

freigegeben - die Änderungen auf diesen Objekten sind dann bereits für andere sichtbar, bevor die Transaktion beendet

ist, verletzt zunächst das Prinzip: atomar aber: - arbeiten andere Transaktionen mit diesen Daten und es erfolgt ein Abort der vorigen Transaktion,

müssen auch die anderen Transaktionen Abort durchführen Konsequenz: es können Abort-Kaskaden entstehen • Variante 2: - Alle gesperrten Objekte einer Transaktion werden erst nach deren Commit wieder freigegeben - vermeidet Abort-Kaskaden, blockiert Objekte aber lange


Bild S.16 Zwei-Phasen-Sperren


Das Zwei-Phasen-Sperrprotokoll ist nicht verklemmungsfrei, Beispiel: T1 und T2 wollen beide auf die Objekte A und B zugreifen

Ablaufvariante 1 1. T2 sperrt A als erster 2. T1 will auch auf A zugreifen und wartet, da A

gesperrt ist 3. T2 sperrt dann B 4. wenn T2 komplett beendet ist, macht T1

weiter, sperrt also A èes findet eine Serialisierung statt

Ablaufvariante 2 1. T1 sperrt zuerst A

2. T2 sperrt dann B

èbeide warten nun auf die Zugriffsmöglichkeit des jeweils ande ren Objekts und blockieren sich deshalb gegenseitig für immer

Vermeidung der Verklemmung • Ordnung auf Objektsperren einführen • alle benötigten Objekte in dieser Reihenfolge am Anfang der Transaktion komplett sperren • falls bereits ein Teil der benötigten Objekte von anderen Transaktionen gesperrt ist, wird nichts gesperrt und

man muß warten Auflösen bestehender Verklemmungen • es ist notwendig, den verteilten Zustand des Systems zu kennen • dann läßt sich eine Verklemmung anhand von Zyklen im Wait-for-Graphen erkennen Bewertung: • potentielle Nebenläufigkeit wird oft verhindert


Optimistische Kontrollverfahren Verfahren von Kung und Robinson • alle Transaktionen arbeiten ohne Sperren mit eigenen Kopien der Objekte • soll ein Commit ausgeführt werden, wird erst zu diesem Zeitpunkt auf Zugriffskonflikte geprüft • trat ein Konflikt auf, so gewinnt die Transaktion, die zuerst fertig ist • dadurch werden kurze, schnelle Transaktionen bevorzugt • der Verlierer verwirft seine Kopien und beginnt erneut. Bewertung: • parallele Arbeit bei verschränkter Benutzung mehrerer Objekten • Verfahren ist verklemmungsfrei • mit privaten Arbeitsbereichen leicht implementierbar.


S.8 Verteilte Terminierung In einem Einzelprozessorsystem: • feststellen, ob alle Prozesse blockiert oder terminiert sind und keine Ein-/Ausgabeoperationen mehr anstehen Im verteilten System: • noch unterwegs befindliche Nachrichten können das System wieder anstoßen, • obwohl bereits alle Prozesse die Kriterien des lokalen Falls erfüllen Definition: global terminiertes System • Ein Prozeß wird als idle bezeichnet, falls er terminiert ist, oder auf eine Nachricht wartet. • Ein verteiltes System ist global terminiert, wenn alle Prozesse idle und keine Nachrichten mehr unterwegs

sind.


S.8.1 Verteilte Terminierung im Ring Annahmen: • Jeder Prozeß kommuniziert nur mit seinem direktem nächsten Nachbarn und ist entweder aktiv oder idle • Initialisiert wird jeder Prozeß als aktiv (rot), es gibt einen token Initiator P[0] • Ein Prozeß wird idle (schwarz), falls er terminiert oder auf eine Nachricht wartet • Empfängt ein Prozeß im Zustand idle eine Basisnachricht, wird er wieder aktiv. • Empfängt ein Prozeß im Zustand aktiv ein token so schickt er ihn erst mit dem Wechsel nach idle weiter • Alle Prozesse sind in einem logischen Ring angeordnet; ein token kann eine Basisnachricht nicht überholen Algorithmus: • P[0] wird zum ersten Mal idle, setzt sich idle und schickt seinen token an den nächsten Nachbarn colour[0] := black; send (P[1], token); • P[i], i∈{0..n}, erhält eine Basisnachricht, verlässt ggf. idle und wird aktiv colour[i] := red; • P[i], i∈{1..n} wartet auf Basisnachricht und erhält ein Token, bleibt idle und schickt token weiter colour[i] := black; send (P[(i+1) mod n], token); • P[0] erhält zum Schluß wieder sein Token if (colour[0] = black) then global_termination; else colour[0] := black; send (P[1], token); endif;


Bild S.19 Tokenring-Algorithmus zur Terminierungserkennung


S.9 Verklemmungen in verteilten Systemen Eine Verklemmung (engl.: deadlock) entsteht, wenn zwei Prozesse gegenseitig auf die Freigabe einer jeweils

vom anderen gehaltenen Ressource warten drei Strategien: • Erkennung (engl.: detection) Aufgetretene Verklemmungen werden erkannt und dann eventuell aufgelöst. • Vorbeugung (engl.: prevention) Die programmtechnische Struktur verhindert generell, daß Verklemmungen auftreten können. • Verhinderung (engl.: avoidance) Eine systemseitige Verteilung der Ressourcen verhindert Verklemmungen. lokaler Fall: • relativ einfach - das Betriebssystem hat Kenntnis über alle Prozesse - verwaltet die Ressourcen verteilter Fall: • ähnliche Problematik wie die Erkennung der globalen Terminierung • globaler Zustand ist zu ermitteln


S.9.1 Erkennen von Verklemmungen Aufgabe: • Erstellen eines rechnerübergreifenden Prozeß-Ressource-Graphen (Wait-for-Graph) • Zyklus = Verklemmung • Aufspüren von Zyklen im Wait-for-Graph Randbedingungen: • bei Prozessen muß einer davon terminiert werden • bei Transaktionen wird eine davon abgebrochen - durch die Alles-oder-Nichts-Semantik von Transaktionen ergibt sich lediglich ein Zeitverlust • ein Abstimmungsverfahren (engl.: voting) legt fest, welcher Prozeß oder Transaktion terminiert werden soll Zentralisierte Erkennung von Verklemmungen • jeder Computer verwaltet einen eigenen Prozeß-Ressource-Graphen • jede Änderung einer Kante am Graphen wird einem zentralen Koordinator mitgeteilt • dieser setzt bei sich aus allen Einzelgraphen einen Gesamtgraphen zusammen und kann so Zyklen und damit

Verklemmungen erkennen


Bild S.21 Zentralisierte Erkennung von Verklemmungen èSzenario: B gibt R frei, A erhält R.... èSzenario: B gibt R frei aber Freigabenachricht R des Rechners 1 wird verzögert an Koordinator überstellt, währenddessen will B T haben und die Rechner 2 Nachricht der T Anforderung erreicht Koordinator vor Freigabenachricht R des Rechners 1 è Zyklus im Graphen aber: false Deadlock Problem: Es können falsche Verklemmung (engl.: false deadlock) entstehen

Resource


Verteilte Erkennung von Verklemmungen Chandy-Misra-Haas Algorithmus: • immer dann starten, falls ein Prozeß (blockierter Prozeß) auf eine Ressource warten muß • dem ressourcehaltenden Prozeß wird eine Nachricht geschickt der Form <blockierter Prozeß, sendender Prozeß, empfangender Prozeß>. • blockiert der Empfänger ebenfalls, ändert er Feld 2 und 3 und schickt die Nachricht weiter • läuft die Nachricht wieder beim blockierenden Prozeß ein, so erkennt er sich selbst in Feld 1 und es gibt

einen Zyklus und damit eine Verklemmung

Bild S.22 Chandy-Misra-Haas Algorithmus


Auflösung der Verklemmung: • am einfachsten durch Terminierung des Initiators • bei mehreren Initiatoren führt dies u.U. zu mehr Terminierungen, als notwendig Algorithmus-Variante: • alle Prozesse hängen ihre Identifikation an die Nachricht an. • erkennt der Initiator seine führende Identifikation, bestimmt er einen Prozeß und • bittet ihn zu terminieren

S.9.2 Vorbeugung vor Verklemmungen

die Struktur des verteilten Programms soll ausgeschliessen, daß überhaupt Verklemmungen auftreten können allgemeine Techniken: • Jeder Prozeß kann zu einem Zeitpunkt maximal eine Ressource halten. • Die Prozesse müssen alle benötigten Ressourcen bereits zur Initialisierungszeit anfordern. • Alle Prozesse müssen ihre gehaltenen Ressourcen freigeben, bevor sie neue anfordern. • Die Ressourcen erhalten eine Ordnung. - alle Anfragen auf Ressourcen müssen strikt in dieser Ordnung angefordert werden


Algorithmen Annahme: • globale Zeit und ein Transaktionssystem zur Verfügung Wait-Die-Algorithmus: • jede Transaktion bekommt beim Start einen globalen Zeitstempel • ältere Transaktionen warten, bis eine jüngere die gewünschte Ressource wieder freigibt • will eine jüngere Transaktion die von einer alten gehaltene Ressource anfordern, wird sie terminiert. • es können keine Zyklen entstehen, da die Zeitstempel immer aufsteigend geordnet sind • durch die Transaktionssemantik können keine Inkonsistenzen erzeugt werden

Bild S.23 Wait-Die-Algorithmus


Wound-Wait-Algorithmus • wie Wait-Die allerdings • um Folgen von Terminierungen zu vermeiden setzen ältere Transaktionen jüngere zurück, die dadurch die

Resourcen freigibt ( è abort jüngere und restart jüngere) • will eine jüngere Transaktion die von einer alten gehaltene Res- source, so wartet sie anstatt zu terminieren

Bild S.24 Wound-Wait-Algorithmus


S.10 Replikation • Gemeinsames Nutzen von Daten ist ein grundlegendes Ziel verteilter Systeme und Anwendungen • Caching und Replikation gemeinsamer Daten dienen dabei der Effizienzsteigerung, Verfügbarkeit und

Fehlertoleranz. Caching • der Nutzer von Daten hält eine lokale Kopie einer gerade benötigten Ressource, um in der Zukunft schneller

darauf zugreifen zu können • beim nächsten Zugriff ist keine erneute entfernte Anfrage notwendig • welche Daten in den Cache übernommen werden, wird dynamisch zur Laufzeit bestimmt • für die Verdrängung von Daten gibt es viele Ersetzungsalgorithmen (u. a. Least-Recently-Used) Replikation • Daten und Ressourcen werden (bei Servern) mehrfach zur Verfügung gestellt • dies geschieht weitestgehend unabhängig davon, welche Daten gerade momentan von Nutzern benötigt

werden • Replikation ist eine bewußt gesteuerte Informationskopie; Anlage von Replikaten:

• Replikate werden per Nachrichtenaustausch angelegt und auch modifiziert • Im verteilten gemeinsamen virtuellen Speicher werden Speicherobjekte repliziert verwaltet - der Zugriff auf eine Speicheradresse kann von verschiedenen physikalischen Lokationen aus bedient

werden


Anforderungen und Zielsetzungen an Replikationsverfahren: • Effizienzsteigerung è Die Anfragelast verteilt sich auf mehrere Server • Verfügbarkeit è steigt mit Zahl n der Server

p = Verfügbarkeit eines Servers; Verfügbarkeit aller Server: pges= 1- ( 1- p )n

• Fehlertoleranz è Redundanz, da gleiche Information auf mehreren Servern; Ersatz bei Ausfall • Transparenz è Zugriff über logische Adresse durch Nutzer auf Objekte • Konsistenz è Wann gleichen sich die Server untereinander ab? Konsistenz (Kohärenz) und Replikationsmanagement: • Asynchrones Replikationsmanagement

- Klientenanfragen werden immer durch das „lokalste“ Replikat bedient -Aktualisierungen zwischen den Replikaten werden nur periodisch durchgeführt - durch die lokale Bedienung ist immer ein schneller Zugriff gewährleistet - die Replikate sind bei Änderungen inkohärent, bis durch die periodisch durchgeführte Aktualisierung

Kohärenz hergestellt wird -starke Entkopplung zwischen den verschiedenen Replikaten


• Kausal geordnetes Replikationsmanagement -über alle voneinander abhängigen Veränderungen der Replikate wird eine kausale Ordnung erzwungen - dadurch sind, zeitlich gesehen, gemeinsam verwendete Replikate immer kohärent - Replikate, die zur Zeit nur von einem Klienten zugegriffen werden, können inkohärent sein - diese werden dann wie oben periodisch aktualisiert. • Synchrones Replikationsmanagement - Alle Replikate sind immer kohärent - dazu müssen alle Veränderungen total geordnet und atomar auf allen Replikaten durchgeführt werden - für alle Klienten und alle Datenobjekte entsteht die logische Sicht eines jeweils einzelnen Objekts Bewertungen: • Je näher man an das synchrone Modell herangeht, desto aufwändiger wird das Replikationsmanagement • Das Verhältnis zwischen Lese- und Schreibzugriffen ist mit entscheidend für die Wahl.


S.10.1 Replikationsmanagement • es ist nicht immer sinnvoll, alle Daten zu replizieren • nur die häufig benötigten Daten sollten repliziert werden Anlage-Strategien: • Explizite Replikation - Der Klient steuert die Replikation - er legt die Replikate explizit bei mehreren Servern an - beim Zugriff verwendet er eines der Replikate - da die Replikate von einem Klienten angelegt werden, hat auch nur dieser die Kenntnis über sie - die Konsistenzwahrung liegt beim Klienten selbst - andere Klienten können nicht von den Replikaten profitieren • Lazy Replikation - ein Hauptserver wird bei der Erzeugung eines neuen Objekts angesprochen - dieser legt irgendwann später Replikate bei anderen Servern an, ohne daß der Klient davon erfährt - die Konsistenzwahrung liegt beim Hauptserver • Replikation in einer Servergruppe

- per Gruppenkommunikation wird an mehrere Server gleichzeitig die Aufforderung ein Objekt und somit jeweils ein Replikat anzulegen geschickt

- alle Schreibzugriffe müssen an die gesamte Gruppe gehen - die Konsistenzwahrung liegt beim Gruppenkommunikationssystem und ist durch dessen Zuverlässigkeits-

und Ordnungssemantik bestimmt


Verwaltungs-Strategien: • Primärkopie

- alle Schreibzugriffe werden immer an einen Primärserver geschickt

è dieser sorgt dafür, daß auch alle Sekundärserver auf aktuellen Stand gebracht werden è Lesezugriffe können auch von Sekundärservern bedient werden è Je nachdem, wie und wann der Primärserver veränderte Daten an die Sekundärserver propagiert, können

schwache bis starke Konsistenzmodelle realisiert werden è soll immer konsistent auch bei Sekundärservern gelesen werden können, muß die Veränderung atomar im Serververbund verteilt werden, sonst:

è bei nicht atomarem Aktualisieren können Klienten bei Sekundärservern „alte“ Werte lesen

- bei einem Absturz des Primärservers sollte ein Sekundärserver dessen Rolle übernehmen


Bild S.26 Replikationsmanagement mit Primärserver


• Abstimmungsverfahren - Engpaß eines Primärservers beim Schreibzugriff durch Abstimmungsverfahren (engl.: voting) vermeiden

- Idee: - zum Schreiben benötigt man mindestens N/2+1 der N Server ‚online’

- diese Server merken sich eine neue Versionsnummer zum geänderten Replikat, damit haben N/2+1 Server ein neues Replikat

- beim Lesen eines Replikat braucht man mindestens N/2+1 Server der N Server è darin befindet sich dann mit Sicherheit mindestens einmal die neueste Version

- Verallgemeinerung (Gifford):

- man benötigt zum Lesen ein Lesequorum Nl - zum Schreiben ein Schreibquorum Ns - mit Nl + Ns > N, wobei N der Anzahl der Server entspricht


• Lazy-Update - alle Server können Lese- und Schreibzugriffe bedienen è erhält ein Server eine Aktualisierungsnachricht, schickt er diese nicht sofort zu den anderen Servern è er faßt mehrere Updates zusammen und sendet sie dann periodisch ( Gossip-Nachricht ) an die anderen

- Konsequenz: keine starke Konsistenz möglich - aber: die Antwortgeschwindigkeit ist höher als bei den vorhergehenden Verfahren

Bild S.27 Replikationsmanagement mit Lazy Update


• Peermodell - Klient und Server sind in einem Programm vereinigt - innerhalb der einzelnen Peers kann jede der zuvor beschriebenen Formen des Replikations- und

Änderungsmanagements implementiert sein

Bild S.28 Peermodell


Übungen zu Synchronisation und Koordination 1. Zeit in Verteilten Systemen a. Sie stellen fest, daß eine Uhr 4 Sekunden vorgeht. Die Uhr soll in 8 Sekunden justiert sein. Geben Sie eine

Funktion an, die dies gewährleistet. b. Was versteht man unter logischer Zeit. Warum reicht eine logische Zeit zur Synchronisation bei verteilten

Systemen oft aus? Nennen Sie Anwendungs-Beispiele für Lamport- und Vektor-Zeit. c. Geben Sie zu untenstehendem Ablaufplan für jedes Ergeignis die jeweilige Lamport- bzw. Vektorzeit an.

Erötern Sie, welche Ereignisse in einer happened-before Relation stehen und wo keine Angaben möglich sind. Dabei bezeichnen:

I - die Initialisierung der Zeit auf 0 bzw. den entsprechenden Vektor. L - ein lokales Ereignis S - ein Sendeereignis E - ein Empfangsereignis



S SYNCHRONISATION UND KOORDINATION 1

S.2 HEARTBEAT-ALGORITHMEN 2

S.2.1 Beispiel: Bestimmung der Netzwerktopologie 4

S.3 PROBE/ECHO-ALGORITHMEN 7

S.4 ELECTION-ALGORITHMEN 8

S.4.1 Bully-Algorithmus 9

S.5 SCHNAPPSCHÜSSE 12

S.6 VERTEILTER WECHSELSEITIGER AUSSCHLUß 19

S.6.1 Ein zentralisierter Algorithmus 21

S.7 TRANSAKTIONEN 24

S.7.1 Basisprimitive für Transaktionen 27

S.7.2 Implementierungsaspekte 28

S.7.3 Zwei-Phasen-Commit-Protokoll 31

S.7.4 Kontrolle nebenläufiger Zugriffe während einer Transaktion auf die beteiligten Objekte 33

S.8 VERTEILTE TERMINIERUNG 37

S.8.1 Verteilte Terminierung im Ring 38

S.9 VERKLEMMUNGEN IN VERTEILTEN SYSTEMEN 40

S.9.1 Erkennen von Verklemmungen 41

S.9.2 Vorbeugung vor Verklemmungen 44

S.10 REPLIKATION 47

S.10.1 Replikationsmanagement 50

ÜBUNGEN ZU SYNCHRONISATION UND KOORDINATION 56

Documents

S Synchronisation und Koordination - lsw.ee.hm.edulsw.ee.hm.edu/~tasin/vorlesung_vs/paul/Verteilte_Systeme_S.pdf · Dies impliziert Verklemmungs-Freiheit (engl.: deadlock free) und