^ ^ Nicht \\ Konservativ (''/ *'') ^ \\ Konservativ (''| *'') ^^ Nicht Strikt (''* \'') | ''%%/ \%%'' | ''%%| \%%'' |^ Strikt (''* |'') | ''%%/ |%%'' | ''%%| |%%'' |
* kurz
* lang: Bis EOT
^ Konsistenzstufe ^ Schreibsperre ^ Lesesperre ^
| 0 | kurz | - |
| 1 | lang | - |
| 2 | lang | kurz |
| 3 | lang | lang |
^ ^ X ^
^ X | (-) |
^ ^ R ^ X ^
^ R | (+) | (-) |
^ X | (-) | (-) |
* U: update/lesen
^ ^ R ^ U ^ X ^
^ R | (+) | (-) | (-) |
^ U | (+) | (-) | (-) |
^ X | (-) | (-) | (-) |
Übergänge:
* U -> X: Möchte jetzt schreiben
* A: = U (update/lesen)
^ ^ R ^ A ^ X ^
^ R | (+) | (+) | (-) |
^ A | (+) | (-) | (-) |
^ X | (-) | (-) | (-) |
Übergänge:
* A -> X: Möchte jetzt schreiben
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
* **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
^ 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 |
Können entweder
* **Vermeiden** werden (konservatives 2PL/precaiming) oder
* **Erkannt** werden
* Wartegraph (Teuer)
* Time-Out
Ich -> warte auf X
^ ^ 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>
* 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)$ |
* Änderungen im RAM
* RS und WS der angefassten Objekte pro TA speichern
* Bei Commit validieren, dann raus schreiben
Mein RS mit WS, beendeter TA (während meiner TA)
Bei Konflikt:
* Nur ich kann noch zurückgesetzt werden
Mein RS mit WS, laufender TA
Bei Konflikt:
* Kill: Ich kill die laufenden TAs
* Die: I die
