Verklemmungen (Deadlocks)

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

Schritt	T₁	T₂	Bemerkung
1.	BOT
2.	lockX( A )
3.		BOT
4.		lockS( B )
5.		read( B )
6.	read( A )
7.	write( A )
8.	lockX( B )		T₁ muß warten auf T₂
9.		lockS( A )	T₂ muß warten auf T₁
10.	...	...	$\Rightarrow$ Deadlock

Tabelle 12.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 12.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.