Deadlock

Wenn sich mehrere Threads synchronisieren, können sie in einen Zustand gelangen, der Deadlock genannt wird. Für das Auftreten eines Deadlocks sind folgende Bedingungen hinreichend und notwendig:

(1) Threads können weitere Ressourcen anfordern, wenn sie bereits Ressourcen besitzen,

(2) besitzt ein Thread eine Ressource, kann sie nicht entzogen werden (der Thread gibt die Ressourcen erst zurück, z.B. wenn er endet oder ein kritisches Gebiet verlässt),

(3) die Ressourcen sind entweder frei oder befinden sich im exklusiven Besitz eines Threads und

(4) der Wartegraph enthält mindestens einen Kreis.

Der Wartegraph repräsentiert die Wartebeziehungen zwischen den Threads, die im Graphen durch die Knoten dargestellt werden. Eine gerichtete Kante von zwischen zwei Knoten X und Y ist dann im Graphen enthalten, wenn der Thread X auf eine Ressource wartet, die der Thread Y besitzt.

Weil im Falle eines Deadlocks keiner der beteiligten Threads seine Arbeit fortsetzen und so normal terminieren kann, müssen Deadlocks vermieden werden. Dieses Ziel kann erreicht werden, in dem mindestens eine der oben genannten Bedingungen unmöglich gemacht wird.
 
(1) Threads können weitere Ressourcen anfordern, wenn sie bereits Ressourcen besitzen: ist unmöglich, wenn die Threads schon bei ihrem Start alle benötigten Betriebsmittel anfordern müssen. Verwirklicht ist diese Strategie beim konservativen Two-Phase Locking.
 
(2) Der Entzug der Betriebsmittel kann z.B. durch Abbruch und nachfolgenden Neustart des Threads realisiert werden. Verwendet wird diese Technik vor allem im Datenbankbereich, da dort die Aktionen eines Threads (in diesem Kontext Transaktion) rückgängig gemacht werden können.
  
(3) Die Art des Zugriffs (exklusiv oder gemeinsam) ist durch die Ressource vorgegeben und kann normalerweise nicht geändert werden.
 
(4) Zyklen im Wartegraphen können dann vermieden werden, wenn die Ressourcen hierarchisiert werden. Dazu wird eine Ordnung über den Betriebsmitteln definiert. Wenn bezüglich dieser Ordnung für zwei Betriebsmittel X und Y gilt X > Y, dann müssen alle Threads, die sowohl auf X als auch auf Y zugreifen wollen zuerst X und dann Y anfordern. Unter diesen Umständen können keine Kreise im Wartegraphen auftreten.
 
Eine weitere Möglichkeit ist der deadlockfreie Systemaufbau, bei dem z.B. keine Wartebeziehungen auftreten (Timestamp Ordering).