prev up next

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:


prev up next