1 Concurrency-Probleme
1.1 Locking zur Lösung der Probleme
1.2 Das lost update Problem
1.3 Das uncommited dependency Problem
1.4 Das inconsistent analysis Problem
1.5 Problem Deadlock
1.6 Techniken zur Vermeidung/Lösung von DeadlocksLocking
1.6.2 Zeitmarkenverfahren (Timestamp technique)
1.6.3 Transaktion Retry
2 Zwei-Phasen-Commit (Two Phase Commit)

1 Concurrency-Probleme
1.1 Locking zur Lösung der Probleme

Die Grundidee des Locking ist es, alle Objekte, welche von einer Transaktion benötigt werden, mit einer entsprechenden Marke (diese wird als Lock bzw. Sperre bezeichnet) zu versehen, welche anderen Transaktionen anzeigt, daß dieses Objekt derzeit nicht verfügbar ist.

2 Arten von Locks werden unterschieden:

X-Lock (exclusive Locks): Wird durch eine Transaktion A ein Datensatz verändert, so wird dieser für alle anderen Transaktionen gesperrt, bis die Transaktion den Datensatz wieder freigibt. Diese Sperre verhindert, daß andere Transaktionen den Datensatz lesen oder verändern.

S-Lock: (share Locks): Wird durch eine Transaktion ein Datensatz abgefragt, so wird dieser Datensatz für X-Locks gesperrt d.h. daß andere Transaktionen den Datensatz nicht ändern dürfen, Lesezugriffe sind jedoch ohne weiteres erlaubt.

Bsp.: Angenommen Transaktion A hat einen Datensatz R für ein Änderung (X-Lock) gesperrt, so wird eine Anfrage von Transaktion B für einen Lock auf denselben Datensatz (egal welchen Typs) diese in einen Wartezustand führen.

Bsp.: Hat aber die Transaktion A ein S-Lock auf den Datensatz R, so muß man bei einer Anfrage eines Locks von Transaktion B auf R zwei Fälle unterscheiden:

a) bei Anfrage von Transaktion B für ein X-Lock auf R gelangt diese in einen Wartezustand bis der Datensatz wieder freigegeben wird.
b) eine Anfrage von Transaktion B für ein S-Lock auf R wird erlaubt.

1.2 Das lost update Problem

Das Problem besteht darin, daß „ältere“ Änderungen durch zeitlich verschobene Zugriffe verloren gehen können.

Mit dem Einlesen des Satzes R zum Zeitpunkt t1 wird dieser mit einem X-Lock gesperrt. Dadurch werden alle weiteren Zugriffe (z.B. Leseanforderung zum Zeitpunkt t2) gesperrt. Erst nach Freigabe der Sperren (Zeitpunkt t4) kann der Datensatz weiter verwendet werden.

Verwendet man allerdings an Stelle der X-Locks in obigem Beispiel S-Locks so treten neue Probleme auf.

Da Transaktion A beim Lesen seine Änderungsabsicht noch nicht bekanntgibt, wird Transaktion B zum Zeitpunkt t2 der Lesezugriff nicht verwehrt. Die in der Folge angeforderten X-Locks versetzen beide Transaktionen in den Wartezustand, da das von der gegnerischen Transaktion gesetzte S-Lock kein X-Lock zuläßt. Diese Situation bezeichnet man als Deadlock. Die Lösung dieses neuen Problems wird später erklärt.



1.3 Das uncommited dependency Problem

Dieses Problem basiert auf der Verwendung von unbestätigten, veränderten Daten und diese müssen Änderungen zurückgenommen werden.

Dadurch, daß die Transaktion A auf die Freigabe des von der Transaktion B gesperrten Datensatzes R wartet, kann sie zu keinem Zeitpunkt (sowohl bei einem Lesen als auch beim Verändern von Datensätzen) mit falschen Daten rechnen.

1.4 Das inconsistent analysis Problem

Bei diesem Problem arbeitet ein Programm mit Daten, die aus einer kurzfristig inkonsistenten Datenbank kommen.
Auch hier tritt wieder das Problem des Deadlocks auf.

1.5 Problem Deadlock

An den zwei vorherigen Beispielen kann man ersehen, daß das Locking nicht alle Probleme löst. Durch das gegenseitige Locking, warten zwei Transaktionen auf die gegenseitige Freigabe eines Datensatzes, was sich dadurch bemerkbar macht, daß keine Transaktion weiter arbeitet.

Dieses Problem kann nur dann gelöst werden, wenn eine der beiden Transaktionen zurückgenommen wird. Dadurch kann die andere Transaktion ihre Arbeit beenden, worauf die abgebrochene Transaktion neu gestartet wird.

1.6 Techniken zur Vermeidung/Lösung von Deadlocks

Erforderliche Eigenschaften von Transaktionen:


1. Atomicity: Eine Transaktion ist eine elementarer Prozeß. Er wird entweder vollständig oder gar nicht durchgeführt.


2. Konsistenzkriterium: Eine korrekte Durchführung einer Transaktion muß die Datenbank wieder in einen konsistenten Zustand versetzt


3. Dauerhaftigkeit: Wurden von einer Transaktion Änderungen durchgeführt und bestätigt, so gehen diese auch durch einen späteren Fehler nicht mehr verloren.


4. Isolation: Alle Änderungen während einer Transaktion dürfen für andere Transaktionen erst nach der Bestätigung sichtbar werden.


5. Serialisierbarkeit: Man spricht von serialisierbaren Transaktionen, wenn ein Datenbankzustand, der durch parallel arbeitende Transaktionen erreicht wurde, auch durch die serielle Abarbeitung der gleichen Transaktionen erreicht würde.

Es wird vorausgesetzt, daß die einzelnen Transaktionen voneinander unabhängig sind. Eine Abhängigkeit wäre gegeben, wenn z.B. eine Transaktion A vor einer Transaktion B unbedingt laufen müßte. Damit ist zwar keine beliebige Hintereinanderausführung mehr möglich, aber es ist ein bestimmter, zeitlicher Ablauf gegeben.


Punkt 1 und 2 sind in der Definition der Transaktion enthalten. Punkt 3 wird durch Recovery-Techniken im Falle eines Fehlers gewährleistet.


Zur Einhalten der im Punkt 4 und 5 geforderten Serialisierbarkeit wird das Two-Phase-Locking Protokoll eingesetzt

1.6.1 Two Phase Locking


Wenn eine Transaktion einen gesperrten Datensatz wieder frei gibt, aber ihn danach noch einmal benötigt und ihn somit wieder sperren muß, muß erwartet werden das die Daten schon von einer anderen Transaktion geändert wurden. Um die daraus resultierenden Probleme (uncommitted dependency) zu vermeiden, werden folgende Forderungen aufgestellt:


· Vor jeder Bearbeitung eines Datensatzes wird dieser gesperrt


· Dieser Datensatz wird erst wieder freigegeben, wenn er für die restliche Transaktion nicht mehr benötigt wird.


Eine Transaktion, die beiden Regeln entspricht, arbeitet nach dem „two Phase Locking Protocol (2PL)“, und erfüllt die Forderung der Serialisierbarkeit.

1.6.2 Zeitmarkenverfahren (Timestamp technique)


Jede Transaktion erhält bei ihrem Start einen Zeitstempel. Die Abarbeitung erfolgt streng noch dem Prinzip First in – First out (FIFO), d.h. streng nach der Startreihenfolge. Tritt ein Konflikt auf, so wird jene Transaktion neu gestartet die den Konflikt auslöste. Ein Konflikt entsteht z.B. wenn eine „ältere“ Transaktion eine Leseanforderung für einen bestimmten Datensatz absetzt, der durch eine „jüngere“ verändert werden soll. Dadurch erhält der Benutzer immer die aktuellen und geänderten Daten. Dieses Verfahren dient unter anderem zur Vermeidung von Deadlocks.

1.6.3 Transaktion Retry

Nach Erkennung eines Deadlocks muß eine der Transaktionen abgebrochen und zu einem späteren Zeitpunkt neu gestartet werden. Für die Entscheidung welche der Transaktionen abzubrechen ist gibt es verschiedene Verfahren:


· Wait-Die Protokoll

· Wound-Wait Protokoll


Bei beiden Verfahren wird jeweils die „jüngere“ Transaktion zurückgenommen und zu einem späteren Zeitpunkt ausgeführt. Dazu ist erforderlich, daß jede Transaktion einen eindeutigen Zeitstempel, am Beginn erhält.


Wenn die Transaktion A einen von der Transaktion B bereits gesperrten Datensatz sperren will, passiert folgendes:


· Wait-Die: falls A älter ist als B wartet A, sonst wird A zurückgenommen

· Wound-Wait: falls A jünger ist als B wartet A, sonst wird B zurückgenommen

Bei diesem System ist sichergestellt, daß kein Deadlock entstehen kann, da jede Transaktion in einer endlichen Zeit und nach endlich vielen Wiederholungen ausgeführt wird. Das Schlimmste was passieren kann, ist daß der Rechner zu langsam ist und jede neu ankommende Transaktion länger abläuft als ihr Vorgänger.

2 Zwei-Phasen-Commit (Two Phase Commit)


Das 2-Phasen-Commit wird eingesetzt, wenn mehrere Systeme (z.B.: hierarchisches und relationales DB-System) gemeinsam synchronisiert werden müssen. Hier tritt das Problem auf, daß zwischen dem Commit für System1 und dem Commit für System2 ein Fehler auftritt. Beim automatischen Recovery würde in diesem Fall System2 zurückgesetzt werden, die Daten für System1 bleiben bestätigt. Dadurch stimmen die beiden Systeme nicht mehr überein.



1. System befindet sich in einem konsistenten Zustand


2. Eine Applikation beginnt mit Änderungsanforderungen. Diese Änderungen werden an den Koordinator geschickt. Dieser leitet sie zeitverzögert an die jeweilige Datenbank.


3. Applikation hat Änderungen abgeschlossen und setzt einen Synchpoint.


4. Darauf leitet der Koordinator Phase 1 von Commit ein. Dazu schickt er eine entsprechende Anforderung an alle Datenbanksysteme.


5. Die einzelnen Datenbanksysteme markieren die Commit-Anforderung in ihrem Logfile und bestätigen anschließend dem Koordinator das Commit.


6. Nach Eintreffen aller Commit-Bestätigungen protokolliert der Koordinator dies in seinem Logfile und leitet anschließend Commit Phase 2 ein.


7. Auch Phase 2 muß von den einzelnen Datenbanksystemen bestätigt werden.


8. Nach Erhalt aller Bestätigungen und einem entsprechenden Protokolleintrag meldet der Koordinator einen neuen konsistenten Zustand der Datenbank.



Treten bis zum Zeitpunkt des ersten Logeintrags des Koordinators Fehler auf oder meldet ein Datenbanksystem einen nicht erfolgreichen Abschluß, so fordert der Koordinator alle Datenbanksysteme zu einem Rollback auf. Tritt hingegen nach diesem Zeitpunkt ein Fehler auf, so werden automatisch alle noch ausständigen Phase 2 Commits durchgeführt.

3 Fragen


Wie lauten die zwei Locks, und welche gleichzeitigen Transaktionen sind erlaubt?


X-Lock (exclusive Locks): Wird durch eine Transaktion A ein Datensatz verändert, so wird dieser für alle anderen Transaktionen gesperrt, bis die Transaktion den Datensatz wieder freigibt. Diese Sperre verhindert, daß andere Transaktionen den Datensatz lesen oder verändern.


S-Lock: (share Locks): Wird durch eine Transaktion ein Datensatz abgefragt, so wird dieser Datensatz für X-Locks gesperrt d.h. daß andere Transaktionen den Datensatz nicht ändern dürfen, Lesezugriffe sind jedoch ohne weiteres erlaubt.



Was ist ein Deadlock, und wie kann er gelöst werden?


Durch das gegenseitige Locking, warten zwei Transaktionen auf die gegenseitige Freigabe eines Datensatzes, was sich dadurch bemerkbar macht, daß keine Transaktion weiter arbeitet.

Dieses Problem kann nur dann gelöst werden, wenn eine der beiden Transaktionen zurückgenommen wird. Dadurch kann die andere Transaktion ihre Arbeit beenden, worauf die abgebrochene Transaktion neu gestartet wird.

4 Concurrency-Probleme
4.1 Locking zur Lösung der Probleme


Zwei Arten von Locks:

· X-Lock (Exclusive Lock)

· S-Lock (Share Lock)
4.5 Deadlock

4.6 Techniken zur Vermeidung/Lösung von Deadlocks


Erforderliche Eigenschaften von Transaktionen:


· Atomicity

· Konsistenzkriterium

· Dauerhaftigkeit

· Isolation

· Serialisierbarkeit



4.6.1 Two Phase Locking

4.6.2 Zeitmarkenverfahren

4.6.3 Transaktion Retry


Zwei Protokolle:

· Wait-Die Protokoll

· Wound-Wait Protokoll

Anwendung wenn mehrere verschiedene Datenbanksysteme synchronisiert werden müssen.