Deadlock (Informatik)

Ein Deadlock (auch Verklemmung genannt) ist in der Informatik ein Zustand von Prozessen, bei dem mindestens zwei Prozesse untereinander auf Betriebsmittel warten, die dem jeweils anderen Prozess zugeteilt sind. Z.B. Kann einem Prozess π1 der Bildschirm zugeteilt worden sein. Gleichzeitig benötigt π1 allerdings den Drucker. Auf der Gegenseite ist der Drucker dem Prozess π2 zugeteilt, der wiederum den Bildschirm fordert.

Ein solcher Zustand kann nur unter bestimmten Voraussetzungen zu Stande kommen:

1. Die Betriebsmittel werden ausschließlich durch die Prozesse freigegeben (No Preemption).
2. Die Prozesse fordern zwar Betriebsmittel, geben aber keine ab (Hold and Wait).
3. Der Zugriff auf die Betriebsmittel ist exklusiv (Mutal Exclusion).
4. Nicht weniger als zwei Prozesse warten in einem geschlossenen System (Circular Wait).

Deadlocks 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.

Verhindern bzw. Vermeidung einer Verklemmung

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, ebenfalls nicht verklemmen.

Treten Verklemmungen ein, so können diese in der Regel nicht normal beseitigt werden. Statt dessen sollte die Betriebsmittelverwaltung versuchen, präventive Maßnahmen anzuwenden. Dabei spricht man von einer Verhinderung, bei der mindestens eine der vier Bedingungen für einen Deadlock nicht erfüllt werden. So könnten z.B. Betriebsmittel im Voraus einem Prozess entzogen, und gezielt einem anderen Prozess zugeteilt werden.

Weitere Möglichkeiten:

• Die benötigten Betriebsmittel für alle Prozesse zugänglich zu machen, in dem man den exklusiven Zugriff auflöst.
• Ein Prozess gibt alle Betriebsmittel frei und kann erst danach auf andere benötigte Betriebsmittel zugreifen.

Wenn man die Verklemmung abnormal auflösen will, so kann man den Prozess vernichten oder ihn auf einen früheren Zustand zurückstellen. Hierbei kann das System jedoch instabil werden. Ebenfalls kann der Prozess verhungern, wenn er ständig zurückgestellt wird und somit nie die benötigten Betriebsmittel erhält.

Zusätzlich kann man versuchen den Deadlock zu vermeiden. Bei einer Vermeidung müssen alle folgenden Vorgänge bekannt sein. Hierbei wird häufig der Bankier-Algorithmus angewandt, bei dem die Betriebsmittel nur dann einem Prozess zugeteilt werden, wenn sie vollständig zurückgegeben werden. Z.B. hat ein Prozess π1 insgesamt 5 Betriebsmittel und er benötigt noch 3 weitere Betriebsmittel zur vollständigen Ausführung. Das Betriebssystem stellt noch 3 weitere Betriebsmittel zu Verfügung. Ein Prozess π2 besitzt 2 Betriebsmittel und fordert noch 8 Betriebsmittel. Dem zu Folge erhält Prozess π1 die 3 Betriebsmittel. Damit besitzt er alle Ressourcen um vollständig verarbeitet zu werden, worauf dem Betriebssystem nach der Verarbeitung 8 Betriebsmittel frei zu Verfügung stehen, die nun Prozess π2 zugeteilt werden können.

Eine Vermeidung ist oft sehr schwierig, da man schlecht abschätzen kann, welcher Prozess genügend Betriebsmittel wieder freigibt.