Differences

This shows you the differences between two versions of the page.

--- uni:8:dbs2:synchronisation [2015-07-17 22:45] – created skrupellos
+++ uni:8:dbs2:synchronisation [2020-11-18 18:11] (current) – external edit 127.0.0.1
@@ Line 1: / Line 1: @@
 ====== Synchronisation ======
 ===== Pessimistische Synchronisation mit Sperren =====
 ==== Sperrprotokoll ====
-^               ^  Nicht \\ Konservativ  ^  \\ Konservativ  ^
+^               ^  Nicht \\ Konservativ (''/ *'') ^  \\ Konservativ (''| *'') ^
-^  Nicht Strikt |  ''%%/ \%%''  |  ''%%| \%%''  |
+^  Nicht Strikt (''* \'') |  ''%%/ \%%''  |  ''%%| \%%''  |
-^        Strikt |  ''%%/ |%%''  |  ''%%/ \%%''  |
+^        Strikt (''* |'') |  ''%%/ |%%''  |  ''%%| |%%''  |
 ==== Konsistenzstufen ====
@@ Line 18: / Line 17: @@
 | 3 | lang | lang |
-===== Sperrverfahren =====
+==== Sperrverfahren ====
-==== Verfahren ====
+=== Verfahren ===
-=== (Voll) ===
+== (Voll) ==
 ^    ^   X   ^
 ^  X |  (-)  |
-=== RX ===
+== RX ==
 ^    ^   R   ^   X   ^
 ^  R |  (+)  |  (-)  |
 ^  X |  (-)  |  (-)  |
-=== RUX ===
+== RUX ==
   * U: update/lesen
@@ Line 41: / Line 40: @@
   * U -> X: Möchte jetzt schreiben
-=== RAX ===
+== RAX ==
   * A: = U (update/lesen)
@@ Line 51: / Line 50: @@
 Übergänge:
   * A -> X: Möchte jetzt schreiben
-=== RIX ===
+== RIX ==
 Auf oberer Ebene (Tabelle):
 ^      ^   R   ^   X   ^   IR  ^   IX  ^  RIX  ^
@@ Line 73: / Line 74: @@
 Auf unterer Ebene (Tupel): RX/RUX/RAX
-=== RAC ===
+== RAC ==
   * **A** Änderung $V_\text{neu}$ im cache
   * **C** $V_\text{alt}$ wird noch von alten Lesern gelesen
@@ Line 84: / Line 86: @@
 Übergänge:
   * A -> C: Bei commit
-==== Eigenschaften ====
+=== 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