Deadlock (Informatik)

Deadlock oder Verklemmung bezeichnet in der Informatik einen Zustand, bei dem eine zyklische Wartesituation zwischen mehreren Prozessen auftritt, wobei jeder beteiligte Prozess auf die Freigabe von mindestens einem Betriebsmittel (einer Ressource) wartet, das ein anderer beteiligter Prozess bereits exklusiv belegt hat. Eine andere Form der Blockierung von Prozessen ist der Livelock.

Der Zustand eines Deadlocks kann als eine Menge von Prozessen definiert werden, in dem sich ein Deadlock befindet, sofern jeder dieser Prozesse auf ein Ereignis wartet, das nur ein anderer Prozess aus dieser Menge verursachen kann.

Vier Prozesse (Fahrzeuge auf blauen Linien) konkurrieren um ein Betriebsmittel (Kreuzung = grauer Kreis). Es gilt die Rechts-vor-Links-Regel. Ein Deadlock tritt auf, wenn alle vier Prozesse das Betriebsmittel gleichzeitig belegen bzw. sperren (schwarze Linien). Die Verklemmung kann aufgelöst werden, indem man die Symmetrie bricht.

Allgemeines

Beispielsweise kann einem Prozess π₁ der Bildschirm zugeteilt worden sein. Gleichzeitig benötigt π₁ allerdings den Drucker. Auf der anderen Seite ist der Drucker dem Prozess π₂ zugeteilt, der wiederum den Bildschirm fordert. Ein Beispiel für eine Verklemmung aus dem realen Leben ist eine Straßenkreuzung, an der von allen vier Seiten Autos gekommen sind und nun (die Regel rechts vor links vorausgesetzt) darauf warten, dass das jeweils rechts wartende Auto zuerst fährt. Ein weiteres Beispiel ist das Philosophenproblem.

Nach Coffman et al. sind die folgenden vier Bedingungen hinreichend für die Möglichkeit einer Verklemmung:

1. Die Betriebsmittel werden ausschließlich durch die Prozesse freigegeben (Da Ressourcenzugriff eines Prozesses nicht unterbrochen werden kann. No Preemption).
2. Die Prozesse fordern Betriebsmittel an, behalten aber zugleich den Zugriff auf andere (Hold and Wait).
3. Der Zugriff auf ein Betriebsmittel ist exklusiv, d. h. nur einem einzigen Prozess wird der Zugriff auf ein Betriebsmittel gestattet (Mutual Exclusion).
4. Mindestens zwei Prozesse besitzen bezüglich der Betriebsmittel eine zirkuläre Abhängigkeit (Circular Wait).

Verklemmungen können bei Systemen eintreten, die fähig sind, mehrere Prozesse parallel ablaufen zu lassen (Multitasksysteme) und bei denen die Reihenfolge der Betriebsmittelvergabe nicht festgelegt ist. Liegen die Ausführungszeiten der zirkulär abhängigen Prozesse weit genug auseinander, kommt es nicht zum Deadlock. Besteht aber die Möglichkeit einer Verklemmung und will man über den Vogel-Strauß-Algorithmus hinausgehen, so muss man sie verhindern oder vermeiden, ggf. beseitigen.

Die Definitionen von Verklemmungsverhinderung und Verklemmungsvermeidung werden auch öfter vertauscht in der Literatur gefunden.

Verklemmungsprävention (deadlock prevention)

Grundsätzlich gilt: Existiert nur ein Prozess in einem geschlossenen System, so kann dieser niemals verklemmen. Ebenso kann ein Prozess, der nur ein Betriebsmittel benötigt, nicht verklemmen.

Treten Verklemmungen ein, so können diese in der Regel nicht normal beseitigt werden. Stattdessen sollte die Betriebsmittelverwaltung versuchen, präventive Maßnahmen anzuwenden, um eine geeignete Sequentialisierung zu erreichen. Man spricht von einer Verhinderung, wenn mindestens eine der vier Bedingungen für eine Verklemmung nicht erfüllt wird.

Verklemmungsvermeidung (deadlock avoidance)

Zusätzlich kann man versuchen, die Verklemmung zu vermeiden (stellenweise auch Verklemmungsverhütung genannt). Dadurch sind Verklemmungen zwar theoretisch möglich; das System versucht jedoch die Prozesse so zu überwachen, dass diese nicht verklemmen. Dieses Vorgehen basiert auf der Methode des sicheren Zustands. Ein Zustand gilt dann als sicher, wenn mindestens eine Scheduling-Reihenfolge existiert, in welcher alle vorhandenen Prozesse beendet werden können, selbst wenn diese noch ihre maximalen Ressourcenanforderungen stellen sollten.

Bei einer Vermeidung müssen alle möglichen folgenden Vorgänge bekannt sein. Hierbei wird häufig der Bankieralgorithmus angewandt, bei dem die Betriebsmittel nur dann einem Prozess zugeteilt werden, wenn sie vollständig zurückgegeben werden. Beispielsweise hat ein Prozess π₁ insgesamt fünf Betriebsmittel und er benötigt noch drei weitere Betriebsmittel zur vollständigen Ausführung. Das Betriebssystem stellt noch drei weitere Betriebsmittel zu Verfügung. Ein Prozess π₂ besitzt zwei Betriebsmittel und fordert noch acht Betriebsmittel. Demzufolge erhält Prozess π₁ die drei Betriebsmittel. Damit besitzt er alle Ressourcen, um vollständig verarbeitet zu werden, worauf dem Betriebssystem nach der Verarbeitung acht Betriebsmittel frei zu Verfügung stehen, die nun Prozess π₂ zugeteilt werden können. Eine Vermeidung ist oft sehr schwierig, da man schlecht abschätzen kann, welcher Prozess genügend Betriebsmittel wieder freigibt.

Zwei einfache Verfahren zur Vermeidung stellen wait/die und wound/wait dar. Hierbei werden zyklische Abhängigkeiten vermieden, indem es feste Regeln gibt, wer ein Mittel behalten darf und welchen es entzogen werden kann. Dieses Verfahren wird vor allem in Datenbanksystemen in Bezug auf Schreib- und Lesesperren genutzt, daher wird im Folgenden auch der Terminus Transaktionen und nicht Prozesse verwendet:
Bei beiden Verfahren wird jeder Transaktion ein Zeitstempel bei seiner Instanziierung zugewiesen.

wait/die:

• Fordert eine Transaktion eine Sperre an, die von einer jüngeren gehalten wird, so wartet die ältere, bis die Sperre von der jüngeren freigegeben wird.
• Fordert eine Transaktion eine Sperre an, die von einer älteren gehalten wird, so bricht sie sich selber ab (genauer: sie startet neu, allerdings behält sie ihren alten Zeitstempel bei, um so „älter“ zu wirken und ihre Chancen zu erhöhen, diesmal komplett durchlaufen zu können)

wound/wait:

• Fordert eine Transaktion eine Sperre an, die von einer jüngeren gehalten wird, so wird die jüngere abgebrochen (genauer: neu gestartet) und die ältere bekommt die Sperre zugewiesen.
• Fordert eine Transaktion eine Sperre an, die von einer älteren gehalten wird, so wartet sie, bis die Sperre von der älteren wieder freigegeben wird.

Die Terminologie ist wie folgt zu verstehen. wait/die bzw. wound/wait geben an, wie sich die anfordernde Transaktion verhält, wenn ein Sperrkonflikt auftritt. Der erste Terminus gibt jeweils an, was passiert, wenn die anfordernde Transaktion die ältere ist, der zweite Terminus gibt an, was passiert, wenn die anfordernde Transaktion die jüngere ist. „Wait“ bedeutet jeweils: die anfordernde Transaktion wartet auf die Freigabe der Sperre; englisch die ‚stirbt‘ bedeutet die anfordernde Transaktion wird zurückgesetzt; „wound“ (verwundet) bedeutet die anfordernde Transaktion „verwundet“ den Sperrbesitzer, d. h. die anfordernde Transaktion versucht den Sperrbesitzer zurückzusetzen. Um unnötige Rücksetzungen zu vermeiden, kann beim „wound“ auf die Rücksetzung dann verzichtet werden, wenn sich der Sperrbesitzer bereits in der Freigabe befindet. In diesem Fall wartet die anfordernde Transaktion entgegen der Regel, weil sichergestellt ist, dass der Sperrbesitzer an keinem Deadlock beteiligt ist.

Verklemmungsbeseitigung (recovery from deadlocks)

Livelock

Eine andere Form der Blockierung von Prozessen, die wie ein Deadlock die weitere Ausführung des Programms verhindert, ist der Livelock. Er bezeichnet eine Form der Blockierung zweier oder mehrerer Prozesse, die im Unterschied zum Deadlock nicht in einem Zustand verharren, sondern ständig zwischen mehreren Zuständen wechseln, aus denen sie nicht mehr entkommen können. Jeder einzelne Prozess verharrt also nicht für immer im Wartezustand, sondern ist weiterhin aktiv, kann aber auch nicht seine Aufgabe abarbeiten.

Anschaulich kann man sich zum Livelock zwei Personen vorstellen, die sich in einem Gang entgegenkommen und fortwährend versuchen, einander in der gleichen (Absolut-)Richtung auszuweichen, und sich gerade dadurch immer gegenseitig blockieren. Beim Deadlock würden sich – in dieser Veranschaulichung bleibend – die zwei Personen nur gegenüberstehen und jeweils darauf warten, dass die andere beiseite geht, was nicht geschieht.

Bahnbetrieb

Im Bahnbetrieb bezeichnet Deadlock eine Betriebssituation, in der zwei oder mehrere Züge sich gegenseitig so blockieren, dass die Sicherungstechnik keine regulären Zugfahrten mehr zulässt. Hier besteht eine Analogie zur Informatik: Jeder Zug blockiert einen Zugfolgeabschnitt und wartet darauf, in den nächsten Abschnitt einfahren zu können. Ein Deadlock lässt sich in Algorithmen zur Steuerung von Stellwerken dadurch erkennen, dass durch das Stellen einer Fahrstraße ein Zirkelbezug auftritt.

Siehe auch

• Lock
• Petri-Netz
• Philosophenproblem

Weblinks

Wiktionary: Deadlock – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

• Deadlock-Erkennung

Einzelnachweise

1. Andrew S. Tanenbaum: Modern Operating Systems. Prentice Hall International, 2008, ISBN 978-0-13-813459-4. 
2. E. C. Coffman, Michael John Elphick, A. Shoshani: System Deadlocks. In: Computing Surveys. Band 3, Nr. 2, 1971, S. 67–78 (cs.umass.edu [PDF; 896 kB]). 
3. Andrew S. Tanenbaum: Moderne Betriebssysteme. Pearson Studium, 2009, ISBN 978-3-8273-7342-7, S. 539 (eingeschränkte Vorschau in der Google-Buchsuche). 
4. Streckenblock auf eingleisiger Strecke. Stellwerke.de; abgerufen am 25. Juli 2013.
5. Jacob Kohlruss: Untersuchung von Methoden zur Vermeidung von Deadlocks in synchronen Eisenbahnsimulationsprogrammen. Diplomarbeit, Institut für Verkehrsmanagement, Fachhochschule Braunschweig/Wolfenbüttel, 2007.
6. Yong Cui: Simulation-Based Hybrid Model for a Partially-Automatic Dispatching of Railway Operation. Dissertation, Universität Stuttgart, 2009, S. 55ff.