Verklemmungen (Deadlocks)

Ein schwerwiegendes Problem bei sperrbasierten Synchronisationsmethoden ist das Auftreten von Verklemmungen (englisch: deadlocks). Tabelle 13.12 zeigt ein Beispiel.

Schritt	T1	T2	Bemerkung
1.	BOT
2.	lockX(A)
3.		BOT
4.		lockS(B)
5.		read(B)
6.	read(A)
7.	write(A)
8.	lockX(B)		T1 muß warten auf T2
9.		lockS(A)	T2 muß warten auf T1
10.	...	...	Deadlock

Tabelle 13.12: Ein verklemmter Schedule

Eine Methode zur Erkennung von Deadlocks ist die Time - out -Strategie. Falls eine Transaktion innerhalb eines Zeitmaßes (z. B. 1 Sekunde) keinerlei Fortschritt erzielt, wird sie zurückgesetzt. Allerdings ist die Wahl des richtigen Zeitmaßes problematisch.

Eine präzise, aber auch teurere - Methode zum Erkennen von Verklemmungen basiert auf dem sogenannten Wartegraphen. Seine Knoten entsprechen den Transaktionen. Eine Kante existiert von T_i nach T_j, wenn T_i auf die Freigabe einer Sperre von T_j wartet. Bild 13.4 zeigt ein Beispiel.

Wartegraph mit zwei Zyklen

Es gilt der Satz: Die Transaktionen befinden sich in einem Deadlock genau dann, wenn der Wartegraph einen Zyklus aufweist.

Eine Verklemmung wird durch das Zurücksetzen einer Transaktion aufgelöst:

• Minimierung des Rücksetzaufwandes: Wähle jüngste beteiligte Transaktion.
• Maximierung der freigegebenen Resourcen: Wähle Transaktion mit den meisten Sperren.
• Vermeidung von Verhungern (engl. Starvation): Wähle nicht diejenige Transaktion, die schon oft zurückgesetzt wurde.
• Mehrfache Zyklen: Wähle Transaktion, die an mehreren Zyklen beteiligt ist.