====== 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 | (X) | (X) |  (X) | kaskadierte freies rücksetzen | Parallele Leser |
|  RUX | (V) | (V) |  (X) |  | Parallele Leser |
|  RAX | (X) | (V) |  (X) |  | 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