11. Mehrbenutzersynchronisation_alt

Damit das System besser ausgelastet wird, da es oft vorkommt, dass auf langsamere Betriebsmittel (e.g. Hintergrundspeicher) oder Benutzereingaben gewartet werden muss

Die einhaltung der Isolation der ACID ziele

-> für jede TA muss es so erscheinen, als wäre sie die einzig aktive!!

1. Verlorengegangene Änderungen (lost updates)

2. Abhängigkeit von nicht freigegebenen Änderungen

3. Phantomproblem

Falls bsp. zwei TA ein datum lesen, ändern und zurückschreiben.

-> Wenn beide lesen bevor die jeweils andere TA zurückgeschrieben hat, wird nur die änderung der als letzte zurückschreibenden TA gespeichert, die änderung der anderen geht verloren!

Auch als dirty read bezeichnet

-> Eine TA greift auf ein datum zu, das von einer anderen TA die dieses bearbeitet nocht nicht freigegeben wurde

-> evtl. ist wert nicht gültig oder TA aborted; dadurch hat andere TA falsche Grundlage für eigene Operation

Bsp.: TA1: bankkonto + 300; TA2: zinsen Bankkonto * 1.03; TA1: abort

-> Es werden zu viel zinsen (9 euro) berechnet!

Diese art von Problem tauch auf, falls eine TA auf ein Datum zugreift, das noch nicht vollständig ist (daten fehlen…)

Bsp. ein Fach in der Notenliste wurde noch nicht veröffentlöicht und einen andere TA greift bereits darauf zu und stellt die zeugnisse zusammen

Das vermögen, eine menge von TA so auszuführen dass sie nebenläufig arbeiten aber das Konzept dier Isolation nicht verletzen

• read

• write

• abort

• commit

=> abort und commit sind mutually exclusive!!!

Es reicht eine Partielle ordnung

• Alle Operationen einer TA i müssen vor einem abort oder commit dieser Transaktion ausgeführt worden sein

  • (abort oder commit IMMER letzte Operation)

• Falls eine TA ein datum liest und schreibt, muss die reihenfolge festgelegt sein

  • reihenfolge gleicher TA auf gleichem Datum immer geordnet!

Den verzahnten ablauf mehrerer Transaktionen in der form einer Partiellen Ordnung auf elementaren Operaitonen

Für die von der serialisierbarkeit vorgeschriebenen Operationen und sog. Konfliktoperationen

Mengen von Operationen, die bei unkontrollierter ausführung zu Inkonsistenzen führen können

Immer wenn ein Datum gelesen und geschrieben wird liegt ein Konflikt vor

• ri(A) wj(A) muss immer geordnet sein (lesen und schreiben auf gleichem Datum)

• wj(A) wi(A) muss immer geordnet sein (schreiben auf gleichem Datum)

Falls alle Konfliktoperationen die gleiche Reihenfolge haben

-> anordnung der nicht konflikt operationen irrelevant!

In dem man durch schlaues vertauschen der nicht konflikt operationen eine äquivalente historie schafft, die besser verzahnt (performanter) ist

Wenn sie äquivalent zu einer seriellen (hintereinanderausführung der TA als blöcke) äquivalent ist!

Ob es eine serialisierbare Historie zu einer gegebenen gibt, und wie diese geordnet sein muss

-> “ordnung” der Transaktionen

• Man schaut sich alle erfolgreich abgeschlossenen (commit) Transaktionen einer Historie an

• für jede Konfliktoperation zweier Transaktionen Ti und Tj zeichnet man eine gerichtete Kante zwischen Ti und Tj an in richtung der später ausgeführten operation (bsp. ri(A) < rj(A) => Ti -> Tj)

Falls der Serialisierbarkeitsgraph azyklisch ist

Falls die anordnung der Transaktionen einer Topologischen Sortierung des Resialisierbarkeitsgraphen entspricht

-> Keine Transaktion Ti steht vor einer anderen Tj, falls es eine (auch transitive) gerichtete Kante von Tj nach Ti gibt!

Die Historie soll so geordnet sein, dass zu jedem Zeitpunk vor einem commit die entsprechende TA lokal zurückgesetzt werden kann ohne dass andere TA davon beeinträchtigt werden

Falls bei lokalem zurücksetzen einer TA bereits commitete TA nicht in mitleidenschaft gezogen werden

=> es gilt immer, dass die schreibende TA vor der lesenden commited

Falls folgendes gilt:

1. wj(A) < ri(A) -> i liest ein Datum dass j zuvor geschrieben hat

2. Tj wird nicht vor dem Lesevorgang zurückgesetzt (falls zurückgesetzt wäre die änderung ja verworfen…)

3. Alle anderen Schreibvorgänge anderer Transaktionen auf A werden zwischen schreiben von j und lesen von i zurückgesetzt (letztes datum ist das das j geschrieben hat…)

=> i liest von j, falls es ein Datum liest das j zuletzt geschrieben hat

Es entsteht ein kaskadierendes zurücksetzen, indem eine schreibende TA aborted, dann die lesende auch aborten muss was wiederum zu einem abort von lesenden TA der lesenden TA zufolge hat……

Falls Ti von Tj liest, muss Tj erst commiten

-> änderungen dürfen erst gelesen werden, wenn die TA die die änderung ausgeführt hat commited hat

Ohne kaskadierendes zurücksetzen

plus:

es dürfen keine geschriebenen daten nicht abgeschlossener (commit oder abort) Transaktionen überschrieben werden

-> Also falls eine TA ein datum liest oder überschreibt das zuvor von der anderen geschrieben wurde muss die erste TA bereits ihr abort oder commit ausgeführt haben

serielle historien TM Strikten Historien TM ohne kaskadierendes Rücksetzen TM alle historien

und serialisierbare historien können jede klasse davon sein! (wobei serielle historien immer serialisierbar sind!)

Er ordnet Operaitonen so, dass sie serialisierbarkeit und kein kaskadierendes Rücksetzen erfüllen

1. Sperrbasierte Synchronisation

2. Zeitstempelbasierte-Synchronisation (pessimistische synchronisation)

3. Optimistische Synchronisation

Sie stellt sicher, dass die resultierende Historie serialisierbar bleibt

TA dürfen erst nach erhalt einer Sperre auf ein Datum zugreifen

1. S (Shared, Read Lock, Lesesperre) -> Transaktion kann read ausführen auf datum von dem sie die S-Sperre erhalten hat

   Mehrere TA können diese Sperre für gleiches datum haben

2. X(exclusive, write lock, schreibsperre) -> TA kann auf datu mder Soerre write operation ausführen

   Diese sperre kann je datum nur eine TA haben

S kann mit S; aber X kann nur alleine (kein S oder X darf bereits auf Datum liegen)

Das Zwei Phasen Sperrprotokoll (2PL)

1. jedes Objekt das eine TA benutzen möchte muss vorher gesperrt werden

2. Eine TA die eine sperre besitzt fordert diese nicht noch einmal an

3. Eine TA muss die sperre anderer TA auf die von ihr angeforderte beachten

   -> falls nicht verträglich, wird sie in eine warteschlange eingereiht

4. Jede TA durchläuft 2 phasen

   1. Wachstumsphase (sperren werden angefordert aber keine greigegeben)

   2. Schrumfungsphase (berworbene sperren werden freigegeben, keine neuen angefordert)

5. Bei EOT (Transaktionsende) muss die TA alle erworbenen sperren freigeben

Es garabtiert nicht das vermeiden von kaskadierendem rücksetzen

Strenges 2PL

erweiterung:

Keine schrumpfungsphase, sondern alle Sperren werden erst bei EOT freigegeben!!

Es können Deadlocks auftreten

1. Time Out methode

2. Wartegraphen

• vorteil: günstige methode

• nachteil:

  • falls zeitmaß zu klein kann es sein dass TA abgebrochen werden, die eigentlich gar nicht verklemmt sind (sondern TA wartet nur auf ressourcen wie z.b. CPU)

  • falls zeitmaß zu groß: deadlocks können zu lange geduldet werden bevor sie abgebrochen werden

TA werden überwacht

-> falls eine TA innerhalb eines definierten Zeitmaßes (bsp. 1 sec) keinen fortschritt erzielt, geht das system von einem deadlock aus und setzt die TA zurück

Ein graph bei dem

• knoten: derzeit aktive Transaktionen

• gerichtete kanten: TA wartet auf sperre die andere TA besitzt (will sperre -> besitzt sperre)

Falls der Wartegraph einen Zyklus aufweist

Präziser aber auch teurer

Rücksetzen einer TA im Zyklus

Mehrere Strategien:

• Minimierung rücksetzaufwand -> jüngste TA rücksetzen

• Maximierung der freigegebenen Ressourcven -> TA mit meisten Sperren rücksetzen

• Vermeidung von Starvation -> verhinderung dass immer die gleiche TA zurückgesetzt wird -> merken wie oft eine TA bereits rückgesetzt wurde und ihr ggf. einen Freifahrtschein geben der eine erneute rücksetzung verhindert

• Mehrfache Zyklen: Falls eine TA in mehreren Zyklen vorkommt, macht es sinn diese rückzusetzen um mehrere Deadlocks auf einmal aufzulösen

1. Preclaiming

2. Zeitstempel

Transaktionen werden erst begonnen, wenn alle Sperrforderungen zur BOT erfüllt werden können

-> anfordern aller benötigter sperren vor beginn der Transaktion!

Die TA muss bereits zu beginn wissen, welche Sperren sie benötigt

-> schwierig bei z.b. if…else anweisungen da mehr sperren angefordert als tatsächlich benötigt…

Jede TA enthält einen Zeitstempel in monoton wachsender Reihenfolge (ältere TA hat kleineren Zeitstempel)

-> TA warten nicht mehr auf freigabe einer sperre sondern es wird nach einer von zwei strategien verfahren

T1 fordert Sperre an, die T2 hat (T1 wartet auf T2)

• wound wait:

  • T1 älter als T2 -> T2 wird abgebrochen und rückgesetzt, T1 erhält sperre

  • T1 jünger als T2 -> T1 wartet auf T2

• wait-die:

  • T1 älter als T2 -> T1 wartet auf Freigabe durch T2

  • T1 jünger als T2 -> T1 wird abgebrochen und zurückgesetzt

i.A. werden zu viele TA zurückgesetzt, da nicht immer ein DL auftreten würde

• Datensätze: einzelne Tupel sind kleinste Sperreinheit; falls viele Datensätze benötigt -> viele sperren

• Seiten

• Segmente: logische einheit mehrerer Seiten -> starke einschränkung der parallelität!

• Datenbasis: extremfall, aus der die serielle abarbeitung der Transaktionen folgt!

Falls z.B. eine TA eine Sperre auf eine Seite anfordern möchte, müssen alle Datensätze der Seite auf evtl. vorhandene Sperren überprüft werden. Dieses problem verschlimmer sich, je größer das sperrgranulat ist!

• zu groß: parallelität zu stark eingeschränkt

• zu klein: es müssen sehr viele sperren angefordert werden

Durch Einführen weiterer Sperrmodi (nicht mehr nur S und X)

multiple-granularity locking (MGL)

intentionssperren

Ursprünglich:

• NL: No Lock

• S: Lesesperre

• X: Schreibsperre

Intentinssperren:

• IS: weiter unten in hierarchie (auf kleinerem sperrgranulat) ist eine Lesesperre

• IX: weiter unten ist eine Schreibsperre

S kann man bei S und IS anfordern

X kann man nur bei NL anfordern

IS kann man bei NL, S, IS und IX anfordern

IX kann man bei NL, IS und IX anfordern

• anforderung: top down

  • Falls Knoten mit S oder IS gesperrt wird, müssen alle vorgänger in der Hierarchie mit IS oder IX gesperrt sein

  • Falls Knoten mit X oder IX gesperrt wird, müssen alle vorgänger mit IX gesperrt sein

• freigabe: bottom up

  • sperren werden nur freigegeben, falls TA nicht weiter unten noch gesperrt hat

Falls mehrere intentionale sperrungen auf einem Objekt liegen, wird immer die Höchste als Gruppenmodus angenommen. Dadurch muss man bei Sperranforderungen immer nur gegen den Gruppenmodus vergleichen

es gilt:

S > IS

IX > IS

Automatisches umschalten von einer niedrigeren Sperrgranularität auf eine höhere sobald eine bestimmte anzahl von sperren der kleineren Granularität angefordert wurden

Deadlocks