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 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 Ti nach Tj, wenn Ti auf die Freigabe einer Sperre von Tj 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:


prev up next