„Eine Menge von Prozessen befindet sich in einem Deadlock-Zustand, wenn jeder Prozess aus der Menge auf ein Ereignis wartet, das nur ein anderer Prozess aus der Menge auslösen kann.“ 2

Schließlich können auch Deadlocks in indirekter Abhängigkeit entstehen, also durch eine Kette von Abhängigkeiten, wie in Abbildung 1.

Natürlich ließen sich noch viel kompliziertere Abhängigkeiten darstellen.

2.2 Unterbrechbare/ununterbrechbare Ressourcen

Bei der Entstehung und Behandlung von Deadlocks muss man zuerst die Ressourcen in unterbrechbare und ununterbrechbare Ressourcen unterteilen. Unterbrechbare Ressourcen sind z.B. der Prozessor und der Hauptspeicher. Ununterbrechbare Ressourcen sind z.B. Drucker, Scanner, CD-Brenner, deren Unterbrechung bzw. das Entziehen der Ressource nicht möglich ist, ohne das Arbeitsergebnis, z.B. einen CD-Rohling, zu zerstören. Deadlocks stehen immer im Zusammenhang mit ununterbrechbaren Ressourcen, denn wenn unterbrechbare Ressourcen an einem Deadlock beteiligt wären, ließe sich dieser normalerweise durch eine Neuzuweisung der Ressource beheben. 3

2.3 Anforderung von Ressourcen

Wenn Ressourcen verwendet werden, besteht deren Nutzung immer aus den Teilschritten:

1. anfordern 2. benutzen 3. freigeben. 4

Benötigt ein Prozess Ressourcen, wird er immer alle drei Teilschritte ausführen, insbesondere Schritt 3 darf nicht vergessen werden. Benötigen mehrere Prozesse(P1, P2) mehrere Ressourcen(R1, R2) und allokieren diese in derselben Reihenfolge P1(R1, R2), P2(R1,R2), kann es nicht zu einer Verklemmung kommen, da die Ressourcen hintereinander allokiert werden. Der Tabelle 1 kann man entnehmen, wie durch die gleiche Reihenfolge eine wechselseitige Allokierung beider Ressourcen verhindert wird, da R1 und R2 immer nur von einem der beiden Prozesse gleichzeitig allokiert werden kann.

² Tanenbaum, A. (2002), S. 181.

³ Vgl. ebenda, S. 178.

⁴ Vgl. ebenda, S.179.

- 2 -

Dagegen kann man der Tabelle 2 entnehmen, dass es in der Konstellation, in welcher gleichzeitig R1 und R2 angefordert werden, sehr wohl ein Deadlock möglich ist. Im Schritt 02 werden die Ressourcen R1 und R2 jeweils dem anderen Prozess zur Verfügung gestellt und nun warten beide Prozesse im Schritt 03 auf die Freigabe der wechselseitig belegten Ressourcen. Dieser kleine Unterschied im Programmierstil kann bereits große Auswirkungen auf die Stabilität der Programme haben. Wenn man sich die Tabelle 1 genauer ansieht, erkennt man auch eine erste Schwäche dieses Vorgehens: Die Parallelität der Prozesse leidet darunter. Das Problem würde sich mit jeder weiteren gleichzeitig benötigten Ressource noch verschärfen. 5

2.4 Vorraussetzungen für Deadlocks

„Nach Coffman et al. (1971) müssen für einen Deadlock folgende vier Voraussetzungen erfüllt sein:

1. Wechselseitiger Ausschluss: Jede Ressource ist entweder verfügbar oder genau einem Prozess zugeordnet.

2. Hold-and-wait-Bedingung: Prozesse, die schon Ressourcen reserviert haben, können noch weitere Ressourcen anfordern.

3. Ununterbrechbarkeit: Ressourcen, die einem Prozess bewilligt wurden, können diesem nicht gewaltsam wieder entzogen werden. Der Prozess muss sie explizit freigeben.

4. Zyklische Wartebedingung: Es muss eine zyklische Kette von Prozessen geben, von denen jeder auf eine Ressource wartet, die dem nächsten Prozess in der Kette gehört.

Alle vier Bedingungen müssen gleichzeitig erfüllt sein, damit ein Deadlock entstehen kann. Wenn eine fehlt, ist ein Deadlock unmöglich.“ 6

⁵ Vgl. Tanenbaum, A. (2002), S. 179-181.

⁶ Ebenda, S. 181.

- 3 -

2.5 Modellierung von Deadlocks

Durch Belegungs-Anforderungs-Graphen ist es möglich Deadlocks grafisch darzustellen. Zuerst hat dies Holt (1972) gezeigt. Dafür verwendete er, wie in Abbildung 2, Kreise für Prozessknoten und Quadrate für Ressourcen. Eine Kante bzw. Pfeil von einem Prozessknoten (P1) zu einer Ressource bedeutet, dass eine Ressource von einem Prozess angefordert wurde und von ihm belegt ist. Die umgekehrte Pfeilrichtung (P2) bedeutet, dass ein Prozess auf eine Ressource wartet. 7

In Abbildung 3 ist eine klassische Deadlock-Situation dargestellt. P1 belegt R1 und fordert R2, P2 belegt R2 und fordert R1.

3 Umgang mit Deadlocks

3.1 Deadlock ignorieren

Am einfachsten ist es, gar nichts zu tun und so zu tun, als ob das Problem nicht existiere (Vogel-Strauß-Algorithmus). Dieses Vorgehen macht dann Sinn, wenn die Eintrittswahrscheinlichkeit bzw. die Eintrittshäufigkeit eines Deadlocks geringer ist als die Störung des Systems durch Abstürze wegen eines Programmier-, Compilerfehlers oder wegen Hardwareausfällen oder anderen Fehlerursachen. Denn dann lohnt sich der Aufwand zur Deadlockvermeidung nicht und die damit verbundenen Einbußen in der Geschwindigkeit des Systems. ⁸ Letztendlich kann die Entscheidung für diese Vorgehensweise auch durch eine Kosten-Nutzen-Analyse getroffen werden und wird auch in Windows und Unix sinnvoll angewendet.

3.2 Deadlocks erkennen und beheben

Mit diesem Konzept will man auch keine Deadlocks verhindern. Viel wichtiger ist hier die Frage, wie erkenne ich diese und wie gehe ich dann mit den Deadlocks um, also wie behebe ich behebe sie. Wie in Abbildung 3 bereits dargestellt, ist ein Deadlock ein Zyklus in einem Belegungs-Anforderungs-Graphen. ⁹ Tanenbaum beschreibt in seinem Buch einen Algorithmus ¹⁰ , welcher jeden Knoten einzeln untersucht, indem er ihn als Wurzel eines Suchbaumes behandelt und rekursiv durchläuft. Endet er wieder beim Ursprungsknoten, hat er keinen Zyklus gefunden. Trifft er auf einen Knoten zweimal, endet der Algorithmus und der Deadlock wurde gefunden. Nun kann der Deadlock durch drei Varianten behoben werden.

⁷ Vgl. Tanenbaum, A. (2002), S. 182.

⁸ Vgl. ebenda, S. 185f.

⁹ Vgl. http://www.wi.fh-fensburg.de/erkennen_riggert.html, Stand 14.05.2009.

¹⁰ Siehe Tanenbaum, A. (2002), S.187.

- 4 -