uni:8:dbs2:synchronisation
Table of Contents
Synchronisation
Pessimistische Synchronisation mit Sperren
Sperrprotokoll
| Nicht Konservativ ( / *) | Konservativ ( | *) |
|
|---|---|---|
Nicht Strikt (* \) | / \ | | \ |
Strikt (* |) | / | | | | |
Konsistenzstufen
- kurz
- lang: Bis EOT
| Konsistenzstufe | Schreibsperre | Lesesperre |
|---|---|---|
| 0 | kurz | - |
| 1 | lang | - |
| 2 | lang | kurz |
| 3 | lang | lang |
Sperrverfahren
Verfahren
(Voll)
| X | |
|---|---|
| X |  |
RX
| R | X | |
|---|---|---|
| R |  | |
| X | | |
RUX
- U: update/lesen
| R | U | X | |
|---|---|---|---|
| R | | | |
| U | | | |
| X | | | |
Übergänge:
- U → X: Möchte jetzt schreiben
RAX
- A: = U (update/lesen)
| R | A | X | |
|---|---|---|---|
| R | | | |
| A | | | |
| X | | | |
Übergänge:
- A → X: Möchte jetzt schreiben
RIX
Auf oberer Ebene (Tabelle):
| R | X | IR | IX | RIX | |
|---|---|---|---|---|---|
| R | | | | | |
| X | | | | | |
| IR | | | | | |
| IX | | | | | |
| RIX | | | | | |
| Überprüfung auf unterer Ebene nötig |
|---|
- Obere Ebene hat …
- R
- X
- Untere Ebene hat …
- R ⇒ IR
- X ⇒ IX
- Obere Ebene hat R, untere Ebene hat X …
- RIX (mix aus R und IX)
Auf unterer Ebene (Tupel): RX/RUX/RAX
RAC
- A Änderung $V_\text{neu}$ im cache
- C $V_\text{alt}$ wird noch von alten Lesern gelesen
| R | A | C | |
|---|---|---|---|
| R | | | |
| A | | | |
| C | | | |
Übergänge:
- A → C: Bei commit
Eigenschaften
| Verfahren | Kein Verhungern | Deadlockfrei selbes Obj. | Deadlockfrei anderes Obj. | Schedule | Bemerkung |
|---|---|---|---|---|---|
| RX |  | | | kaskadierte freies rücksetzen | Parallele Leser |
| RUX |  | | | Parallele Leser | |
| RAX | | | | Zwar nach kein verklemmen, dafür verhungern für mehr Parallelität |
Deadlocks
Können entweder
- Vermeiden werden (konservatives 2PL/precaiming) oder
- Erkannt werden
- Wartegraph (Teuer)
- Time-Out
Wartegraph
Ich → warte auf X
Time-Out
| Jüngere TA hält Sperre | Ältere TA hält Sperre | |
|---|---|---|
| Wound-Wait | ⇒ ältere TA “verwundet” (Wound) jüngere TA; jüngere TA wird zurückgesetzt! | ⇒ jüngere TA “wartet” (Wait) |
| Wait-Die | ⇒ ältere TA “wartet” (Wait) | ⇒ ältere TA “tötet” (Die) jüngere TA; jüngere TA wird zurückgesetzt! |
- Es wird immer die Jüngere getötet
- Es wird immer die anfragende warten
- Name: <Jüngere TA hält Sperre>-<Ältere TA hält Sperre>
Pessimistische Synchronisation mit Zeitstempeln
- Jedes Objekt hat Zeitstepel der jüngsten TA pro read/write
- Beim Zugriff prüfen:
| Leser | älter als jüngster Schreiber | des Objekts ⇒ Leser zurücksetzen | $TS(T_i) < \text{writeTS}(O)$ |
| Schreiber | älter als jüngster Schreiber oder Leser | des Objekts ⇒ Schreiber zurücksetzen | $TS(T_i) < \text{writeTS}(O) \vee TS(T_i) < \text{readTS}(O)$ |
Optimistische Synchronisation mit Zeitstempeln
- Änderungen im RAM
- RS und WS der angefassten Objekte pro TA speichern
- Bei Commit validieren, dann raus schreiben
BOCC
Mein RS mit WS, beendeter TA (während meiner TA)
Bei Konflikt:
- Nur ich kann noch zurückgesetzt werden
BOCC+
FOCC
Mein RS mit WS, laufender TA
Bei Konflikt:
- Kill: Ich kill die laufenden TAs
- Die: I die
uni/8/dbs2/synchronisation.txt · Last modified: 2020-11-18 18:11 by 127.0.0.1