TDO-Referat - Lösungswege zu den Concurrency-Problemen referat

xl182g7156illv 17182gxy56ilv9x

1 Concurrency-Probleme 1

1.1 Locking zur Lösung der Probleme 1

1.2 Das lost update Problem 2

1.3 Das uncommited dependency Problem 3

1.4 Das inconsistent analysis Problem 4

1.5 Problem Deadlock 5

1.6 Techniken zur Vermeidung/Lösung von Deadlocks 5

1.6.1 Two Phase Locking 6

1.6.2 Zeitmarkenverfahren (Timestamp technique) 6

1.6.3 Transaktion Retry 6

2 Zwei-Phasen-Commit (Two Phase Commit) 7

3 Fragen 8

Concurrency-Probleme

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.

xl182g7156illv 17182gxy56ilv9x

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.

xl182g7156illv 17182gxy56ilv9x

Aus diesen zwei Aussagen ergibt sich folgende Wertetabelle

gefordertes Lock

gesetztes Lock von Transaktion A

von Transaktion B	X	S	kein
X	wait B	wait B	OK
S	wait B	OK	OK

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:

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

xl182g7156illv 17182gxy56ilv9x

eine Anfrage von Transaktion B für ein S-Lock auf R wird erlaubt.

Das lost update Problem

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

Transaktion A	Zeit	Transaktion B
-	\|	-
lese Satz R	t1	-
xl182g7156illv 17182gxy56ilv9x	\|	xl182g7156illv 17182gxy56ilv9x
-	t2	lese Satz R
xl182g7156illv 17182gxy56ilv9x	\|	xl182g7156illv 17182gxy56ilv9x
ändere Satz R	t3	-
xl182g7156illv 17182gxy56ilv9x	\|	xl182g7156illv 17182gxy56ilv9x
-	t4	ändere Satz R
-	¯	-

Lösung mittels Locking:

Transaktion A	Zeit	Transaktion B
-	\|	-
lese Satz R zum Ändern (meldet X-Lock auf Satz R an)	t1 \|	-
xl182g7156illv 17182gxy56ilv9x	\|	xl182g7156illv 17182gxy56ilv9x
-	t2 \|	lese Satz R zum Ändern (möchte X-Lock auf Satz R)
xl182g7156illv 17182gxy56ilv9x	\|	xl182g7156illv 17182gxy56ilv9x
ändere Satz R	t3	wartet auf Freigabe von Satz R durch A
xl182g7156illv 17182gxy56ilv9x	\|	xl182g7156illv 17182gxy56ilv9x
Synchpoint; Ende Transaktion (gibt Satz R wieder frei)	t4 \|	wartet auf Freigabe von Satz R durch A
xl182g7156illv 17182gxy56ilv9x	\|	xl182g7156illv 17182gxy56ilv9x
-	t5 \|	lese Satz R zum Ändern (meldet X-Lock auf Satz R an)
-	¯	-

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:

Transaktion A	Zeit	Transaktion B
-	\|	-
lese Satz R (meldet S-Lock auf Satz R an)	t1 \|	-
xl182g7156illv 17182gxy56ilv9x	\|	xl182g7156illv 17182gxy56ilv9x
-	t2 \|	lese Satz R (meldet S-Lock auf Satz R an)
xl182g7156illv 17182gxy56ilv9x	\|	xl182g7156illv 17182gxy56ilv9x
ändere Satz R (möchte X-Lock auf Satz R)	t3 \|	-
xl182g7156illv 17182gxy56ilv9x	\|	xl182g7156illv 17182gxy56ilv9x
wartet auf Freigabe von Satz R durch B	t4 \|	ändere Satz R (möchte X-Lock auf Satz R)
xl182g7156illv 17182gxy56ilv9x	\|	xl182g7156illv 17182gxy56ilv9x
wartet auf Freigabe von Satz R durch B	t5	wartet auf Freigabe von Satz R durch A
xl182g7156illv 17182gxy56ilv9x	\|	xl182g7156illv 17182gxy56ilv9x
wartet auf Freigabe von Satz R durch B	¯	wartet auf Freigabe von Satz R durch A

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.

Das uncommited dependency Problem

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

Transaktion A	Zeit	Transaktion B
-	\|	-
-	t1	ändere Satz R
xl182g7156illv 17182gxy56ilv9x	\|	xl182g7156illv 17182gxy56ilv9x
lese Satz R	t2	-
xl182g7156illv 17182gxy56ilv9x	\|	xl182g7156illv 17182gxy56ilv9x
-	t3	Rollback

Lösung mittels Locking:

Transaktion A	Zeit	Transaktion B
-	\|	-
-	t1 \|	ändere Satz R (meldet X-Lock auf Satz an)
xl182g7156illv 17182gxy56ilv9x	\|	xl182g7156illv 17182gxy56ilv9x
lese Satz R (möchte S-Lock auf Satz R)	t2 \|	-
xl182g7156illv 17182gxy56ilv9x	\|	xl182g7156illv 17182gxy56ilv9x
wartet auf Freigabe von Satz R durch B	t3 \|	Rollback; Synchpoint; Ende Transaktion (gibt Satz R wieder frei)
xl182g7156illv 17182gxy56ilv9x	\|	xl182g7156illv 17182gxy56ilv9x
lese Satz R (meldet S-Lock auf Satz R an)