1

Stand der Folien: 20. Dezember 2011

Aktuelle Themen zu Informatik der Systeme:

Nebenlaufige Programmierung:Praxis und Semantik

Zugriff auf mehrere Ressourcen

WS 2011/12

Deadlocks bei mehreren Ressourcen Transactional Memory

Ubersicht

1 Deadlocks bei mehreren RessourcenEinleitungDeadlock-VerhinderungDeadlock-Vermeidung

2 Transactional MemoryEinleitungACID-EigenschaftenOperationenMerkmale

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 2/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Deadlocks bei mehreren Ressourcen

Deadlock beim Mutual Exclusion Problem

Deadlock: Kein Prozess kommt in den kritischen Abschnitt,obwohl mindestens ein Prozess in den kritischen Abschnittmochte

Kommt dem Belegen einer Ressource gleich

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 3/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Deadlocks bei mehreren Ressourcen (2)

Deadlocks allgemeiner (bei mehreren Ressourcen)

Definition

Eine Menge von Prozessen ist deadlocked (verklemmt), wenn jeder(nicht beendete) Prozess auf ein Ereignis wartet, das nur einanderer Prozess herbeifuhren kann.

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 4/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Beispiele

Mutual-Exclusion Problem: Deadlock, wenn es nicht mehrmoglich ist, dass irgendein Prozess den kritischen Abschnittbetritt, obwohl alle Prozesse in den kritischen Abschnittmochten

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 5/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Beispiele (2)

Zwei Prozesse machen Umbuchungen zwischen Konto A undKonto B.

Vorgehensweise:

Sperren des ersten KontosSperren des zweiten KontosUberweisung von erstem Konto auf zweites Konto durchfuhrenEntsperren der Konten.

Prozess P Prozess Qwait(KontoA); wait(KontoB);wait(KontoB); wait(KontoA);buche von A nach B buche von B nach Asignal(KontoA); signal(KontoB);signal(KontoB); signal(KontoA);

Deadlock!

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 6/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Beispiele (3)

Funktionierende Losung (Deadlock-frei)

Prozess P Prozess Qwait(KontoA); wait(KontoA);wait(KontoB); wait(KontoB);buche von A nach B buche von B nach Asignal(KontoA); signal(KontoA);signal(KontoB); signal(KontoB);

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 7/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Beispiele (4)

Ahnliches Problem bei: Speisende Philosophen

Deadlock moglich, wenn alle Philosophen unsychronisiert

Alle haben die linke Gabel keiner die rechte.

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 8/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Beispiele (5)

Engstelle

Nur ein Fahrzeug kann passieren

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 9/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Beispiele (6)

Alle warten, dass “rechts frei” ist

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 10/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Beispiele (7)

Gleiches Problem, aber etwas komplizierter

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 11/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Deadlock-Behandlung

Vier Ansatze

1 Ignorieren: Keine Vorkehrungen, Hoffnung, dass Deadlocksnur selten auftreten.

2 Deadlock-Erkennung und -Beseitigung: Laufzeitsystemerkennt Deadlocks und beseitigt sie. Problem: FindeAlgorithmus der Deadlocks erkennt.

3 Deadlock-Vermeidung: Algorithmus verwaltet Ressourcen undlasst Situation nicht zu, die zu einem Deadlock fuhren konnen.

4 Deadlock-Verhinderung: Der Programmierer entwirft dieProgramme so, dass Deadlocks nicht auftreten konnen.

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 12/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Deadlock-Behandlung (2)

Offensichtlich: Beste Methode: Deadlock-Verhinderung

Dafur muss man wissen:Unter welchen Umstanden kann ein Deadlock auftreten?

Im folgenden: Bedingungen fur Deadlock

und Deadlock-Verhinderung

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 13/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Wann tritt Deadlock auf?

Vier notwendige Bedingungen (alle gleichzeitig erfullt):

1 Wechselseitiger Ausschluss (Mutual Exclusion): Nur einProzess kann gleichzeitig auf eine Ressource zugreifen,

2 Halten und Warten (Hold and Wait): Ein Prozess kann eineRessource anfordern (auf eine Ressource warten), wahrend ereine andere Ressource bereits belegt hat.

3 Keine Bevorzugung (No Preemption): Jede Ressource kannnur durch den Prozess freigegeben (entsperrt) werden, der siebelegt hat.

4 Zirkulares Warten: Es gibt zyklische Abhangigkeit zwischenwartenden Prozessen: Jeder wartende Prozess mochte Zugriffauf die Ressource, die der nachste Prozesse im Zyklus belegthat.

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 14/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Veranschaulichung

Prozess P1 will Ressource R1 belegen (hat sie aber nicht):

P1 R1

Prozess P1 hat Ressource R1 belegt:

P1 R1

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 15/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Veranschaulichung der 4 Bedingungen

1 Wechselseitiger Ausschluss (Mutual Exclusion): Nur einausgehender (gruner) Pfeil pro Ressource

2 Halten und Warten (Hold and Wait): Rote und grune Pfeilefur einen Prozess moglich

3 Keine Bevorzugung (No Preemption): Grune Pfeile konnennicht verandert werden (außer vom Prozess, der den Pfeil hat)

4 Zirkulares Warten: Zyklus im Graphen

Verboten:

P2

R1P1

Erlaubt:

R1P1

R3

P2

R1P1

R3

P3 R2

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 16/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Beispiel

Prozess 1: Prozess 2: Prozess 3:Request R1 Request R2 Request R3

Request R2 Request R3 Request R1

Release R1 Release R2 Release R3

Release R2 Release R3 Release R1

P1 P2 P3

R1 R2 R3

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 17/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Beispiel: Anderes Scheduling

Prozess 1: Prozess 2: Prozess 3:Request R1 Request R2 Request R3

Request R2 Request R3 Request R1

Release R1 Release R2 Release R3

Release R2 Release R3 Release R1

P1 P2 P3

R1 R2 R3

Deadlock-Verhinderung: Programm so erstellt, dass unabhangigvom Scheduling kein Deadlock auftritt

Deadlock-Vermeidung: Scheduler erkennt Deadlock-Gefahr undschließt diese Schedulings aus

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 18/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Deadlock-Verhinderung

Ansatz: Greife eine der vier Bedingungen an, so dass sie nie wahrwird.

Mutual Exclusion: Im allgemeinen schwer moglich, manchmalaber schon:Bsp. Druckerzugriff wird durch Spooler geregelt.

No Preemption: Schwierig, man kann z.B. nicht den Zugriffauf den Drucker entziehen, wenn Prozess noch nicht fertiggedruckt hat usw.

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 19/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Verhindern von Hold and Wait

Moglichkeit: Prozess fordert zu Beginn alle Ressourcen an, dieer benotigt.

Philosophen: Exklusiver Zugriff auf alle Gabeln

1. Problem: Evtl. zu sequentiell

2. Problem: Oft nicht klar, welche Ressourcen jeder Prozessbraucht

Variation dieser Losung: 2-Phasen Sperrprotokoll

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 20/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

2-Phasen Sperrprotokoll

Die Prozesse arbeiten in zwei Phasen

Jeder Prozess fuhrt dabei aus:

1. Phase: Der Prozess versucht alle benotigen Ressourcen zubelegen.Ist eine benotigte Ressource nicht frei, so gibt der Prozessalle belegten Ressourcen zuruck und der Prozess startet vonneuem mit Phase 1.

2. Phase: Der Prozess hat alle benotigten RessourcenNachdem er fertig mit seiner Berechnung ist, gibt er alleRessourcen wieder frei.

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 21/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Beispiel: Speisende Philosophen

Initial alle Gabeln (Semaphoren) mit 1 initialisiert

tryWait: Nicht-blockierende Implementierung von wait:

tryWait(S) ={

True, wenn Semaphore belegt werden konnteFalse, sonst

Phase 1, Phase 2

Philosoph iloop forever(1) l := tryWait(gabel[i]);(2) if l then(3) r:=tryWait(gabel[i+1]);(4) if r then(5) Philosoph isst(6) signal(gabel[i + 1]);(7) signal(gabel[i]);(8) else signal(gabel[i]);(9) Philosoph denkt;end loop

P3

gabel[1]P1

gabel[2]

P2 gabel[3]

Deadlock nicht moglich!

Aber Livelock!

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 22/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Timestamping-Ordering

Prozesse erhalten eindeutigen Zeitstempel, wenn sie beginnen.

Zwei-Phasen Sperrprotokoll mit Timestamping

Jeder Prozess geht dabei so vor:

1. Phase: Der Prozess versucht alle benotigten Ressourcen aufeinmal zu sperren.Ist eine benotigte Ressource belegt mit kleineremZeitstempel, dann gibt Prozess alle Ressourcen frei undstartet von neuem.Ist eigener Zeitstempel kleiner, dann wartet der Prozess aufdie restlichen Ressourcen.

2. Phase: Wie vorher.

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 23/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Timestamping-Ordering (2)

Deadlock-frei

Livelock nicht moglich

Starvation-frei.

Definition

Starvation ist eine Situation, in der ein Prozess niemals (nachbeliebig vielen Berechnungsschritten) in der Lage ist, allebenotigten Ressourcen zu belegen.

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 24/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Zirkulares Warten verhindern

Versuche das zirkulare Warten zu verhindern.

Philosophen-Problem: N. Prozess hebt zuerst rechte Gabel

Dann kann kein zirkulares Warten enstehen

Denn die Gabeln wurden total geordnet: 1 < 2 . . . N .

Und die Philosophen haben die Ressourcen entsprechenddieser Ordnung belegt.

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 25/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Total-Order Theorem

Allgemein gilt:

Total-Order Theorem

Sind alle gemeinsamen Ressourcen durch eine totale Ordnunggeordnet und jeder Prozess belegt seine benotigten Ressourcen inaufsteigender Reihenfolge bezuglich der totalen Ordnung, dann istein Deadlock unmoglich.

Beweis: durch Widerspruch. Annahme: Es gibt einen Deadlock.D.h. es gibt Ressoucen R1, . . . , Rn und Prozesse P1, . . . , Pn mit

Prozess Pi hat Ressource Ri−1 belegt

Prozess Pi wartet auf Ressource Ri

Sei Rj die kleinste Ressource aus {R1, . . . , Rn} bezuglich dertotalen Ordnung. Dann wartet Prozess Pj auf Ressource Rj , wobeier Ressource Rj−1 schon belegt hat. Widerspruch.

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 26/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Total Order Theorem (2)

Man kann nachweisen:

Lemma

Ein Deadlock-freies System, indem die Belegung von (allen)einzelnen Ressourcen Starvation-frei ist, ist auch insgesamtStarvation-frei

Mit dem Total Order Theorem lasst sich folgern:

Wenn es eine totale Ordnung der Ressourcen gibt, die Ressourcenentsprechend dieser Ordnung belegt werden und die Belegungeinzelner Ressourcen Starvation-frei ist, dann ist das GesamtsystemStarvation-frei.

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 27/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Deadlock-Vermeidung

Erinnerung:

Deadlock-Vermeidung: Algorithmus verwaltet Ressourcen undlasst Situation nicht zu, die zu einem Deadlock fuhren konnen.

Im folgenden:

Beispiel von Dijkstra zur Deadlock-Vermeidung:

Problem des Deadly Embrace

Losung: Bankier-Algorithmus

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 28/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Deadly Embrace

Annahme:

Es gibt m gleiche Ressourcen

Jeder Prozesse Pi benotigt eine gewisse Zahl mi ≤ m dieserRessource

Prozesse fordern Ressourcen nach und nach an

Die maximal benotigte Anzahl mi ist beim Start bekannt

Hat ein Prozess seine maximale Anzahl, terminiert er und gibtdie Ressourcen zuruck.

Problem: Implementiere Ressourcenverwalter

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 29/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Dijkstra’s Veranschaulichung

Ressource: Geld

Prozesse sind Bankkunden

Ressourcenverwalter: Bankier

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 30/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Deadlock-Vermeidung: Beispiel

Vorhandene Ressourcen am Anfang: 98 EUR

2 Kunden, beide benotigen 50 EUR

Beide Kunden haben bereits 48 EUR erhalten

Beide Kunden fordern 1 EUR an.

Soll der Bankier beide Anforderungen zulassen?

Nein: Dann haben beide Kunden 49 EUR, die Bank 0 EUR

Ein Deadlock ist eingetreten.

Ein Kunde fordert 1 EUR an

Soll er das Geld bekommen?

Ja, denn danach ist der Zustand immer noch sicher

sicher = Deadlock noch vermeidbar (muss nicht eintreten)

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 31/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Losungsversuch

Naive Losung:

Kunden erhalten Reihenfolge

Bankier bedient immer einen Kunden, bis er seinen maximalenBetrag erhalten hat

Alle andere Kunden mussen warten

Schlecht, da sequentieller Algorithmus

Deshalb:

Zusatzliche Anforderung: Erlaube soviel Nebenlaufigkeit wiemoglich

Lehne nur dann Anfrage ab, wenn der Zustand dann unsicherwurde,d.h. ein Deadlock eintreten muss

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 32/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Bankier-Algorithmus: Datenstrukturen

Annahme: Verschiedene Ressourcen, z.B. mehrere Wahrungen

Vektor−→A : Aktueller Vorrat in der Bank. Jede Komponente

von−→A ist nicht-negative Ganzzahl und stellt Vorrat einer

Wahrung dar

P Menge der Kunden (Prozesse). Fur P ∈ P sei:

−−→MP der Vektor der maximal durch Prozess P anzuforderndenRessourcen−→CP der Vektor der bereits an Prozess P vergebenenRessourcen

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 33/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Bankier-Algorithmus: Sicherer Zustandsicher = Deadlock in der Zukunft vermeidbar

Ein Zustand (mit all seinen Vektoren) ist sicher,wenn es eine Permutation π der Prozesse P1, . . . , Pn ∈ P gibt,sodass es fur jeden Prozesse Pi entsprechend der Reihenfolge derPermutation genugend Ressourcen gibt, wenn er dran ist.

Genugend Ressourcen bedeutet hierbei:

−→A +

∑π(j)<π(i)

−−−→CPπ(j)

−−−→MPi +

−→CPi ≥

−→0

Zu den aktuell verfugbaren Ressourcen−→A

durfen momentan vergebenen Ressourcen hinzuaddiertwerden, deren zugehorige Prozesse entsprechend derPermutation vor Pi vollstandig bedient werden.

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 34/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Bankier-Algorithmus: Grundgerust

Bankier erhalt eine Ressourcenanfrage−→LP eines Prozesses

P ∈ P.

Konsistenzbedingung:−→LP +

−→CP ≤

−−→MP

Bankier berechnet den Folgezustand, alsob P die Ressourcenerhalt, d.h. −→

A :=−→A −

−→LP−→

CP :=−→CP +

−→LP

Anschließend: Teste ob Zustand noch sicher

Wenn unsicher, dann stelle Ursprungszustand her und lasse Pwarten

Wenn Kunde maximale Ressourcen erhalt wird−→A automatisch

angepasst,

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 35/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Bankier-Algorithmus: Test auf Sicherheit

function testeZustand(P,−→A ):

if P = ∅ thenreturn “sicher”

else

if ∃P ∈ P mit−−→MP −

−→CP ≤

−→A then

−→A :=

−→A +

−→CP ;

P := P \ {P};testeZustand(P,

−→A )

elsereturn “unsicher”

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 36/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Eigenschaften

Algorithmus berechnet eine der gesuchten Permutationen

Laufzeit O(|P|2)!Kriterium ist ausschließlich

”Kein Deadlock“ sonst keine

”Optimierung“

kleine Verbesserung:

Wenn−→A ≥

−−→MP −

−→CP (genugend Ressourcen vorhanden um P

komplett zu bedienen) dann ist nach Anfrage−→LP der Zustand

immer sicher (Test muss nicht ausgefuhrt werden)

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 37/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Beispiel

4 Ressourcen (EUR, USD, JYN, SFR)4 Prozesse A, B, C, DAktueller Zustand

Maximal-Werte Erhaltene Werte Verfugbare Ressourcen−−→MA = (4, 7, 1, 1)

−→CA = (1, 1, 0, 0)

−→A = (2, 2, 3, 3)

−−→MB = (0, 8, 1, 5)

−→CB = (0, 5, 0, 3)

−−→MC = (2, 2, 4, 2)

−→CC = (0, 2, 1, 0)

−−→MD = (2, 0, 0, 2)

−→CD = (1, 0, 0, 1)

Ist der Zustand sicher?

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 38/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung Deadlock-Verhinderung Deadlock-Vermeidung

Beispiel (2)

Wir betrachten nun die Anfrage LA = (2, 2, 0, 0), d.h. Prozess Amochte zwei weitere EUR und zwei weitere USD belegen.

Nach Aktualisierung (−→A :=

−→A −

−→LA und

−→CA :=

−→CA +

−→LA)

erhalten wir den Zustand:

Maximal-Werte Erhaltene Werte Verfugbare Ressourcen−−→MA = (4, 7, 1, 1)

−→CA = (3, 3, 0, 0)

−→A = (0, 0, 3, 3)

−−→MB = (0, 8, 1, 5)

−→CB = (0, 5, 0, 3)

−−→MC = (2, 2, 4, 2)

−→CC = (0, 2, 1, 0)

−−→MD = (2, 0, 0, 2)

−→CD = (1, 0, 0, 1)

Bleibt der Zustand sicher?

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 39/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung ACID-Eigenschaften Operationen Merkmale

Transactional Memory

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 40/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung ACID-Eigenschaften Operationen Merkmale

Transactional Memory

Neuer Programmieransatz

Ziel: Programmier schreibt mehr oder weniger sequentiellenCode

System garantiert Deadlockfreiheit und evtl. noch mehr

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 41/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung ACID-Eigenschaften Operationen Merkmale

Motivation: Beispiel

Uberweisungen zwischen Konto A und B

Losung: Sperre Konten entsprechend einer totalen Ordnung

Erweiterung: Buche nur dann ab, wenn Konto gedeckt

Losung 1: Abort und Restart: Wenn Konto nicht gedeckt,starte von neuem. Birgt die Gefahr, immer wieder neu zustarten.

Losung 2: Warte bis Konto gedeckt (Sperren mussenaufgehoben werden!)

Fazit: Kleine Erweiterungen erfordern große Anderungen

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 42/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung ACID-Eigenschaften Operationen Merkmale

Lock-basierte Programmierung ist schlecht . . .

(Argumente von S. L. Peyton Jones)

Setzen zu weniger Locks: Programmierer vergisst eine Sperrezu setzen, Folge: Race Condition

Setzen zu vieler Locks: Programmierer ubervorsichtig:Folgen:

Programm unnotig sequentiell (Best-Case),Deadlock (Wort-Case)

Setzen der falschen Locks: Beziehung zwischen Sperren undDaten kennt nur der Programmierer. Compiler oder andereProgrammierer kennen die Beziehung evtl. nicht.

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 43/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung ACID-Eigenschaften Operationen Merkmale

Lock-basierte Programmierung ist schlecht . . . (2)

Setzen von Locks in der falschen Reihenfolge: Das Total-OrderTheorem kann nur eingehalten werden, wenn jederProgrammierer weiß, wie die Ordnung der Locks aussieht.

Fehlerbehandlung schwierig, da bei Fehlerbehandlung Locksentsperrt werden mussen.

Vergessene signal-Operationen oder vergessenes erneutesPrufen von Bedingungen fuhrt zu fehlerhaften Systemen.

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 44/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung ACID-Eigenschaften Operationen Merkmale

Ein schlagendes Argument

Lock-basierte Programmierung ist nicht modular

Beispiel:

Buche von Konto A1 oder A2 auf Konto B, je nachdemwelches Konto gedeckt ist.

kann nicht aus den bestehenden Programmenzusammengesetzt werden

sondern erfordert neues Programm

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 45/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung ACID-Eigenschaften Operationen Merkmale

Transactional Memory: Idee

Datenbanksysteme sind nebenlaufig

Aus Anwendersicht jedoch: Kein Sperren o.a. notig

Anwender schreibt Anfragen, die als Transaktionen auf derDatenbank ausgefuhrt werden

Idee: Ubertrage dieses Modell fur die nebenlaufigeProgrammierung

Transaktionen auf dem gemeinsamen Speicher

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 46/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung ACID-Eigenschaften Operationen Merkmale

Transactional Memory: Stand der Technik

Es gibt einige (prototypische) Implementierungen

Es gibt Software Transactional Memory aber auchHardware Transactional Memory

Jede Menge Designunterschiede

Praxistauglichkeit noch nicht erwiesen

Transaktionsverwaltung ist Zeit- und Platzintensiv

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 47/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung ACID-Eigenschaften Operationen Merkmale

ACID-Eigenschaften

Zunachst betrachten wir Datenbanktransaktionen.Diese mussen die ACID-Eigenschaften erfullen:

Atomicity: Alle Operationen einer Transaktion werdendurchgefuhrt, oder keine Operationen wird durchgefuhrt.Verboten: Operation schlagt fehl, aber Transaktion erfolgreichVerboten: fehlgeschlagene Transaktion hinterlasstbeobachtbare UnterschiedeEine erfolgreiche Transaktion commits,eine fehlgeschlagene Transaktion aborts

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 48/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung ACID-Eigenschaften Operationen Merkmale

ACID-Eigenschaften (2)

Consistency: Eine Transaktion verandert den Zustand derDatenbank. Diese Anderung muss konsistent sein.Konsistenz einer commited Transaktion hangt von derjeweiligen Anwendung ab. (z.B. der Kontostand einesBankkontos darf nicht beliebig groß negativ sein, oder ein neuhinzugefugtes Konto muss eine eindeutige Kontonummererhalten, usw.).

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 49/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung ACID-Eigenschaften Operationen Merkmale

ACID-Eigenschaften (3)

Isolation: Eine Transaktion liefert ein korrektes Resultatunabhangig davon, wieviele weitere nebenlaufigeTransaktionen durchgefuhrt werden.

Durability: Das Ergebnis einer commited Transaktion istpermanent. D.h. es wird auf der Festplatte oder ahnlichespermant geschrieben, bevor die Transaktion als commitedgekennzeichnet werden darf.

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 50/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung ACID-Eigenschaften Operationen Merkmale

Speichertransaktionen

A,C,I wunschenswert

Durability nicht moglich, da Hauptspeicher fluchtig.

Atomaritat nur gewahrleistet, wenn alle Operationen alsTransaktionen durchgefuhrt werden.

Weitere Anforderungen an TM:

Datenbanken konnen Zugriffszeiten auf Festplatten mitRechenzeit gegenrechnen, im Hauptspeicher geht das nicht,da Zugriffszeiten viel kurzer

TM muss in bestehende Programmiersprachen integriertwerden.

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 51/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung ACID-Eigenschaften Operationen Merkmale

Basisoperationen von TM

atomic-Blocke:

atomic {Code der Transaktion

}

Code wird als Transaktion durchgefuhrt

Vorteil gegenuber Monitoren: Variablen mussen nicht explizitaufgezahlt werden.

Problem: Was passiert wenn gleiche Variable auch vonaußerhalb geandert wird?

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 52/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung ACID-Eigenschaften Operationen Merkmale

Atomaritat ist nicht garantierbar

Transaktionen mussen abbrechen oder comitten, aber:

atomic {while True do skip;

}

Deswegen andere Semantik (anders als bei Datenbanken): DieAusfuhrung einer Transaktion (atomaren Blocks) hat drei moglicheErgebnisse:

commit, wenn die Transaktion erfolgreich war,

abort, wenn die Transaktion abgebrochen wurde

undefiniert, wenn die Transaktion nicht terminiert

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 53/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung ACID-Eigenschaften Operationen Merkmale

Abbrechen von Transaktion

Transaktionen brechen ab, wenn

Ein Konflikt auftritt, und der Transaktionsmanager aufAbbruch (und Roll-Back) entscheidetVerhalten normalerweise: Manager versucht die Transaktionerneut durchzufuhren

ein expliziter abort-Befehl aufgerufen wird.Verhalten normalerweise: Transaktion wird abgebrochen

atomic {Guthaben := Guthaben + Zins;if Guthaben < 0 then abort;

}

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 54/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung ACID-Eigenschaften Operationen Merkmale

Semantik von atomic

Programm verhalt sich, alsob fur alle atomic-Blocke einglobaler Lock verwendet wird.

Zugriff auf Transaktionsvariablen außerhalb von Transaktionenkann beliebigen Unsinn anstellen

Schreibender Zugriff: Variable wird verandert

Lesender Zugriff: Kann Werte beobachten, die noch nichtcomitted sind!

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 55/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung ACID-Eigenschaften Operationen Merkmale

Basisoperationen (2)

Der retry-BefehlErmoglicht es Transaktionen zu koordinieren

retry: Transaktion wird abgebrochen (Roll-back) und erneutgestartet

Beispiel: Bounded Buffer:

atomic{if isEmpty(buffer) then retry;Lese erstes Element des Puffers usw.

}

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 56/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung ACID-Eigenschaften Operationen Merkmale

Basisoperationen (3)

Der orElse-BefehlGibt Alternativen vor, wenn Transaktionen abbrechen

T1 orElse T2.

Zunachst wird T1 durchfuhrt. Falls T1 commited oder T1

explizit via Befehl abgebrochen wird, dann wird T2 nichtausgefuhrt. Die Transaktion T1orElseT2 commited oderaborts, je nachdem was die Ausfuhrung von T1 macht.Falls T1 durch den Transaktionsmanager abgebrochen wirdoder retry ausgefuhrt wird, dann startet dieser T1 nicht neu,sondern versucht T2 durchzufuhren.Falls T2 explizit aborted oder commited, dann ist die gesamteTransaktion beendet.Falls T2 ein retry durchfuhrt (oder vom System abgebrochenwird), dann wird wieder mit T1orElseT2 gestartet.

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 57/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung ACID-Eigenschaften Operationen Merkmale

orElse-Schaubild

T1 orElse T2

T1 T2

T1orElseT2 commited T1orElseT2 aborted

T1 commitsT1 aborts

T1 retries

T2 aborts

T2 retries

T2 commits

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 58/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung ACID-Eigenschaften Operationen Merkmale

orElse-Beispiel

atomic {{if A1 ≤ 0 then retry;B := B + Betrag;A1 := A1 - Betrag;

}orElse{if A2 ≤ 0 then retry;B := B + Betrag;A2 := A2 - Betrag;

}

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 59/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung ACID-Eigenschaften Operationen Merkmale

Merkmale von TM-Systemen

Weak / Strong Isolation

Weak Isolation: Speicherplatze konnen auch außerhalb vonTransaktionen manipuliert werden

Strong Isolation: Trennung in Transaktionsvariablen undandere Variable. System schutzt den Zugriff aufTransaktionsvariablen. Z.B. fugt der Compiler atomic-Blockeautomatisch ein.

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 60/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung ACID-Eigenschaften Operationen Merkmale

Merkmale von TM-Systemen (2)

Geschachtelte Transaktionen

x := 1atomic {

x:=2;atomic {

x:= 3;abort;

}}

Geglattete Transaktionen: Verhalten, alsob das innere atomicStatement fehlt. Beispiel ergibt abort (x=1).

Geschlossene Transaktionen: Verhalten wie bei geglatteten,aber innerer Abbruch fuhrt nicht zum Abbruch der außerenTransaktion. Beispiel ergibt x=2.

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 61/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung ACID-Eigenschaften Operationen Merkmale

Merkmale von TM-Systemen (3)

Offene Transaktionen: Innere Transaktion sind eigenstandig.Sobald innere Transaktion committed, ist deren Effekt fur allesichtbar und bleibt sichtbar, selbst dann, wenn die außereTransaktion abbricht

x := 1atomic {

x:=2;atomic {

x:= 3;}abort;

}

Ergebnis: x = 3!

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 62/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung ACID-Eigenschaften Operationen Merkmale

Merkmale von TM-Systemen (4)

Granularitat

Welche Einheiten werden auf Konflikte uberwacht?

Wort-/ Blockgranularitat: Wenn paralleler Zugriff aufSpeicherworte, dann Konflikt

Objektgranularitat: Paralleler Zugriff auf ein Objekt fuhrt zumKonflikt

Beachte bei Objektgranularitat: Konflikt auch dann, wennunterschiedliche Objektattribute geandert werden

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 63/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung ACID-Eigenschaften Operationen Merkmale

Merkmale von TM-Systemen (5)

Direktes und verzogertes Update

Direktes Update:

Ausfuhrende Transaktionen modifizieren Objekte sofort.Erfordert Schutz vor gleichzeitigem Zugriff (ConcurrencyControl)Alte Werte werden in einem Log gespeichertAbbruch der Transaktion: Roll-Back und Recovery:Wiederherstellen der Daten aus dem Log

Verzogertes Update

Transaktionen erhalten lokale Kopien der ObjekteModifikation zunachst an den KopienBeim Commit: Originale werden durch lokale Kopien ersetztLogging: Wer hat welche Kopien, wer darf committen?

Direktes Update ist optimistisch, verzogertes Updatepessimistisch

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 64/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung ACID-Eigenschaften Operationen Merkmale

Merkmale von TM-Systemen (6)

Zeitpunkt der Konflikterkennung

Beim ersten Zugriff (Logging: Wer hat schon zugegriffen)

Iteratives Prufen (in Zeitabstanden)

Am Ende: Erst beim committen wird gepruft, ob ein Konfliktvorliegt

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 65/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung ACID-Eigenschaften Operationen Merkmale

Merkmale von TM-Systemen (7)

Konfliktmanagement

Beim Konflikt: Welche Transaktion wird abgebrochen?

Viele verschiedene Strategien

Ziel: Fortschritt des Gesamtsystems

Dadurch verboten: Breche alle Transaktionen ab

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 66/67

Deadlocks bei mehreren Ressourcen Transactional Memory Einleitung ACID-Eigenschaften Operationen Merkmale

Fazit

Transactional Memory noch in den Kinderschuhen

Hoffnung fur die Zukunft: Leichtere Programmierung mit TM

Problem: Transaktionen konnen nur Operationen sicherverarbeiten, die umkehrbar sind

Beispiele: Drucke”Hallo“,

”Launch Missiles“ etc.

TIDS – Globale Deadlocks – WS 2011/12 – D. Sabel 67/67