Verklemmungen (Deadlocks)

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

Schritt	$T_1$	$T_2$	Bemerkung
1.	BOT
2.	lockX($A$)
3.		BOT
4.		lockS($B$)
5.		read($B$)
6.	read($A$)
7.	write($A$)
8.	lockX($B$)		$T_1$ muß warten auf $T_2$
9.		lockS($A$)	$T_2$ muß warten auf $T_1$
10.	...	...	$\Rightarrow 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. Abbildung 13.4 zeigt ein Beispiel.

Abbildung 13.4: 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.